双向最大匹配算法 BMM

中文分词算法分两大方向：一是机械分词算法, 一是基于统计的分词算法。本篇文章主要介绍机械分词算法中最基础的算法: 最大匹配算法(Maximum Matching， 一下简称MM算法)。 MM算法有三种: 正向最大匹配算法（ forwards maximum match algorithm）， 逆向最大匹配算法（ reverse directional algorithm）以及双向最大匹配算法（Bi-directional Maximum Match）。双向最大匹配算法是取前面两种分词算法切分出来词, 然后根据一定的策略筛出切分效果最好的作为最终的切分结果。

前言：最近需要根据某个既定的信息在已有的文本库中进行词条匹配并返回匹配的结果，因此BMM算法是该领域中相对来说更为高效和简便的。本文主要介绍的是BMM算法的基本使用步骤。

1.加载已有的文本库

第一步的主要目的是通过给定的dict_path目录路径（一般来说是txt格式文件的路径）参数生成文本库的列表（即字典）并返回列表中文本的最大长度（用于后续算法），需要注意的是打开文件的时候需要指定字符集的参数，否则可能会出现报错的情况（一般来说是因为文本库中可能存在一些无法被正常解析的符号）。

# 加载词典
def load_words(self, dict_path):
    words = list()
    max_len = 0
    for line in open(dict_path,encoding='utf-8'):   #需要指定打开文件的字符集
        wd = line.strip()	#去除本行内容的前向和后向空格
        if not wd:	#如果本行内容处理后为空那么继续处理下一行数据
            continue
        if len(wd) > max_len:	#记录下文本库中最大的单词长度
            max_len = len(wd)
        words.append(wd)	#将本行内容存储到集合中
    return words, max_len
1
2
3
4
5
6
7
8
9
10
11
12

2.正向最大匹配算法

正向的方向定义是从字符串下标0到字符串末尾位置，取出字串与字典进行匹配
首先需要进行的初始化工作为：初始化最大匹配长度（已经在上述过程中得到为self.max_worldlen），初始化当前位置index为0，处理结果为cutList为空，正式开始匹配：

1. 首先确保当前index并未超过该字符串的最大长度，在此基础上不断前进
2. 对于每一个index而言都需要在max_worldlen大小的滑窗内进行匹配，滑窗从右向左依次减小直到0（不包括），步长为-1
3. 对于每一个大小的滑窗所包围的字符串而言，如果其在字典内那么就将其加入到cutList中并将matched置为True同时终止滑窗从右向左依次减小。但是如果没有匹配上那么就按照字符进行切分，将当前index所表征的单个字符加入到cutList中，同时将i置为1。
4. 将index进行位移，如果匹配到了那么就从匹配到的字符串的下一个位置开始，如果没有匹配到就从上一个位置的下一个位置开始继续匹配。

用一个给定的例子来简单讲解上述的过程：假设此时字典为['acf','bc','ef','g']那么max_wordlen为3即滑窗的最大长度为3，对于给定的字符串'abcdefg'那么首先index指定字符串的第一个位置即0，滑窗的初始长度为3即此时滑窗所包围的字符串为'abc'并不在字典中，那么滑窗自右向左依次减小即下一个所包围的字符串为'ab'也不在该字典中同理'a'也不在该字典中，那么此时matched仍为false也就意味着对于index=0而言无法找到匹配的字串，因此将此时index所表征的单个字符'a'加入到字典中同时index+=i意味着此时的字串从'bcdefg'继续开始匹配，此时第一个被滑窗所包围的字串为'bcd'不在字典中，下一个'bc'在字典中于是滑窗不继续减小直接break并将'bc'加入到cutList中同时i为2意味着此时的字串从'defg'开始匹配，同理可以得出类似的结论。最后得到的cutList应该为['a','bc','d','ef','g']
下面是正向最大匹配算法的代码：

# 前向最大匹配算法
def max_forward_cut(self, sent):
    # 1.从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
    # 2.查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
    cutlist = []
    index = 0
    while index < len(sent):
        matched = False
        for i in range(self.max_wordlen, 0, -1):
            cand_word = sent[index: index + i]
            if cand_word in self.word_dict:
                cutlist.append(cand_word)
                matched = True
                break

        # 如果没有匹配上，则按字符切分
        if not matched:
            i = 1
            cutlist.append(sent[index])
        index += i
    return cutlist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.后向最大匹配算法

后向的方向定义是从字符串末尾的位置到字符串下标为0的位置，取出字串与字典进行匹配
首先需要进行的初始化工作为：初始化最大匹配长度（已经在上述过程中得到为self.max_worldlen），初始化当前位置index为len(sent)即字符串的末尾位置，处理结果cutList为空，正式开始匹配：

1. 首先确保当前index大于0，在此基础上不断后退
2. 对于每一个index而言都需要在max_worldlen大小的滑窗内进行匹配，滑窗从左向右依次减小直到0（不包括），步长为-1
3. 对于每一个大小的滑窗所包围的字符串而言，如果其在字典内那么就将其加入到cutList中并将matched置为True同时终止滑窗从左向右依次减小。但是如果没有匹配上那么就按照字符进行切分，将当前index-1所表征的单个字符加入到cutList中，同时将i置为1。
4. 将index进行位移，如果匹配到了那么就从匹配到的字符串的前一个位置开始，如果没有匹配到就从上一个位置的前一个位置开始继续匹配。

