中文分词算法：逆向最大匹配法

分词算法：逆向最大匹配法"/>

中文分词算法：逆向最大匹配法

1、词典

./data/rmm_dic.utf8

南京市
南京市长
长江大桥
人民解放军
大桥

2、RMM算法

#逆向最大匹配
class RMM(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:continueself.dictionary.add(line)if len(line) > self.maximum:self.maximum = len(line)def cut(self, text):result = []index = len(text)while index > 0:print('index='+str(index))word = None# 语法 range(start, stop[, step])for size in range(self.maximum, 0, -1):print('size='+str(size))# 切片开始位置：index - sizeif index - size < 0:continue#逆向切片，提取当前可能存在的最长词piece = text[(index - size):index]print('piece='+str(piece))#切分出一个词if piece in self.dictionary:word = pieceresult.append(word)#切分词后，剩下的字符串长度index -= sizebreakif word is None:index -= 1return result[::-1]def main():text = "南京市长江大桥"tokenizer = RMM('./data/rmm_dic.utf8')print(tokenizer.cut(text))main()

执行结果

index=7
size=5
piece=市长江大桥
size=4
piece=长江大桥
index=3
size=5
size=4
size=3
piece=南京市
['南京市', '长江大桥']

程序解析：
1、初始值
    待切分字符串长度index =7
    最大词典长度maximum=5
2、第1次大循环while
 index =7
 （1）第1次for循环
   size=5
   切分出可能的最长词（5）=市长江大桥，非词，进入下次循环
 （2）第2次for循环
   size=4
   切分出可能的最长词=长江大桥，命中
   剩下待切分长度index=3
   跳出for循环
3、第2次大循环while
 index =3
 （1）第1次for循环
   size=5，大于待切分长度3
 （2）第2次for循环
   size=4，大于待切分长度3
 （3）第3次for循环
   size=3，等于待切分长度3
   切分出可能的最长词=南京市，命中
   剩下待切分长度index=0
   跳出for循环
4、第3次大循环while
 不满足index > 0，退出