)
分词算法----正向和逆向最大匹配算法(含Python代码实现)
文章目录
- 分词算法(Segmentation Method)
- 最大匹配算法(Maximum Matching)
- 需要的前提
- 正向最大匹配算法(Forwards Maximum Match，FMM)
- 逆向最大匹配算法(Reverse Maximum Match，RMM)
- 双向最大匹配算法
- 小结
分词算法(Segmentation Method)
在文本处理流程中，对语句进行分词（Segmentation）操作对于计算机认识并理解人类语言是基础且重要的。
对于中文来讲，不同于英文直接采用空格符进行分隔，并且中文词语内涵丰厚，语义丰富，所以只有采用合适的分词算法，才能准确迅速地向计算机表达原有的意思，提高工作效率。
最大匹配算法(Maximum Matching)
最大匹配算法是基于词表进行分词操作的，主要包括正向正向最大匹配算法、逆向最大匹配算法、双向最大匹配算法等。 其主要原理都是切分出单字串(词语)，然后和词库进行比对，如果对比成功就记录下来，从整句切除下来， 否则减少一个单字，继续比较，直到字符串全部切除完毕，即分词成功，数组中的所有词语即是分词结果。
以下详细介绍算法的主要思想及具体代码实现。
需要的前提
进行匹配算法的执行前，一定自己要设定一个字典库，通常作为测试即可。
这里我自己使用
字典库
ch/_dict = [‘我们’,‘经常’,‘有’,‘有意见’,‘意见’,‘分歧’]
测试语句
sentence = ‘我们经常有意见分歧’
最大匹配值
max/_match/_len = 5
正向最大匹配算法(Forwards Maximum Match，FMM)
算法主要思想
从字符串的正方向出发，先截取前5个字符，与词典库中的词语进行对比。若比对不成功，则截取前4个字符进行对比，依次类推，直到仅剩第一个字符，自动进行截取，此次截取结束；若对比成功，则将该词语记录下来，并从句子中截取下来。直至句子全部被拆分为词语，以数组进行存储。
算法思想示意图
具体代码实现
''' (分词算法)正向最大匹配算法 ''' if __name__ == '__main__': ch_dict = ['我们','经常','有','有意见','意见','分歧'] #中文的词典库，用于匹配句子中的词语 sentence = '我们经常有意见分歧' #例句，需要进行分词 segment_list = [] #存放分词后的分词词组 #例句不为空时，循环地进行分词操作 while len(sentence) >= 1: # 最大匹配单词的长度为5，当然实际意义从3开始即可，因为词典最大单词长度为3 max_match_len = 5 #当匹配单词长度大于1时，循环判断分词 while max_match_len > 1: #判断前 max_match_len 个字符是否存在于字典 if sentence[0:max_match_len] in ch_dict: segment_list.append(sentence[0:max_match_len]) #追加到分词词组中 sentence = sentence[max_match_len:len(sentence)] #将符合的词语从原例句中截取 break #退出循环，重新从max_match_len最长匹配数开始匹配截取 max_match_len -= 1 #max_match_len累减，开始匹配4个字符，3个字符，，， #只剩下一个汉字时，说明当前不再存在任何符合的词语，直接截取一个汉字作为词组 if max_match_len == 1: segment_list.append(sentence[0:1]) #追加单个汉字词语 sentence = sentence[1:len(sentence)] #截取例句 #输出存放分词的列表 print(segment_list) #输出进行分词后的例句 print('/'.join(segment_list)) #我们/经常/有意见/分歧运行结果
['我们', '经常', '有意见', '分歧'] 我们/经常/有意见/分歧 Process finished with exit code 0逆向最大匹配算法(Reverse Maximum Match，RMM)
算法主要思想
刚好与正向最大匹配算法相反，该算法旨在从句子末尾对句子进行分词操作，基本原理同正向最大匹配算法。
算法思想示意图
具体代码实现
''' (分词算法)后向最大匹配算法 ''' if __name__ == '__main__': ch_dict = ['我们','经常','有','有意见','意见','分歧'] #中文的词典库，用于匹配句子中的词语 sentence = '我们经常有意见分歧' #例句，需要进行分词 segment_list = [] #存放分词后的分词词组 #例句不为空时，循环地进行分词操作 while len(sentence) >= 1: # 最大匹配单词的长度为5，当然实际意义从3开始即可，因为词典最大单词长度为3 max_match_len = 5 #当匹配单词长度大于1时，循环判断分词 while max_match_len > 1: #判断前 max_match_len 个字符是否存在于字典 if sentence[-max_match_len:] in ch_dict: segment_list.append(sentence[-max_match_len:]) #追加到分词词组中 sentence = sentence[:-max_match_len] #将符合的词语从原例句中截取 break #退出循环，重新从max_match_len最长匹配数开始匹配截取 max_match_len -= 1 #max_match_len累减，开始匹配4个字符，3个字符，，， #只剩下一个汉字时，说明当前不再存在任何符合的词语，直接截取一个汉字作为词组 if max_match_len == 1: segment_list.append(sentence[-1:]) #追加单个汉字词语 sentence = sentence[:-1] #截取例句 # 输出进行分词后的例句 print('/'.join(segment_list)) #分歧/有意见/经常/我们 #对分词列表进行倒序 segment_list = segment_list[::-1] #再次输出进行分词后的例句 print('/'.join(segment_list)) # 我们/经常/有意见/分歧运行结果
分歧/有意见/经常/我们 我们/经常/有意见/分歧 Process finished with exit code 0双向最大匹配算法
算法的主要思想
双向最大匹配算法是同时采用正向最大匹配算法和逆向最大匹配算法，根据对比不同的执行结果，选择最优解。
有以下几种选择方案：
- 如果分词数量结果不同：选择数量较少的那个。
- 如果分词数量结果相同。
A. 分词结果相同，返回任意一个。
B. 分词结果不同，返回单个字数较少的一个。
C. 若单个字数也相同，任意返回一个。
小结
最大匹配算法在简单场景往往能够发挥出较好的分词效果，但其算法的时间复杂度较高，理解中文歧义问题不够准确，故存在一定的局限性，仅作为低级的分词算法使用。
《网络安全从零到精通全套学习大礼包》
96节从入门到精通的全套视频教程免费领取
如果你也想通过学网络安全技术去帮助就业和转行，我可以把我自己亲自录制的96节 从零基础到精通的视频教程以及配套学习资料无偿分享给你。
网络安全学习路线图
想要学习 网络安全，作为新手一定要先按照路线图学习，方向不对，努力白费。对于从来没有接触过网络安全的同学，我帮大家准备了从零基础到精通学习成长路线图以及学习规划。可以说是最科学最系统的学习路线，大家跟着这个路线图学习准没错。
配套实战项目/源码
所有视频教程所涉及的实战项目和项目源码
学习电子书籍
学习网络安全必看的书籍和文章的PDF，市面上网络安全书籍确实太多了，这些是我精选出来的
面试真题/经验
以上资料如何领取？
.csdnimg.cn/direct/92a6ab8e26034045b97ae8ac36b2a650.png)
