中文分词相关算法

1. 分词算法2：N-gram模型

N-gram是一种基于隐马尔科夫模型（HMM）假设的模型，在自然语言处理领域非常实用。它不仅适用于分词，还可以应用于文本分类、语音识别、实体识别等领域，是自然语言处理乃至机器学习领域的经典算法之一。它也是概率论中的一个重要应用。

N-gram的概率计算

假设一句话的字集合是S={W1,W2,W3,...,Wn}，那么这句话的概率表达公式如下： [ P(S) = P(W1) times P(W2|W1) times P(W3|W2,W1) times ... times P(Wn|Wn-1,Wn-2,...,W1) ]

当一句话只有两个字时，S={W1,W2}，则有： [ P(W1,W2) = P(W1) times P(W2|W1) ]

这个公式表示的是联合概率。当字数增加时，计算复杂度会显著上升，因为最后一项的参数数量会达到O(n)。

数据稀疏问题

当字词数量很大时，计算中可能会遇到某些条件概率为零的情况，因为某些组合在自然文本中可能从未出现过。这会导致整体概率为零，从而影响模型的泛化能力。

词粒度过细问题

当N取所有字时，全概率组合可能导致词粒度过细，使得分词结果失去意义。尤其在长句中，这样的分词器会倾向于将所有词打碎，从而产生无意义的分词结果。

N-gram的出现

考虑到上述问题，我们引入了马尔科夫假设，即当前状态只与前一个状态有关。放到文本中，这意味着每个字的出现只与其后出现的L个字有关。

Bi-Gram和Tri-Gram模型

当N=2时，称为二元模型（Bi-Gram），当前字的出现只依赖于前一个字。公式如下： [ P(W2|W1) ]

当N=3时，称为三元模型（Tri-Gram），当前字的出现只与前两个字有关。公式如下： [ P(W3|W2,W1) ]

在实际应用中，最常用的模型是二元模型（Bi-Gram）和三元模型（Tri-Gram），有时也会使用一元模型（Uni-Gram）。N>4的情况较少使用，因为随着N的增大，数据稀疏问题变得更加严重。

如何获得条件概率

我们可以通过最大似然估计来获得条件概率。例如，二元模型中的条件概率P(W2|W1)可以通过以下公式计算： [ P(W2|W1) = frac{text{同时出现的次数}}{text{W1出现的次数}} ]

对于第一个字的概率P(W1)，可以通过以下公式计算： [ P(W1) = frac{text{以W1开头的句子数量}}{text{总句子数量}} ]

例子

假设我们有一句话"S='我们的生活富有了'"，采用二元模型（Bi-Gram）来计算其概率。

这些值来自于以下二元模型的组合： [ P(text{我/}), P(text{们|我}), P(text{的|们}), P(text{生|的}), P(text{活|生}), P(text{富|活}), P(text{裕|富}), P(text{了|裕}) ]

例如： [ P(text{们|我}) = frac{text{出现次数}}{text{我出现的次数}} ]

假设训练语料中“我们”一词出现了1000次，“我”这个词出现了10000次，则： [ P(text{们|我}) = frac{1000}{10000} = 0.1 ]

通过计算可以得到P(S1), P(S2)，选择其中概率最大的方案作为最终分词结果。

N-gram分词工业界做法

工业界通常采用更为复杂的分词方法，如前缀字典树匹配和动态规划算法。以“研究生物学”为例，步骤如下：

1. 前缀字典树匹配：使用字典树（提前加载好的词典）进行匹配识别词。推荐使用双数组Trie树（Double-Array Trie）。
2. 构建有向无环图（DAG）：基于匹配结果构建有向无环图。
3. 求最短路径（Dijkstra算法）：使用动态规划算法求解最短路径，得到最佳分词结果。

分词算法3：基于训练标注的模型法

字标注法

字标注法包括4字标注法（{S,B,M,E}）和6字标注法（{S,B,M1,M2,M,E}）。

• 4字标注法：单字成词（S）、词的开头（B）、词的中间部分（M）、词的结尾（E）。
• 6字标注法：在4字标注的基础上增加了中间字的标注（M1,M2,M）。

例如：“自然语言处理”可以标注为“自/B 然/M1 语/M2 言/M 处/M 理/E”。

字标注法本质上不是一种分词算法，而是一种分字标注的基础。许多模型基于字标注法进行分词，如隐马尔科夫模型（HMM）、最大熵模型（ME）、条件随机场（CRF）、循环神经网络（RNN）、长短时记忆网络（LSTM）等。

小结

以上介绍了工业界常用的分词算法，但实际应用中仍有许多细节问题需要解决。例如，标注数据集的大小和精度、数据平滑方法等。尽管现在从模型优化的角度提升分词准确率难度较高，但对于特定场景下的特殊分词，现有模型训练语料的效果已经相当不错。在具体业务场景中，往往需要针对特殊情况做个性化处理，例如添加个性化词库或规则优化。