逆向最大匹配(Backward Maximum Matching)

简介: 逆向最大匹配(Backward Maximum Matching)是一种分词算法。它的工作原理与正向最大匹配相反,即从字符串结尾开始查找。

逆向最大匹配(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上找到数据集,自己实现一个逆向最大匹配模型
查看更多博客与文章,解决常见问题
总的来说,您可以通过:

理解原理
实现算法
实际应用
案例分析
有效理解和使用逆向最大匹配算法。

目录
相关文章
|
6月前
|
vr&ar C++
B. Fake Plastic Trees(贪心+dp)
B. Fake Plastic Trees(贪心+dp)
|
机器学习/深度学习 自然语言处理 算法
正向最大匹配(Forward Maximum Matching)
正向最大匹配(Forward Maximum Matching)是一种查找文本字符串中词语的算法。
431 1
UVa10776 - Determine The Combination(有重复元素的组合问题)
UVa10776 - Determine The Combination(有重复元素的组合问题)
43 0
|
存储
LeetCode 187. Repeated DNA Sequences
所有 DNA 由一系列缩写为 A,C,G 和 T 的核苷酸组成,例如:“ACGAATTCCG”。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。 编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列(子串)。
81 0
LeetCode 187. Repeated DNA Sequences
|
机器学习/深度学习 安全
Re28:读论文 CECP Charge Prediction by Constitutive Elements Matching of Crimes
Re28:读论文 CECP Charge Prediction by Constitutive Elements Matching of Crimes
Re28:读论文 CECP Charge Prediction by Constitutive Elements Matching of Crimes
|
人工智能
UPC-Match Matching(完全背包dp+字符串)
UPC-Match Matching(完全背包dp+字符串)
78 0
|
算法 决策智能
Greedy Randomized Adaptive Search 算法超详细解析,附代码实现TSP问题求解(一)
Greedy Randomized Adaptive Search 算法超详细解析,附代码实现TSP问题求解
331 0
Greedy Randomized Adaptive Search 算法超详细解析,附代码实现TSP问题求解(一)