【Python】实现正向(逆向)最大匹配法（中文分词，NLP，编译原理）_编程实现基于字典分词算法-逆向最大匹配算法。

正向最大匹配法（Maximum Match Method）

Step 1 假定分词词典中的最长词有i个汉字字符，则用被处理的当前字串中的前i个字作为匹配字段，查找字典。
Step 2 若字典中存在这样一个i字词，则匹配成功；否则，失败，将匹配字段中的最后一个字符去掉， 对剩下字串进行匹配。
Step 3 如此进行下去，直到匹配成功，即切分出一个词或剩余字串长度为0。
不停的匹配，直到文档被扫描完为止。

逆向最大匹配法（Reverse Maximum Match Method）

原理与MM类似
Step 1 假定分词词典中的最长词有i个汉字字符，从文档末端开始匹配扫描，每次取最末端的i个字作为匹配字段，查找字典。
Step 2 若字典中存在这样一个i字词，则匹配成功；否则，失败，将匹配字段中的最前面一个字符去掉， 对剩下字串进行匹配。
Step 3 如此进行下去，直到匹配成功，即切分出一个词或剩余字串长度为0。
不停的匹配，直到文档被扫描完为止。

任务

给定字典，[‘研究’，’研究生’, ’生命’，’命’，’的’，‘起源’]
实现正向最大匹配法或逆向最大匹配法，以实现对“研究生命的起源”这个串的分词，对比两种方法在切分“研究生命的起源”的差异

实现代码

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 23 22:38:30 2020

@author: 
"""
dic_list=['研究', '命', '的', '起源', '研究生', '生命'] #分词字典列表
sentence="研究生命的起源" #待分词的句子
ans_forward=[]  #存放正向匹配的结果
ans_reverse=[]  #存放逆向匹配的结果，相当于栈
max_length=3    #分词字典中最大长度字符串的长度
"""
要是分词字典列表中最大长度字符串的长度一眼看不出来，可采用下一行的形式
max_length=len(sorted(dic_list, key=lambda x: len(x))[-1])
"""

#1、正向最大匹配
len_row=len(sentence)  #len_orw为当前为划分句子的长度
while len_row>0:       #当前待划分句子长度为0时，结束划分
    divide = sentence[0:max_length]    #从前向后截取长度为max_length的字符串
    while divide not in dic_list:      #当前截取的字符串不在分词字典中，则进循环
        if len(divide)==1:             #当前截取的字符串长度为1时，说明分词字典无匹配项
            break                      #直接保留当前的一个字
        divide=divide[0:len(divide)-1] #当前截取的字符串长度减一
    ans_forward.append(divide)         #记录下当前截取的字符串
    sentence = sentence[len(divide):]  #截取未分词的句子
    len_row = len(sentence)            #记录未分词的句子的长度
print("\'正向最大匹配\'的分词结果为：",ans_forward)

#2、逆向最大匹配
sentence="研究生命的起源"
len_row=len(sentence)
while len_row>0 :
    divide = sentence[-max_length:]
    while divide not in dic_list:
        if len(divide)==1:
            break
        divide=divide[1:]   #注意这里缩短截取字符串是缩短前部分，保留后部分
    ans_reverse.append(divide)
    sentence = sentence[0:len(sentence)-len(divide)]
    len_row = len(sentence)
print("\'逆向最大匹配\'的分词结果为：",ans_reverse[::-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

输出结果

其他资料

1、“直接扫描法”等其他词法分析知识参考资料

2、numpy等其他python相关知识参考资料（莫烦python）

3、中文分词–最大正向与逆向匹配算法python实现（本博客参考链接）

4、python如何用一行代码输出一个全是字符串的列表中，最长的那个字符串