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

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

解释

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

示例

我们在野生动物园玩 为例, 假设 N 初始化为 4:

  1. 匹配 我们在野, 字典中无此词语,匹配失败,缩减 N 为 3
  2. 匹配 我们在, 字典中无此词语,匹配失败,缩减 N 为 2
  3. 匹配 我们, 字典中有此词语,匹配成功,结束匹配

继续匹配剩余未分词字符串 在野生动物园玩,直至字符串全部被分词。

局限

因为只考虑了能否构成词汇,完全没有考虑上下文,所以部分情况下会出现问题。
例如 我们在野生动物园玩 则会被分成 我们 / 在野 / 生动 / / /

优化方案

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

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

关联算法

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

参考文献