逆向最大匹配(Backward Maximum Matching)是一种分词算法。它的工作原理与正向最大匹配相反,即从字符串结尾开始查找。
原理
从字符串结尾开始查找,匹配最长可以匹配的词语:
从字符串结尾开始查找
查找最长的可以匹配的词语
匹配到最长的词语后,将其移除,并重复第一步,直到字符串起始处
示例:
字符串:goodness going goodes good
匹配goodness(最长匹配)
去除goodness,字符串变为:going goodes good
匹配going(最长匹配)
去除going,字符串变为:goodes good
5.匹配 goodes(最长匹配)
...
最终匹配到的词语序列为:goodness going goodes good
与正向最大匹配相比,逆向最大匹配可以避免一些歧义。
应用
分词。可用于中文/英文分词任务。
信息检索。评估文本与查询的相关性。
文本挖掘。从文本中提取关键词。
示例代码
Python 实现逆向最大匹配分词:
python
Copy
def backward_max_matching(text):
words = []
while text:
for i in range(len(text),0,-1):
word = text[-i:]
if word in dictionary:
words.append(word)
text = text[:-i]
break
return words
它通过搜索字典中存在的最长词语,实现分词。
'''
(分词算法)逆向最大匹配算法negative_max_matching(max_length, words, ch_dict)
max_length 为最大匹配词语长度
words 为待分词文本
ch_dict 为词典
'''
def negative_max_matching(max_length, words, ch_dict):
word_list = [] # 存放分词后的分词词组
while len(words) >= 1: # words不为空时，循环地进行分词操作
max_match_len = max_length # 取出最大匹配单词长度为循环判断做准备
while max_match_len > 1: # 当匹配单词长度大于1时，循环判断分词
sample_word = words[-max_match_len : ] # 判断 words 倒数 max_length 个字符是否存在于字典
print("截取的词：", sample_word)
if sample_word in ch_dict: # 判断取出的字符序列是否在词典ch_dict中
word_list.append(sample_word) # 追加到分词词组中
words = words[ : -max_match_len] # 将符合的词语从原例句中截取
break # 退出循环，重新从max_length最长匹配数开始匹配截取
max_match_len -= 1 # max_length减小1个单位
# 当 max_length 为 1 时代表只剩下一个汉字，直接截取词组中最后的汉字作为词组
if max_match_len == 1:
sample_word = words[-1 : ]
word_list.append(sample_word) # 追加单个汉字词语
print("截取的词：", sample_word)
words = words[:-1] # 截取例句
return word_list
if __name__ == '__main__':
dict_words = ["生活", "研究", "家居", "美好", "手机", "强大", "功能", "喜欢", "智能", "本质", "铭铭", "人工", "研究生"] # 词典
words = "铭铭喜欢研究生活的本质" # 待分词的文本
contents = negative_max_matching(4, words, dict_words) # 调用算法分词，备注：最大匹配词语长度设为4，实际上因为词典中最大词语长度为3，可以设置为3
print("分词的结果：", contents)
print("分词后的例句:", '/'.join(contents)) # 输出进行分词后的例句
contents = contents[::-1] # 对分词列表进行倒序处理
print('/'.join(contents)) # 再次输出倒序后的分词例句
以下是学习和使用逆向最大匹配算法的一些推荐资料:
1.《自然语言处理:理论与技术综述》一书对逆向最大匹配算法做了详细解释,并讨论其在中文分词中的应用。
2.《中文分词技术与系统实现》也有介绍逆向最大匹配,详细介绍了该算法。
3.相关在线课程包括:
Andrew Ng 机器学习课程,在分词一章有介绍
斯坦福自然语言处理课程
北大语音与自然语言处理课程等。
4.可以学习的内容主要有:
逆向最大匹配的原理与实现
在中文分词与信息检索中的应用
使用编程实现算法
与其他算法的对比与优缺点分析
除此之外,您还可以:
查看Kaggle和GitHub上的相关项目源码
在Kaggle上找到数据集,自己实现一个逆向最大匹配模型
查看更多博客与文章,解决常见问题
总的来说,您可以通过:
理解原理
实现算法
实际应用
案例分析
有效理解和使用逆向最大匹配算法。
