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