构建中文分词器 - 反向最大匹配法

最大匹配每次寻找和确定最佳分词的时候按照最长(最大)匹配作为依据,从字符串的右边到左边(反向)依次寻找最大匹配。

解释

从解释的角度,可以理解为:判断待分词字符串的后 N 个字符构成的字符串是否在字典中,如果在,则匹配结束。如果没有匹配成功,则依次缩减 N 直到匹配成功。

示例

中国的首都是北京 为例, 假设 N 初始化为 4:

  1. 匹配 都是北京, 字典中无此词语,匹配失败,缩减 N 为 3
  2. 匹配 是北京, 字典中无此词语,匹配失败,缩减 N 为 2
  3. 匹配 北京, 字典中有此词语,匹配成功,结束匹配

继续匹配剩余未分词字符串 中国的首都是,直至字符串全部被分词。

局限

因为只考虑了能否构成词汇,完全没有考虑上下文,所以部分情况下会出现问题。
例如 中国的首都是北京 则会被分成 中国 / / / 都是 / 北京

优化方案

本算法耗时最大的部分在于扫描词典,因此可以通过特定的数据结构优化加速字典查找过程:

  1. 按照长度分别构建多个字典,能够一定程度的加速字典扫描的速度
  2. 使用 Trie-Tree 能够极大的加速查找过程

关联算法

最大正向匹配法 思想完全一样,用于解决 最大正向匹配法 的某些问题。比如:我们在野生动物园玩最大正向匹配法 中无法正确分词,但 反向最大匹配法 能够正确分词。

参考文献