从trie树说起

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

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

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

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，运行后的输出结果为：

这段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】

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