分词

对于西方拼音语言来说，从词之间由明确的分界符，而很多亚洲语言（如汉语、日语、韩语、泰语）词之间没有明确的分界符，因此需要先对句子进行分词，才能做进一步的自然语言处理（也适用于英文词组的分割、或者手写识别，平板电脑、智能手机手写时单词间的空格可能不清楚）。

分词的输入是一串词，分词的输出是用分界符分割的一串词。

分词的不一致性问题：

• 越界型错误：“北京大学生” -> “北京大学”、“生”
• 覆盖型错误：“北京大学” -> “北”、“京”、“大”、“学”
• 颗粒度的不一致性

分词的颗粒问题：

• 在分词的同时，找到复合词的嵌套结构。如“北京”、“大学”、“北京大学”
• 机器翻译：一般来讲，颗粒度大翻译效果好。如“北京大学”
• 语音识别，网页搜索：一般来讲，颗粒度小效果好。如“北京”、“大学”

中文分词是一个已解决问题，只要采用统计语言模型，效果差不到哪去。一般不同应用该有不同的分词系统，需要针对不同的应用设计实现专门的分词系统。 构造分词器时，更好的做法是让一个分词器同时支持不同层次的词的切分，由不同的应用自行决定切分的颗粒度。通常中文分词工作的重点是继续做数据挖掘，不断完善复合词的词典（新词发现）。

基于字符串匹配的分词方法（“查字典”）

此方法按照不同的扫描方式，逐个查找词库进行分词。根据扫描方式可细分为：正向最大匹配，反向最大匹配，双向最大匹配，最小切分(即最短路径)；总之就是各种不同的启发规则。

全切分方法

它首先切分出与词库匹配的所有可能的词，再运用统计语言模型决定最优的切分结果。最好的一种分词方法应该保证分完词后这个句子出现的概率最大。

问题：穷举所有可能的分词方法并计算每种可能性的句子的概率，计算量相当大。

技巧：看成一个动态规划（Dynamic Programming）问题，利用维特比（Viterbi）算法快速地找到最佳分词。

维特比（Viterbi）算法

维特比算法是一个特殊但是应用最广的动态规划算法。利用动态规划，可以解决任何一个图中的最短路径问题。维特比算法是针对一个特殊的图—— 篱笆网络（Lattice） 的有向图最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都要用它来解码，如语音识别、机器翻译、拼音转汉字（中文输入法）、分词。

例如输入法，输入的可见序列为 y1,y2,...,yN$y_1,y_2,...,y_N$，而产生它们的隐含序列是 x1,x2,...,xN$x_1,x_2,...,x_N$

P(xi|xi−1)$P(x_i|x_{i-1})$ 是状态之间的转移概率，P(yi|xi)$P(y_i|x_i)$ 是每个状态的产生概率。

维特比算法:

• 从点 S$S$ 开始，对于第一个状态 x1$x_1$ 的各个节点，计算距离
  d(S,xi)$d(S,x_i)$ ，只有一步所以都是最短距离。
• 对于第二个状态 x2$x_2$ 的所有节点，计算 S$S$ 到它们的最短距离，计算复杂度 O(n1⋅n2)$O(n_1\cdot n_2)$

• 如上从第二个状态走到第三个状态，直到最后，就得到了网络的最短路径。每一步计算的复杂度都与相邻两个状态 Si$S_i$ 和 Si+1$S_{i+1}$ 各自的节点数目 ni,ni+1$n_i,n_{i+1}$的乘积成正比，假定节点最多的状态由D$D$个节点，长度为N$N$，算法复杂度为 O(N⋅D2)$O(N\cdot D^2)$

由字构词的分词方法

可以理解为字的分类问题，也就是自然语言处理中的sequence labeling问题，通常做法里利用HMM，MAXENT，MEMM，CRF等预测文本串每个字的tag，比如B，E，I，S，这四个tag分别表示：beginning, inside, ending, single，也就是一个词的开始，中间，结束，以及单个字的词。

一般而言，方法一和方法二在工业界用得比较多，方法三因为采用复杂的模型，虽准确率相对高，但耗时较大.

一个文本串除了分词，还需要做词性标注，命名实体识别，新词发现等。

《数学之美》 4 26

http://www.flickering.cn/ads/2015/02/%E8%AF%AD%E4%B9%89%E5%88%86%E6%9E%90%E7%9A%84%E4%B8%80%E4%BA%9B%E6%96%B9%E6%B3%95%E4%B8%80/