分词算法----正向和逆向最大匹配算法(含Python代码实现)_正向最大匹配算法

---

分词算法(Segmentation Method)

在文本处理流程中，对语句进行分词（Segmentation）操作对于计算机认识并理解人类语言是基础且重要的。

对于中文来讲，不同于英文直接采用空格符进行分隔，并且中文词语内涵丰厚，语义丰富，所以只有采用合适的分词算法，才能准确迅速地向计算机表达原有的意思，提高工作效率。

---

最大匹配算法(Maximum Matching)

最大匹配算法是基于词表进行分词操作的，主要包括正向正向最大匹配算法、逆向最大匹配算法、双向最大匹配算法等。 其主要原理都是切分出单字串(词语)，然后和词库进行比对，如果对比成功就记录下来，从整句切除下来， 否则减少一个单字，继续比较，直到字符串全部切除完毕，即分词成功，数组中的所有词语即是分词结果。

以下详细介绍算法的主要思想及具体代码实现。

需要的前提

进行匹配算法的执行前，一定自己要设定一个字典库，通常作为测试即可。
这里我自己使用
字典库

ch_dict = [‘我们’,‘经常’,‘有’,‘有意见’,‘意见’,‘分歧’]

测试语句

sentence = ‘我们经常有意见分歧’

最大匹配值

max_match_len = 5

正向最大匹配算法(Forwards Maximum Match，FMM)

算法主要思想

从字符串的正方向出发，先截取前5个字符，与词典库中的词语进行对比。若比对不成功，则截取前4个字符进行对比，依次类推，直到仅剩第一个字符，自动进行截取，此次截取结束；若对比成功，则将该词语记录下来，并从句子中截取下来。直至句子全部被拆分为词语，以数组进行存储。

算法思想示意图

具体代码实现

'''
(分词算法)正向最大匹配算法
'''
if __name__ == '__main__':

    ch_dict = ['我们','经常','有','有意见','意见','分歧']       #中文的词典库，用于匹配句子中的词语
    sentence = '我们经常有意见分歧'          #例句，需要进行分词
    segment_list = []                      #存放分词后的分词词组

    #例句不为空时，循环地进行分词操作
    while len(sentence) >= 1:
        # 最大匹配单词的长度为5，当然实际意义从3开始即可，因为词典最大单词长度为3
        max_match_len = 5
        #当匹配单词长度大于1时，循环判断分词
        while max_match_len > 1:

            #判断前 max_match_len 个字符是否存在于字典
            if sentence[0:max_match_len] in ch_dict:
                segment_list.append(sentence[0:max_match_len])              #追加到分词词组中
                sentence = sentence[max_match_len:len(sentence)]            #将符合的词语从原例句中截取
                break                   #退出循环，重新从max_match_len最长匹配数开始匹配截取

            max_match_len -= 1          #max_match_len累减，开始匹配4个字符，3个字符，，，

        #只剩下一个汉字时，说明当前不再存在任何符合的词语，直接截取一个汉字作为词组
        if max_match_len == 1:
            segment_list.append(sentence[0:1])          #追加单个汉字词语
            sentence = sentence[1:len(sentence)]        #截取例句

	#输出存放分词的列表
    print(segment_list)
    #输出进行分词后的例句
    print('/'.join(segment_list))               #我们/经常/有意见/分歧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

运行结果

['我们', '经常', '有意见', '分歧']
我们/经常/有意见/分歧

Process finished with exit code 0
1
2
3
4

逆向最大匹配算法(Reverse Maximum Match，RMM)

算法主要思想

刚好与正向最大匹配算法相反，该算法旨在从句子末尾对句子进行分词操作，基本原理同正向最大匹配算法。

算法思想示意图

具体代码实现

'''
(分词算法)后向最大匹配算法
'''

if __name__ == '__main__':

    ch_dict = ['我们','经常','有','有意见','意见','分歧']       #中文的词典库，用于匹配句子中的词语
    sentence = '我们经常有意见分歧'          #例句，需要进行分词
    segment_list = []                      #存放分词后的分词词组

    #例句不为空时，循环地进行分词操作
    while len(sentence) >= 1:
        # 最大匹配单词的长度为5，当然实际意义从3开始即可，因为词典最大单词长度为3
        max_match_len = 5
        #当匹配单词长度大于1时，循环判断分词
        while max_match_len > 1:

            #判断前 max_match_len 个字符是否存在于字典
            if sentence[-max_match_len:] in ch_dict:
                segment_list.append(sentence[-max_match_len:])              #追加到分词词组中
                sentence = sentence[:-max_match_len]            #将符合的词语从原例句中截取
                break                   #退出循环，重新从max_match_len最长匹配数开始匹配截取

            max_match_len -= 1          #max_match_len累减，开始匹配4个字符，3个字符，，，

        #只剩下一个汉字时，说明当前不再存在任何符合的词语，直接截取一个汉字作为词组
        if max_match_len == 1:
            segment_list.append(sentence[-1:])          #追加单个汉字词语
            sentence = sentence[:-1]                    #截取例句

    # 输出进行分词后的例句
    print('/'.join(segment_list))               #分歧/有意见/经常/我们

    #对分词列表进行倒序
    segment_list = segment_list[::-1]
    #再次输出进行分词后的例句
    print('/'.join(segment_list))               # 我们/经常/有意见/分歧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

运行结果

分歧/有意见/经常/我们
我们/经常/有意见/分歧

Process finished with exit code 0
1
2
3
4

双向最大匹配算法

算法的主要思想

双向最大匹配算法是同时采用正向最大匹配算法和逆向最大匹配算法，根据对比不同的执行结果，选择最优解。

有以下几种选择方案：

1. 如果分词数量结果不同：选择数量较少的那个。
2. 如果分词数量结果相同。
   A. 分词结果相同，返回任意一个。
   B. 分词结果不同，返回单个字数较少的一个。
   C. 若单个字数也相同，任意返回一个。

小结

最大匹配算法在简单场景往往能够发挥出较好的分词效果，但其算法的时间复杂度较高，理解中文歧义问题不够准确，故存在一定的局限性，仅作为低级的分词算法使用。