将所有可能的分词结果按照词语构建成一个有向无环图，寻找其中联合概率最大的路径。

解释

所需的语料是一个包含词语频率的字典。查找所有可能的分词结果可以通过查找字典中的词是否在一个字符串的开始位置来完成。

构建成有向无环图后，我们找出所有路径中联合概率（朴素观点为：各个词语概率相乘）最大的路径。但一般情况下图理论和图相关的库都是用来求解最短路径（所有路径中权重之和最小的路径），因此这里做数学上的变换，能够按照最小路径求解的方式，找到联合概率最大的路径。具体变动如下:

使用 log 函数将求解相乘问题转换成相加问题

log(a * b) = log(a) + log(b)

使用倒数函数将求解最大问题变成求解最小问题

a > b
then
1/a < 1/b

示例

以 我们在野生动物园玩 为例，假设我们的词典里只包含如下词汇

词汇 频数 概率 概率的倒数 log(概率的倒数)
我们 30 0.30 3.3 1.19
在 40 0.40 2.5 3.69
在野 2 0.02 50 3.91
野生动物园 8 0.08 12.5 2.53
物 1 0.01 100 4.61
园 1 0.01 100 4.61
玩 18 0.18 5.6 1.72

NOTE : log 函数在这里是以自然对数 e 为低的，等同于函数 ln

从 我们在野生动物园玩 开始，扫描词汇表，找到匹配的前缀词汇。

  1. 第一轮找到词汇 我们，剩余未分词字符串为 在野生动物园玩
  2. 第二轮找到词汇 在 和 在野，剩余未分词字符串为 野生动物园玩 和 生动物园玩
  3. 第三轮则对上面两个未分词字符串，应用相同的规则分词，得到词汇 野生动物园 和 生动
  4. 如此重复直到所有的未分词字符串为空。

经过上述步骤，我们得到两种分词可能

  1. 我们 / 在 / 野生动物园 / 玩
  2. 我们 / 在野 / 生动 / 物 / 园 / 玩

添加开始节点 <start> 和 结束节点 <end> 后，我们可以构建一个 有向无环图, 节点之间的边的权重为上一个节点对应的 log(概率的倒数)。

则得到类似如下的有向无环图：

DAG

通过求解最小路径的方法可以得到最短路径为 我们 / 在 / 野生动物园 / 玩

局限

因为基于词典，因此不具备新词发现的能力，同时也很难处理歧义问题。