自然语言处理之中文分词技术与算法_自然语言mm算法

1 正向最大匹配法

1.1 正向最大匹配（Maximum Match Method, MM法）的基本思想：
假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理。如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。

其算法描述如下：
1）从左向右取待切分汉语句的m个字符作为匹配字段，m为机器词典中最长词条的字符数。
2）查找机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，重复以上过程，直到切分出所有词为止。

1.2 代码实现：

# !/usr/bin/python3
# -*- coding:utf-8 -*-
# @Time : 2019/10/13 11:48
# @Author : Huang Shiquan
# @Email : 1357626165@qq.com
# @File : MM.py
# @Project : Unit3_SplitWords
# @algorithm : 正向最大匹配法
class MM(object):
    def __init__(self):
        self.window_size = 3

    def cut(self,text):
        result = []
        index  = 0
        text_length = len(text)
        dic = ['研究','研究生','生命','命','的','起源']
        piece = ''
        while text_length > index:
            for size in range(self.window_size+index, index, -1):
                piece = text[index:size]
                if piece in dic:
                    index = size - 1
                    break
            index = index + 1
            result.append(piece)
        return result

if __name__ == '__main__':
    text = '研究生命的起源'
    tokenizer = MM()
    print(tokenizer.cut(text))
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

1.3 程序运行结果为：

2 逆向最大匹配法

2.1 逆向最大匹配（Reverse Maximum Match Method, RMM法）的基本思想:
与MM法相同，不同的是分词切分的方向与MM法相反。逆向最大匹配法从被处理文档的末端开始匹配扫描，每次取最末端的i个字符（i为词典中最长词数）作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。相应地，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式存放。在实际处理时，先将文档进行倒排处理，生成逆序文档。然后，根据逆序词典，对逆序文档用正向最大匹配法处理即可。

2.2 代码实现：

# !/usr/bin/python3
# -*- coding:utf-8 -*-
# @Time : 2019/10/13 16:56
# @Author : Huang Shiquan
# @Email : 1357626165@qq.com
# @File : RMM.py
# @Project : Unit3_SplitWords
# @algorithm : 逆向最大匹配法
class RMM(object):
    def __init__(self):
        self.window_size = 3

    def cut(self,text):
        result = []
        index = len(text)
        dic = ['研究','研究生','生命','命','的', '起源']
        piece = ''
        while index > 0:
            for size in range(index-self.window_size, index):
                piece = text[size:index]
                if piece in dic:
                    index = size + 1
                    break
            index = index - 1
            result.append(piece)
        result.reverse()
        return result

if __name__ == '__main__':
    text = '研究生命的起源'
    tokenizer = RMM()
    print(tokenizer.cut(text))
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

2.3 程序运行结果为：

3 双向最大匹配法

3.1 双向最大匹配法（Bi-directction Matching method）的基本思想：
双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较，然后按照最大匹配原则，选取词数切分最少的作为结果。

3.2 代码实现：

# !/usr/bin/python3
# -*- coding:utf-8 -*-
# @Time : 2019/10/13 17:28
# @Author : Huang Shiquan
# @Email : 1357626165@qq.com
# @File : BDMM.py
# @Project : Unit3_SplitWords
# @algorithm : 双向最大匹配法
class BDMM(object):
    def __init__(self):
        self.window_size = 3

    # 正向最大匹配法切分
    def cut_MM(self,text):
        result = []
        index = 0
        text_length = len(text)
        dic = ['研究', '研究生', '生命', '命', '的', '起源']
        piece = ''
        while text_length > index:
            for size in range(self.window_size + index, index, -1):
                piece = text[index:size]
                if piece in dic:
                    index = size - 1
                    break
            index = index + 1
            result.append(piece)
        return result

    # 逆向最大匹配法切分
    def cut_RMM(self,text):
        result = []
        index = len(text)
        dic = ['研究', '研究生', '生命', '命', '的', '起源']
        piece = ''
        while index > 0:
            for size in range(index - self.window_size, index):
                piece = text[size:index]
                if piece in dic:
                    index = size + 1
                    break
            index = index - 1
            result.append(piece)
        result.reverse()
        return result

    # 单字较少的list
    def min_single(self, result1, result2):
        count1 = 0
        count2 = 0
        for res1 in result1:
            if(len(res1) == 1):
                count1 = count1 + 1
        for res2 in result2:
            if(len(res2) == 1):
                count2 = count2 + 1
        return result1 if count1 < count2 else result2

    # 双向最大匹配法切分
    def cut_BDMM(self,text):
        """
        双向最大匹配的规则：
        (1) 如果正反向分词结果次数不同，则取分词数量较少的那个
        (2) 如果分词结果次数相同：
         1) 分词结果相同，就说明没有歧义，可返回任意一个；
         2) 分词结果不同，返回单字较少的那个。
        """
        result_MM = self.cut_MM(text)
        result_RMM = self.cut_RMM(text)
        if len(result_MM) != len(result_RMM):
            return result_MM if len(result_MM) < len(result_RMM) else result_RMM
        elif result_RMM == result_MM:
            return result_MM
        else:
            return self.min_single(result_MM, result_RMM)

if __name__ == '__main__':
    text = '研究生命的起源'
    tokenizer = BDMM()
    print(tokenizer.cut_BDMM(text))
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

3.3 程序运行结果为：

*【注】如果你觉得此文不错，可以考虑打赏我哦，您的打赏将是我更新的最大动力，非常感谢。（打赏也是基于自愿原则的哦(￣︶￣)）