【python自然语言处理】规则分词（最大匹配法）_编写正向最大匹配法的python程序词典为dic.utf8,待分词文本为“北京市民办高中”

【python自然语言处理】规则分词（最大匹配法）

前言

基于规则的分词，主要是通过维护词典，在切分语句时，将语句的每个字符串与词表中的词逐一匹配，找到则切分，否则不切分。

一、正向最大匹配

算法解释

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

代码实现

class MM(object):
    def __init__(self, dic_path):
    #dic_path为字典的路径
        self.dictionary = set()
        self.maximum = 0
        #读取词典
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)
        print(self.dictionary)
    def cut(self, text):
        result = []
        length = len(text)
        index=0
        while length > 0:
            word = None
            for size in range(self.maximum, 0, -1):
                if length - size < 0:
                    continue
                piece = text[index:index+size]
                if piece in self.dictionary:
                    word = piece
                    result.append(word)
                    length -= size
                    index += size
                    break
            if word is None:
                length-=1
                result.append(text[index])
                index += 1
                
        return result

def main():
    text = "南京市长江大桥"
    tokenizer = MM('./data/imm_dic.utf8')
    print(tokenizer.cut(text))

main()
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

二、逆向最大匹配

算法解释

• 1，从被处理的文档的末端开始匹配扫描，每次取最末端的i个字符（i为字典中最长词数）作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字
• 2，继续匹配。相应的，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式存放。在实际处理时，先将文档进行倒排处理，生成逆序文档
• 3， 然后，根据逆序词典，对逆序文档用正向最大匹配法处理即可

代码实现

class IMM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        #读取词典
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)
        print(self.dictionary)
    def cut(self, text):
        result = []
        index = len(text)
        while index > 0:
            word = None
            for size in range(self.maximum, 0, -1):
                if index - size < 0:
                    continue
                piece = text[(index - size):index]
                if piece in self.dictionary:
                    word = piece
                    result.append(word)
                    index -= size
                    break
            if word is None:
                index -= 1
        return result[::-1]

def main():
    text = "南京市长江大桥"
    tokenizer = IMM('./data/imm_dic.utf8')
    print(tokenizer.cut(text))

main()
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

三、双向最大匹配

算法解释

• 将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较，然后按照最大匹配原则，选取词数切分最少的作为结果。

代码实现

class BMM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        self.dic_path=dic_path
        #读取词典
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)
    def cut(self,text):
        mm = MM(self.dic_path)
        imm = IMM(self.dic_path)

        mmMatch = mm.cut(text)
        immMatch = imm.cut(text)

#         #返回分词数较少者
        if (len(mmMatch) != len(immMatch)):
            if (len(mmMatch) < len(immMatch)):
                return mmMatch 
            else:
                return immMatch
        else:#若分词数量相同，进一步判断
            mmsingle = 0
            immsingle = 0
            isEqual = True #用以标志结果是否相同
            for i in range(len(mmMatch)):
                if(mmMatch[i] != immMatch[i]):
                    isEqual = False
                #统计单字数
                if(len(mmMatch[i])==1):
                    mmsingle += 1
                if(len(immMatch[i])==1):
                    immsingle += 1
            if(isEqual):
                return mmMatch
            if(mmsingle < immsingle):
                return mmMatch
            else:
                return immMatch

def main():
    text = "南京市长江大桥"
    tokenizer = BMM('./data/imm_dic.utf8')
    print(tokenizer.cut(text))

main()
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

总结

以上主要总结了三种规则匹配方法，正向最大匹配法，逆向最大匹配法，和双向最大匹配算法，并给出了相应的代码实现，以上代码都可以直接运行出结果。