背景介绍
词是表达语义的最小单位，分词是搜索引擎的基石。
在搜索引擎中，倒排索引就是由一个个Term所构成，分词器通过对自然语言的理解，拆分出Term。分词的输入是一串连续的文字，对于英文”girl is beautiful.boy is handsome.”分词比较容易，可以根据空格和标点符号分割，那最终会分为girl/is/beautiful/boy/is/handsome（一般来说，is作为停用词），是不是很容易？但这种方式在中文中却不行，”女孩美丽，男孩帅气。”这句话应该分为”女孩/美丽/男孩/帅气”,不是简单的靠空格和符号就能实现的。
上例提出了中文分词的背景，那么总要有理论来解决中文分词的问题。经过几十年的研究，中文分词方法也取得了长足的发展，产生了众多的分词方法，主要分为基于字符串匹配的分词方法，基于统计的分词方法，基于理解的分词方法三大流派。
##基于字符串匹配的分词方法
基于字符串匹配的分词算法也叫做机械分词算法，一般都需要事先建立足够大的分词词典，然后将待分词文本中的字符串与分词词典中的词进行匹配，如果匹配成功，该字符串当做一个词从待分词文本中切分出来，否则不切分。
下面介绍下主流的字符串匹配算法
最大正向匹配分词算法(Forward Maximum Matching，FMM)
这是字符串匹配分词算法中最基本的一种分词算法，统计结果表明，单纯使用最大正向匹配算法的错误率为1/169。优点是原理简单，切分速度快，易与实现。缺点是歧义处理不精确。
最大逆向匹配分词算法(Reverse Maximum Matching，RMM)
与FMM算法的基本思想相同，不同的是该方法从待切分的汉字串的末位开始处理，每次不匹配时去掉最前面的一个汉字，继续匹配。优点同FMM一样，而且最大逆向匹配算法对交集型歧义字段的处理精度比正向的要高，错误率在1/245左右，缺点是不能完全排除歧义现象。
双向最大匹配算法(Bi-directction Matching method，BMM)
双向匹配算法基本原理是同时进行FMM和RMM扫描，然后分析两种扫描的结果。如果两种扫描结果一致，则认为不存在歧义现象；如果不一致，则需要定位到歧义字段处理。优点是提高了分词的准确率，消除了部分歧义现象。缺点是算法执行要做双向扫描，时间复杂度会有所增加。
全切分算法
全切分算法是指切分出字符串中所有可能的词语，该算法可以大大提高切分的召回率，识别出所有可能的歧义现象。但缺点是算法复杂度比较高。
总结：
字符串匹配分词方法，逻辑简单清晰，易实现，分词性能较高。但是严重依赖字典，如果某些词在字典中未登陆，则会对分词的精度产生较大的影响。另外算法的效率很大层面体现在字典的数据结构上，如果用Hash表的方式，检索最快但是内存占用大，一般情况下会牺牲部分性能来降低词典的容量比如TRIE索引树词典、逐词二分词典、整词二分词典。
基于统计的分词方法
下面介绍下统计分词的常用分词方法
N元文法模型(N-gram)
令C=C1C2…Cm．C 是待切分的汉字串，W=W1W2…Wn．W 是切分的结果。
设P(WlC)是汉字串C切分为W的某种估计概率。Wa，Wb，⋯．Wk是C的所有可能的切分方案。那么，基于统计的切分模型就是这样的一种分词模型，它能够找到目的词串W ，使得W 满足：
P(W|C)=MAX(P(Wa|C),P(Wb|C)…P(Wk|C))，
即估计概率为最大之词串。我们称函数P(W|C)为评价函数。一般的基于统计的分词模型的评价函数，都是根据贝叶斯公式．同时结合系统本身的资源限制，经过一定的简化，近似得来的。根据贝叶斯公式， 有：P(W|C)=P(W) P(C|W)/P(C)，对于C的多种切分方案，P(C)是一常数，而P(C|W)是在给定词串的条件下出现字串C的概率，故P(C|W)=1。所以 ，我们用P(W)来代替P(W|C)。那么，如何估计P(W)呢?最直接的估计P(W)的方法利用词的n-gram，即：
P(W)=P(W1) P(W2lW1) P(W3|W1W2)⋯P(Wk|W1,W2…Wk-1)
但是，由于当前的计算机技术和我们现有的语料资源所限，这种方法存在致命的缺陷：①对于有6万词的词典而言，仅词和词的bigram就可能需要60000 x 60000=3600M的统计空间，这是当前的计算机硬件水平所难以接受的，更不要说更大的n-gram 了。
②需要与上述空间相当的熟语料，否则就会产生训练语料不足所产生的数据稀疏问题。
③由于不同领域的语料库的用词有所差异，针对某一个领域的语料库统计出来的n-gram，若用于其它领域，其效果难以预料，而目前通过语料库搭配来克服领域差民间的方法尚未成熟。因此，利用词的n-gram 直接估计P(W)的方法，在目前是不可行的。基于上述的原因，大多数基于统计的分词模型都没有直接采用上述公式，而是采用各种各样的估计方法，从不同的角度，实现对P(W)的近似。
隐马尔可夫模型(Hidden Markov Model，HMM)
##
