基于词典的正向/逆向最大匹配(附代码)

会员服务 ·

基于词典的正向/逆向最大匹配(附代码)

2020 年 10 月 26 日 AINLP

正向最大匹配和逆向最大匹配步骤类似，只是方向不同，我以正向匹配为例，先用一句话去总结它：

在做整个正向成词的过程中，我们做了两个步骤，首先按照字典最大长度进行对原始文本进行切分，然后逐渐去掉右边一个单字，去查看剩余文本在字典是否存在，依次迭代。

上面这句话只看不太好理解，我来个简单的例子，如下：

我要被切分的句子是这样的："今天天气真不错啊"

我的字典是这样的：[今天,天天,天气,真不错,不错,啊,哈哈哈哈哈]

对于字典这一块，最粗糙的就是存成列表，优化一点可以存成字典树，这里简化一点，我们存成列表。

我字典的最大长度是 “哈哈哈哈哈”，为5.

所以我第一次正向匹配就是：

今天天气真 # 取原始文本前五个单词，查看是否存在于字典，否，删除底部

今天天气 # 查看是否存在于字典，否，删除底部

今天天 # 查看是否存在于字典，否，删除底部

今天 #匹配到字典中的“天气”这个词

第二次正向匹配是这样的：

天气真不错啊 # 因为”今天“已经被匹配到了，所以我们不在考虑，取剩余文本的前五个单词，查看是否存在于字典，否，删除底部

天气真不错 #查看是否存在于字典，否，删除底部

天气真不 #查看是否存在于字典，否，删除底部

天气真 #查看是否存在于字典，否，删除底部

天气 #匹配到字典中的“天气“这个单词

第三次正向匹配的过程：

真不错啊 # 剩余文本不够5个，我们取小，取4个，查看是否存在于字典，否，删除底部

真不错 # 匹配到”真不错“ 这个单词

第四次正向匹配的过程：

啊 # 字典中没有与之相关的单词，由于长度已经为1，直接单独成词就可以

在做整个正向成词的过程中，我们做了两个步骤，首先按照字典最大长度进行对原始文本进行切分（需要比对最大长度和文本的长度，如果文本长度不够的话，就取文本长度，总之取小。比如第三次正向匹配”真不错啊“这剩余的四个字就不够5个），然后逐渐去掉右边一个单字，去查看剩余文本在字典是否存在，依次迭代。

其实逆向匹配是很类似的过程，只不过方向变了，需要注意的是我们始终删除的是底部单词：

第一次逆向匹配：

气真不错啊 # 查看是否存在于字典，否，删除底部

真不错啊 # 查看是否存在于字典，否，删除底部

不错啊 # 查看是否存在于字典，否，删除底部

错啊 # 查看是否存在于字典，否，删除底部

啊 # 字典中没有与之相关的单词，由于长度已经为1，直接单独成词就可以

......

双向最大匹配算法就是两种方法都切一遍，从中选择一种比较好的，标准就是：大颗粒度词越多越好，非词典词和单字词越少越好.

对于代码的实现，我记得是好久之前从网上down下来的，具体来源忘了，不过都大同小异，自己写也没啥问题。

我在这里啰嗦的讲一下大致思路，如果您觉得比较简单，或者只想看代码，跳过就可以：

基本思路是这样的，我有一个存储我词典的列表，以词典中最大长度为基线顺序对原始文本进行切分，迭代查看当前切分词是否在词典，在就算一个词，不在的话，当前词长度减一，就是往前缩小一个词，继续进行上述活动。直至长度为1，是最后的一个迭代条件。

在写代码的时候，我自己觉得从两个方面来掌握，一个是从小方面，怎么讲，就是比如说我的字典最大的长度是5个单词，我在5个单词迭代的去找有没有在字典的中的词，这是一个while循环。

还有一个方面是大的方面，就是我现在5个单词迭代完了，比如找到了一个长度为2的在字典中的词（需要注意的是如果没有在字典中，那么长度就是1的单字就可以加进去了），然后我要做的就是把这两个单词之后的字段作为输入，再重复上面这个过程，这个是大的方面，是另一个While循环。

想测试代码的直接去github吧，微信格式直接down下来可能会报错

正向匹配代码

## 正向最大匹配算法def cut_words(split_sentence,words_dic):    #统计词典中最长的词    max_length = max(len(word) for word in words_dic)    sentence = split_sentence.strip() ## 简单清理一下    #统计序列长度    words_length = len(sentence) ## 在第二个循环的时候，我需要不停的和字典最大长度比较，取最小值作为基线    #存储切分好的词语    cut_word_list = []    while words_length > 0: ## 第二个循环，找到一个之后，循环的去找下一个符合要求的        max_cut_length = min(max_length, words_length)        subSentence = sentence[0 : max_cut_length]        while max_cut_length > 0: ## 第一个循环，迭代找到符号字典的            if subSentence in words_dic:                cut_word_list.append(subSentence)                break            elif max_cut_length == 1:                cut_word_list.append(subSentence)                break            else:                max_cut_length = max_cut_length -1                subSentence = subSentence[0:max_cut_length]        sentence = sentence[max_cut_length:]        words_length = words_length - max_cut_length    return cut_word_listinput_str="今天天气真不错啊，适合出去旅游"bmm_word_list = cut_words(input_str, words_dic)print(bmm_word_list)

逆向匹配代码

def cut_words(raw_sentence,words_dic):    #统计词典中词的最长长度    max_length = max(len(word) for word in words_dic)    sentence = raw_sentence.strip()    #统计序列长度    words_length = len(sentence)    #存储切分出来的词语    cut_word_list = []    #判断是否需要继续切词    while words_length > 0:        max_cut_length = min(max_length, words_length)        subSentence = sentence[-max_cut_length:]        while max_cut_length > 0:            if subSentence in words_dic:                cut_word_list.append(subSentence)                break            elif max_cut_length == 1:                cut_word_list.append(subSentence)                break            else:                max_cut_length = max_cut_length -1                subSentence = subSentence[-max_cut_length:]        sentence = sentence[0:-max_cut_length]        words_length = words_length -max_cut_length    cut_word_list.reverse()    return  cut_word_list

参考链接：

中文分词中的正向最大匹配与逆向最大匹配：https://blog.csdn.net/chengzheng_hit/article/details/54752673

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入中文分词技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注中文分词

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。