分词的基本原理

本文只是对NLP知识进行梳理，巩固及时查漏补缺。

  在对文本处理的时候，首要做的就是分词。英文可以按空格分词，但有时候需要把多个单词作为一个分词，比如一些名词如“New York”，需要作为一个词看待。而中文没有空格，分词就是一个需要专门去解决的问题了。无论是英文还是中文，分词的原理都是类似的，本文就对文本挖掘时的分词原理做一个总结。

三大主流分词方法：

• 基于词典的方法；
• 基于规则的方法；
• 基于统计的方法。

1. 分词的基本原理

  现代分词几乎都是基于统计的分词，而统计的样本内容来自于一些标准的语料库。
  假如有一个句子：“小明来到荔湾区”，我们期望语料库统计后分词的结果是："小明/来到/荔湾/区"，而不是“小明/来到/荔/湾区”。那么如何做到这一点呢？
  从统计的角度，我们期望"小明/来到/荔湾/区"这个分词后句子出现的概率要比“小明/来到/荔/湾区”大。数学表示就是：如果有一个句子S，它有m种分词选项，
其中下标代表第种分词的词个数。如果我们从中选择了最优的第𝑟种分词方法，那么这种分词方法对应的统计分布概率应该最大，即：
但是我们的概率分布并不好求出来，因为它涉及到个分词的联合分布。在NLP中，为了简化计算，我们通常使用马尔科夫假设，即每一个分词出现的概率仅仅和前一个分词有关，即：
由马尔科夫假设，则联合分布为：
而通过我们的标准语料库，我们可以近似的计算出所有的分词之间的二元条件概率，比如任意两个词,，它们的条件概率分布可以近似的表示为：
其中𝑓𝑟𝑒𝑞(𝑤1,𝑤2)表示𝑤1,𝑤2在语料库中相邻一起出现的次数，而其中𝑓𝑟𝑒𝑞(𝑤1),𝑓𝑟𝑒𝑞(𝑤2)分别表示𝑤1,𝑤2在语料库中出现的统计次数。
  利用语料库建立的统计概率，对于一个新的句子，我们就可以通过计算各种分词方法对应的联合分布概率，找到最大概率对应的分词方法，即为最优分词。

2. 基于规则或词典的方法

定义：按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。

1. 按照扫描方向的不同：正向匹配和逆向匹配；
2. 按照长度的不同：最大匹配和最小匹配；

2.1 正向最大匹配思想MM

1. 从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
2. 查找大机器词典并进行匹配：
     1. 若匹配成功，则将这个匹配字段作为一个词切分出来。
     2. 若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，重复以上过程，直到切分出所有词为止。

例： 我们要对南京市长江大桥这个句子进行分词，根据正向最大匹配的原则：

1. 先从句子中拿出前5个字符“南京市长江”，把这5个字符到词典中匹配，发现没有这个词，那就缩短取字个数，取前四个“南京市长”，发现词库有这个词，就把该词切下来；
2. 对剩余三个字“江大桥”再次进行正向最大匹配，会切成“江”、“大桥”；
3. 整个句子切分完成为：南京市长、江、大桥；

2.2 逆向最大匹配算法RMM
  该算法是正向最大匹配的逆向思维，匹配不成功，将匹配字段的最前一个字去掉，实验表明，逆向最大匹配算法要优于正向最大匹配算法。

例：取出南京市长江大桥的后四个字“长江大桥”，发现词典中有匹配，切割下来；对剩余的“南京市”进行分词，整体结果为：南京市、长江大桥。

2.3 双向最大匹配法BM
  双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。

例：双向的最大匹配，即把所有可能的最大词都分出来，上面的句子可以分为：南京市、南京市长、长江大桥、江、大桥。

2.4 设立切分标志法
  收集切分标志，在自动分词前处理切分标志，再用MM、RMM进行细加工。

3. 基于统计的分词

  随着大规模语料库的建立，统计机器学习方法的研究和发展，基于统计的中文分词方法渐渐成为了主流方法。
主要思想：把每个词看做是由词的最小单位各个字组成的，如果相连的字在不同的文本中出现的次数越多，就证明这相连的字很可能就是一个词。因此我们就可以利用字与字相邻出现的频率来反应成词的可靠度，统计语料中相邻共现的各个字的组合的频度，当组合频度高于某一个临界值时，我们便可认为此字组可能会构成一个词语。
主要统计模型：

• N元文法模型（N-gram）
• 隐马尔可夫模型（Hidden Markov Model ，HMM）
• 最大熵模型（ME），
• 条件随机场模型（Conditional Random Fields，CRF）等。

N元模型
  只依赖于前一个词太武断了，我们能不能依赖于前两个词呢？
  这样也是可以的，只不过这样联合分布的计算量就大大增加了。我们一般称只依赖于前一个词的模型为二元模型(Bi-Gram model)，而依赖于前两个词的模型为三元模型。以此类推，我们可以建立四元模型，五元模型,...一直到通用的N元模型。越往后，概率分布的计算复杂度越高。当然算法的原理是类似的。
   在实际应用中，N一般都较小，一般都小于4，主要原因是N元模型概率分布的空间复杂度为O()，其中|V|为语料库大小，而N为模型的元数，当N增大时，复杂度呈指数级的增长。
  N元模型的分词方法虽然很好，但是要在实际中应用也有很多问题，

1. 某些生僻词，或者相邻分词联合分布在语料库中没有，概率为0。这种情况我们一般会使用拉普拉斯平滑，即给它一个较小的概率值，
2. 如果句子长，分词有很多情况，计算量也非常大，这时我们可以用下一节维特比算法来优化算法时间复杂度。

维特比算法与分词
  为了简化原理描述，我们的讨论都是以二元模型为基础。
  对于一个有很多分词可能的长句子，我们当然可以用暴力方法去计算出所有的分词可能的概率，再找出最优分词方法。但是用维特比算法可以大大简化求出最优分词的时间。
  大家一般知道维特比算法是用于隐式马尔科夫模型HMM解码算法的，但是它是一个通用的求序列最短路径的方法，不光可以用于HMM，也可以用于其他的序列最短路径算法，比如最优分词。
  维特比算法采用的是动态规划来解决这个最优分词问题的，动态规划要求局部路径也是最优路径的一部分，很显然我们的问题是成立的。首先我们看一个简单的分词例子："人生如梦境"。它的可能分词可以用下面的概率图表示：

  图中的箭头为通过统计语料库而得到的对应的各分词位置BEMS（开始位置，结束位置，中间位置，单词）的条件概率。比如P(生|人)=0.17。有了这个图，维特比算法需要找到从Start到End之间的一条最短路径。对于在End之前的任意一个当前局部节点，我们需要得到到达该节点的最大概率δ，和记录到达当前节点满足最大概率的前一节点位置Ψ。

参考：https://www.cnblogs.com/pinard/p/6677078.html