为此，人们也提出了基于字标注的思路，所谓字标注，就是通过几个标记把句子的正确分词法表示出来。比如4标注的是：single，单字成词。begin，多字词的开头。middle，三字以上词语的中间部分。end，多字词的结尾。它能够较好地解决未登录词的问题。但它存在速度较慢的问题。总之，各有优缺点，实际使用可能会结合两者。例如jieba分词，用的是有向无环图的最大概率组合。

2.2 中文分词涉及的主要算法

2.2.1 TRIE树

TRIE树在计算机科学中，也被称为数字树。有时候也被叫做小树或前缀树（可以通过前缀搜索），是一种搜索树。TRIE树是一种被用于存储动态集或关联的有序树的数据结构。树的值倾向于仅与叶子相关联，以及一些对应于期望的键值的内部节点。

在TRIE树中，键被列在它们的节点中。每个完整的词都有一个与之相关联的任意整数值。一个TRIE树可以看作是一个树状的确定性的有限自动机。每个有限语言由TRIE自动机生成，并且每个TRIE可以被压缩成确定性非循环有限状态自动机。

2.2.2 有向无环图（DAG）

有向非循环图（DAG）是一个没有定向循环的有限有向图。也就是说，它的元素包括顶点、边。每个边从一个顶点引导到另一个顶点。因此无法做到：在任何顶点v处开始，遵循一致的定向的边序列，最终循环回v。DAG是有向图，其具有拓扑排序。此外，DAG也可以被看作是一个由顶点构成的序列。序列中每个边从前序的节点指向后序的节点。

DAG通过顶点和边的集合形成图形，其中顶点是由成对的边连接的无结构对象。在有向图的情况下，每个边具有从一个顶点到另一个顶点的指向。如果其第一个边的起始顶点等于其最后一个边的结束顶点，则路径形成一个周期。有向非循环图是没有循环的有向图。

有向图的拓扑排序是其顶点到序列中的顺序。因此边的开始顶点比结束顶点更早出现在序列中。具有拓扑排序的图形不能有任何循环。因为这样进入循环最早顶点的边将按错误的方式初始化。因此，该属性可以用作有向非循环图的另一种理解。也就是说，它们是具有拓扑排序的图。

2.2.3 Viterbi算法与HMM模型

一个HMM模型包含两组状态集合和三个概率集合。

隐藏状态：一个系统的（真实）状态。

观察状态：在这个过程中‘可视’的状态。

 向量：包含了（隐）模型在时间t=1时一个特殊的隐藏状态的概率（初始概率）。 也称为初始概率。

状态转移矩阵：包含了从一个隐藏状态得到另一个隐藏状态的概率

上式表示t-1时刻隐藏状态i到t时刻隐藏状态j的概率。

混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，得到某个观察状态的概率。也称为发射概率。

上式表示为隐藏状态i到观察状态j的概率。

Viterbi算法是一种利用了动态规划思想的HMM算法，由Andrew Viterbi在1967年提出。

所谓解码，即给定观察序列搜索最可能的隐藏序列。考虑语音信号识别这个例子，一个人只能听到语音的声音信号，但是他更想知道文本的内容，文本内容在这里就是隐藏状态。

2.3 中文分词器面临的困难

中文分词的主要困难在于歧义和未登录词。歧义又分为两种，即结构性歧义

和组合型歧义。结构性歧义指某一个汉字与其之前和之后的字都可以组合成次。组合型歧义指某几个字既可以划分，又可以不划分。 Python中文分词技术研究(3):http://www.chuibin.com/tongxin/lunwen_205968.html