例子与最大前向匹配异曲同工，就不赘述了，直接看代码即可。需要注意的是这里采用temp+1其实主要是为了让滑窗的大小不降为1个字符，因为1个字符的时候不论是否发生匹配都会将该字符加入到cutList中，还有一种解决方案是在range的时候终止位置stop从0改为1，这种效果可能更好，因为可以避免滑窗大小比词库中最长的单词更长的时候不可能发生匹配的情况发生。

# 后向最大匹配算法
def max_backward_cut(self, sent):
    # 1.从右向左取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
    # 2.查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
    cutlist = []
    index = len(sent)
    max_wordlen = 5
    while index > 0:
        matched = False
        for i in range(self.max_wordlen, 0, -1):
            tmp = (i + 1)
            cand_word = sent[index - tmp: index]
            # 如果匹配上，则将字典中的字符加入到切分字符中
            if cand_word in self.word_dict:
                cutlist.append(cand_word)
                matched = True
                break
        # 如果没有匹配上，则按字符切分
        if not matched:
            tmp = 1
            cutlist.append(sent[index - 1])

        index -= tmp

    return cutlist[::-1]
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

4.双向最大匹配算法

双向最大匹配算法的原理就是将正向最大匹配算法和逆向最大匹配算法进行比较，从而选择正确的分词方式，一般来说都已经有固定的比较原则了，基本上采用的启发式规则如下所示：

1. 比较两种匹配算法的分词数量
2. 如果分词数量结果不同：选择数量较少的那个
3. 如果分词数量结果相同，继续比较
   1. 分词结果相同，返回任意一个
      1. 分词结果不同，返回单字符数较少的一个
      2. 若单字数也相同，任意返回一个

下面是双向最大匹配算法的代码：

# 双向最大向前匹配
def max_biward_cut(self, sent):
    # 双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。
    # 启发式规则：
    # 1.如果正反向分词结果词数不同，则取分词数量较少的那个。
    # 2.如果分词结果词数相同 a.分词结果相同，就说明没有歧义，可返回任意一个。 b.分词结果不同，返回其中单字较少的那个。
    forward_cutlist = self.max_forward_cut(sent)
    backward_cutlist = self.max_backward_cut(sent)
    count_forward = len(forward_cutlist)
    count_backward = len(backward_cutlist)

    def compute_single(word_list):
        num = 0
        for word in word_list:
            if len(word) == 1:
                num += 1
        return num

    if count_forward == count_backward:
        if compute_single(forward_cutlist) > compute_single(backward_cutlist):
            return backward_cutlist
        else:
            return forward_cutlist

    elif count_backward > count_forward:
        return forward_cutlist

    else:
        return backward_cutlist
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

5.测试结果和完整的代码

这里采用的单词库就是前向最大匹配算法中的例子

完整代码如下所示：

class CutWords:
    def __init__(self):
        dict_path = './test.txt'
        self.word_dict, self.max_wordlen = self.load_words(dict_path)

    # 加载词典
    def load_words(self, dict_path):
        words = list()
        max_len = 0
        for line in open(dict_path,encoding='utf-8'):   #需要指定打开文件的字符集
            wd = line.strip()
            if not wd:
                continue
            if len(wd) > max_len:
                max_len = len(wd)
            words.append(wd)
        return words, max_len

    # 最大向前匹配
    def max_forward_cut(self, sent):
        # 1.从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
        # 2.查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
        cutlist = []
        index = 0
        while index < len(sent):
            matched = False
            for i in range(self.max_wordlen, 0, -1):
                cand_word = sent[index: index + i]
                if cand_word in self.word_dict:
                    cutlist.append(cand_word)
                    matched = True
                    break

            # 如果没有匹配上，则按字符切分
            if not matched:
                i = 1
                cutlist.append(sent[index])
            index += i
        print('前向最大匹配结果')
        print(cutlist)
        return cutlist

    # 最大向后匹配
    def max_backward_cut(self, sent):
        # 1.从右向左取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
        # 2.查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
        cutlist = []
        index = len(sent)
        max_wordlen = 5
        while index > 0:
            matched = False
            for i in range(self.max_wordlen, 0, -1):
                tmp = (i + 1)
                cand_word = sent[index - tmp: index]
                # 如果匹配上，则将字典中的字符加入到切分字符中
                if cand_word in self.word_dict:
                    cutlist.append(cand_word)
                    matched = True
                    break
            # 如果没有匹配上，则按字符切分
            if not matched:
                tmp = 1
                cutlist.append(sent[index - 1])

            index -= tmp
        print('后向最大匹配结果')
        print(cutlist)
        return cutlist[::-1]

    # 双向最大向前匹配
    def max_biward_cut(self, sent):
        # 双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。
        # 启发式规则：
        # 1.如果正反向分词结果词数不同，则取分词数量较少的那个。
        # 2.如果分词结果词数相同 a.分词结果相同，就说明没有歧义，可返回任意一个。 b.分词结果不同，返回其中单字较少的那个。
        forward_cutlist = self.max_forward_cut(sent)
        backward_cutlist = self.max_backward_cut(sent)
        count_forward = len(forward_cutlist)
        count_backward = len(backward_cutlist)

        def compute_single(word_list):
            num = 0
            for word in word_list:
                if len(word) == 1:
                    num += 1
            return num

        if count_forward == count_backward:
            if compute_single(forward_cutlist) > compute_single(backward_cutlist):
                return backward_cutlist
            else:
                return forward_cutlist

        elif count_backward > count_forward:
            return forward_cutlist

        else:
            return backward_cutlist

if __name__ == '__main__':
    handler = CutWords()
    while 1:
        question = input('input a string:')
        data = handler.max_biward_cut(question)
        print(data)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105