中文分词——最大匹配法

在英文中，单词之间有空格做天然的分割，分词变得非常简单。但是在中文中就没有那么容易了，所以分词是自然语言处理的基础，分词不好，后面很难去做进一步分析。尽管现在NLP中有很多算法以字来切分，比如bert，中文分词仍然是NLP中很重要、很基础的一块工作。目前已经有许多开源的中文分词工具，比如jieba，hanlp，pkuseg。这些分词工具都能很好地处理好大部分中文语句的分词工作，所以大部分时候我们不需要重复造轮子了。对于一些专业的垂直领域，有些专业常用语可以用增加自定义词典的方式来提高上述分词工具的准确性。

但是分词的常用方法还是需要了解的，可以讲中文分词方法简单归纳为：

• 基于词表的方法
• 基于统计的方法
• 基于序列标记的方法

今天我们就来谈谈基于词典的分词方法——最大匹配法（Maximum Matching）

最大匹配法

基于词典的分词方法最为简单，根据起始匹配位置不同可以分为：

• 前向最大匹配算法 (FMM，Forward Maximum Matching)
• 后向最大匹配算法（BMM, Backward Maximum Matching）
• 双向最大匹配算法

前向最大匹配算法

前向最大匹配算法，顾名思义，前向即从左往右取词，取词最大长度为词典中长词的长度，每次右边减一个字，直到词典中存在或剩下1个单字。

假设我们有词典为

words_dict = ['我','我们', '在','中', '中国', '是', '出生', '中国人', '堂堂正正', '的']
sentence = '我出生在中国我是堂堂正正的中国人'
max_len = 4  # 词典中最大词长

第一轮：

第一次："我出生在"，查找字典，无

第二次："我出生"，查找字典，无

第三次："我出"，查找字典，无

第四次："我"，剩下一个字，独立成词

第一轮结束，输出第1个词为“我”，去除第1个词后，开始第2轮

第二轮：

第一次："出生在中"，查找字典，无

第二次："出生在"，查找字典，无

第三次："出生"，查找字典，有

第二轮结束，输出第2个词为“出生”，去除第2个词后，开始下一轮

之后继续往后匹配，直到匹配完整个句子。

最终分词结果为：

['我', '出生', '在', '中国', '我', '是', '堂堂正正', '的', '中国人']

FMM算法python代码如下：

def FMM(user_dict, sentence):
    """
    正向最大匹配（FMM）
    :param user_dict: 词典
    :param sentence: 句子
    """
    # 词典中最长词长度
    segment_words = []
    max_len = max([len(item) for item in user_dict])
    start = 0
    while start != len(sentence):
        index = start+max_len
        if index>len(sentence):
            index = len(sentence)
        for i in range(max_len):
            if (sentence[start:index] in user_dict) or (len(sentence[start:index])==1):
                segment_words.append(sentence[start:index])
                start = index
                break
            index += -1
    return segment_words

测试如下：

user_dict = ['我','我们', '在','中', '中国', '是', '出生', '中国人', '堂堂正正', '的']
sentence = '我出生在中国我是堂堂正正的中国人'
segs = FMM(user_dict, sentence)
print(segs)

输出如下：

['我', '出生', '在', '中国', '我', '是', '堂堂正正', '的', '中国人']

后向最大匹配算法

后向算法，即从右往左匹配，其他逻辑和前向算法相同。

Python实现方法如下：

def BMM(user_dict, sentence):
    """
    反向最大匹配（BMM）
    :param user_dict:词典
    :param sentence:句子
    """
    # 词典中最长词长度
    max_len = max([len(item) for item in user_dict])
    result = []
    start = len(sentence)
    while start != 0:
        index = start - max_len
        if index < 0:
            index = 0
        for i in range(max_len):
            if (sentence[index:start] in user_dict) or (len(sentence[start:index])==1):
                result.append(sentence[index:start])
                start = index
                break
            index += 1
    return result[::-1]

测试如下：

user_dict = ['我','我们', '在','中', '中国', '是', '出生', '中国人', '堂堂正正', '的']
sentence = '我出生在中国我是堂堂正正的中国人'
segs = BMM(user_dict, sentence)

双向最大匹配法

双向最大匹配法：FMM和BMM两种算法都分词一遍，然后根据大颗粒度词越多越好，非词典词和单字词越少越好的原则，选取其中一种分词结果输出。

选择标准：

1. 首先看两种方法结果的分词数，分词数越少越好；
2. 分词数相同的情况下，看单个词的数量，越少越好；