词条化
分词又叫做词条化（tokenlize），指的是将原始的字符流转换成一个一个词条（token）的过程。词条化属于自然语言处理中预处理的一个步骤，它是分析语义的基础。下图是一个词条化的例子。
在不同的语言中，分词的方法和难点不同。在英语中，词与词之间有空格作为自然分隔符，处理的难点在于大小写代表的不同含义以及符号的用法。比如单词 china 在小写的情况下指的是陶瓷器，而大写的 China 代表中国。大小写的用法在英语中非常常见，包括句首、人名地名、专有名词以及缩略语等，如何正确处理这些大小写等情况是英语词条化的难点之一。另一个比较复杂的情景是上撇号「 ’ 」的用法，它既可以代表所有关系也可以代表缩写。比如说 aren’t 的词条可能会有以下几种结果：
在处理一些东亚语言如汉语、日语、泰语等时，问题就会复杂很多。在中文里是以字为基本书写单位，词语甚至句子之间都没有明显的区分标记。中文字和词的界限模糊，不同的分词方法可以将语料分解成不同的语义。例如：「南京市长江大桥」可以被分为：
- 南京市 \ 长江 \ 大桥
- 南京 \ 市长 \ 江大桥
在英语中词的构成单元是字母，而字母的数量有限（ 26个 ），可以通过枚举的方式将所有的词加入词典中。常见的人名地名以及专有名词可以在有限的空间内进行存储。
而在中文中，字与字之间排列可以组合出名词的数量过于庞大，无法以词典的方式进行识别。因此，如何识别出人名等不常见的名词也是中文分词的难点。
停用词
在自然语言中，存在一些没有实际含义的虚词，例如汉语中的「了、着、吧、啊」和英语中的「the、that、a」等。还有一些结构助词「的、是、对」和「is、to、on、of」等。
不同的应用场景下，对于这些词的处理方式不相同。训练词向量时，由于这些词没有实际意义，应该作为停用词（stop word）去除，下图是英语中的一种停用词表。
在构建知识图谱时，结构助词能够表达实体之间关系，比如语句「苹果是一种水果」构建了 「苹果」与「水果」的从属关系。
在信息检索中，这些词通常没有意义，可以作为停用词，并且由于停用词的出现频率很高，停用后能提高检索效率以及准确度。但是在一些查询中，例如 Beatles 乐队的名曲 Let It Be 在去除停用词以后就很难被检索到。因此，在现代搜索引擎中，一般不停用词，而是采用了很多方法避免停用词产生过大开销。
中文分词方法
中文的分词方法一般分为三类：基于字典的分词方法、基于统计的分词方法和机器学习分词方法。
基于词典的分词方法
使用基于词典的分词方法时，需要一个中文词典，将待分词的文本与词典中的词条进行匹配。
正向最大匹配法
输入：字符串 s
过程：
1. 令 i=0，指针 pi 指向 s 的初始位置
2. repeat
3. 计算当前指针 pi 到字串末端的字数(即未被切分字串的长度) n
4. 令 m=词典中最长单词的字数，如果 n<m, 令 m=n
5. 从当前 pi 起取 m 个汉字作为词 wi
6. if wi 在词典中
7. then 在 wi 后添加一个切分标志，根据 wi 的长度修改指针 pi
8. else
9. 将 wi 从右端去掉一个字
10. until pi 指向字串末端
输出： 添加切分标志后的字符串 s
最短路径法
在使用最短路径法之前除了需要词典以外，还需要一个词图。词图是一个全联通图，每个顶点代表词典中的一个词，顶点之间的边代表两个词组合的距离，例如「天气」和「好」之间的距离小于「天气」和「大」的之间距离，因为「天气好」这个组合的可能性更高。
输入：字符串 S = c1c2...cn, 其中 ci 为单个的汉字
过程：
1. 建立一个节点数为 n+1 的切分有向无环图 G，各节点编号为 V0，V1...Vn
2. 在相邻节点Vk，Vk-1之间建立有向边，边长查词图得出为Lk
3. repeat
4. if 存在 w = ci...cj (0<i<j<=n) ,并且 w 在词典中
5. then 将 w 作为新节点加入图中，与 Vi-1 和 Vj 建立有向边
6. until 没有新的 w 能够加入图中
7. 计算从 V0 到 Vn 的最短路径
输出：依次输出最短路径上的顶点
其中，G 的最短路径求解可以使用 Dijkstra 等方法。
基于统计的分词方法
基于统计的分词方法首先建立学习样本的生成模型，再利用模型对预测结果进行间接推理。
隐马尔可夫模型
首先对分词问题建立隐马尔可夫模型，状态值集合为{B, M, E, S}，分别代表字在词语中的不同位置（B，begin 表示词语的起始字；M，middle 表示词语的中间子；E，end 表示词语的结束字；S，single 表示单子成词）。观察值为需要分词的语料。在这个问题中，需要通过观察值求出可能性最大的状态序列，例如：
状态序列：BMEBMBM
观察值：南京市长江大桥
事实上，一个观察值能够对应多种可能的状态序列，就像是「南京市长江大桥」这个语料也有不同的分词解法：
状态序列1：BME \ BM \ BM
状态序列2：BM \ BM \ S \ BM
观察值：南京市长江大桥
如何对一个语料「正确地」分词就取决于如何使我们需要的状态序列的概率最大，这是一个 HMM 的参数估计问题。这里需要确定的参数有初始状态的概率分布 π \pi π ，状态转移概率 a i j a_{ij} aij 和发射概率 b i j b_{ij} bij 。可以使用最大似然估计训练出所需的参数。
训练参数完成后得到了隐马尔可夫模型 μ = ( S , K , A , B , π ) \mu = \left(S, K, A, B, \pi \right ) μ=(S,K,A,B,π) 后，要解决的问题变成了序列问题：给定一个观察序列 O = O 1 O 2 … O T O = O_1O_2…O_T O=O1O2…OT 和模型 μ = ( A , B , π ) \mu = \left ( A,B,\pi \right ) μ=(A,B,π) ，如何快速有效地选择在一定意义下「最优」的状态序列 Q = q 1 q 2 … q t Q = q_1q_2…q_t Q=q1q2…qt ，使得该状态序列「最好地解释」观察序列？
这个问题一般使用 Viterbi 算法求解。
基于语义的分词方法
未完待续
参考资料
- 宗成庆.统计自然语言处理(第2版). 统计自然语言处理. 2008.
- 李航. 统计学习方法. 2012.
本作品采用知识共享署名-非商业性使用 3.0 未本地化版本许可协议进行许可。欢迎转载，演绎，但是必须保留本文的链接，不得用于商业目的。如您有任何疑问或者授权方面的协商，请与我联系。
