自然语言处理(2)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

自然语言处理(2)

简介:

从trie树说起

Trie树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。

Trie树可以利用字符串的公共前缀来节约存储空间。如下图所示,该trie树用10个节点保存了6个字符串tea,ten,to,in,inn,int:

image

 

trie树的优缺点

在该trie树中,字符串in,inn和int的公共前缀是“in”,因此可以只存储一份“in”以节省空间。当然,如果系统中存在大量字符串且这些字符串基本没有公共前缀,则相应的trie树将非常消耗内存,这也是trie树的一个缺点。

Trie树的基本性质可以归纳为:

(1)根节点不包含字符,除根节点意外每个节点只包含一个字符。

(2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

(3)每个节点的所有子节点包含的字符串不相同。

 

trie树的demo

Ansj作者ansjsun为此数据结构专门开了一个项目,clone下来之后可以用作者提供的一个demo进行测试:

import java.io.BufferedReader;
import java.io.StringReader;

import love.cq.domain.Forest;
import love.cq.library.Library;
import love.cq.splitWord.GetWord;

/**
 * @author feng
 *
 */
public class TreeSplitTest {

    /**
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        /**
         * 词典的构造.一行一个词后面是参数.可以从文件读取.可以是read流.
         */
        String dic = "中国\t1\tzg\n人名\t2\n中国人民\t4\n人民\t3\n孙健\t5\nCSDN\t6\njava\t7\njava学习\t10\n";
        Forest forest = Library.makeForest(new BufferedReader(new StringReader(
                dic)));

        /**
         * 删除一个单词
         */
        Library.removeWord(forest, "中国");
        /**
         * 增加一个新词
         */
        Library.insertWord(forest, "中国人");
        String content = "中国人名识别是中国人民的一个骄傲.孙健人民在CSDN中学到了很多最早iteye是java学习笔记叫javaeye但是java123只是一部分";
        GetWord udg = forest.getWord(content);

        String temp = null;
        while ((temp = udg.getFrontWords()) != null)
            System.out.println(temp + "\t\t" + udg.getParam(1) + "\t\t"
                    + udg.getParam(2));
    }

}

以上代码完全来自ansjsun的demo,运行后的输出结果为:

image

这段demo的目的是利用一个小词典对后面一句话进行分词,词典被用来构造了一颗Trie树,也就是代码中的forest。这个版本的分词器中需要引入条件概率(隐马尔可夫模型)提高分词的准确性。

 

CRF 简介入门

Conditional Random Field:条件随机场,一种机器学习技术(模型)。

CRF由John Lafferty最早用于NLP技术领域,其在NLP技术领域中主要用于文本标注,并有多种应用场景,例如:

  • 分词(标注字的词位信息,由字构词)
  • 词性标注(标注分词的词性,例如:名词,动词,助词)
  • 命名实体识别(识别人名,地名,机构名,商品名等具有一定内在规律的实体名词)

 

使用CRF进行中文分词

 1)CRF VS 词典统计分词

    • 基于词典的分词过度依赖词典和规则库,因此对于歧义词和未登录词的识别能力较低;其优点是速度快,效率高
    • CRF代表了新一代的机器学习技术分词,其基本思路是对汉字进行标注即由字构词(组词),不仅考虑了文字词语出现的频率信息,同时考虑上下文语境,具备较好的学习能力,因此其对歧义词和未登录词的识别都具有良好的效果;其不足之处是训练周期较长,运营时计算量较大,性能不如词典分词

 2)CRF VS HMM,MEMM

    • 首先,CRF,HMM(隐马模型),MEMM(最大熵隐马模型)都常用来做序列标注的建模,像分词、词性标注,以及命名实体标注
    • 隐马模型一个最大的缺点就是由于其输出独立性假设,导致其不能考虑上下文的特征,限制了特征的选择
    • 最大熵隐马模型则解决了隐马的问题,可以任意选择特征,但由于其在每一节点都要进行归一化,所以只能找到局部的最优值,同时也带来了标记偏见的问题,即凡是训练语料中未出现的情况全都忽略掉
    • 条件随机场则很好的解决了这一问题,他并不在每一个节点进行归一化,而是所有特征进行全局归一化,因此可以求得全局的最优值。

CRF 原理

1)CRF把分词当做字的词位分类问题,通常定义字的词位信息如下:

  • 词首,常用B表示
  • 词中,常用M表示
  • 词尾,常用E表示
  • 单子词,常用S表示

2)CRF分词的过程就是对词位标注后,将B和E之间的字,以及S单字构成分词

3)CRF分词实例:

  • 原始例句:我爱北京天安门
  • CRF标注后:我/S 爱/S 北/B 京/E 天/B 安/M 门/E
  • 分词结果:我/爱/北京/天安门 

CRF 分词及使用

目前常见的CRF工具包有pocket crf, flexcrf 车crf++。下面的链接是使用CRF进行中文分词的示例:

http://x-algo.cn/index.php/2016/02/27/crf-of-chinese-word-segmentation/

总结

在下面将介绍中文分词中的几个经典算法,包括正向最大匹配、逆向最大匹配、逐词匹配、最少切分和全切分。

作者:skyme 出处: http://www.niubua.com/

联系方式: 
邮箱【cloudskyme@163.com】 
QQ【270800073】

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章