赞
踩
前段时间研究了如何用分词工具进行分词,但是分词中涉及的一些算法,不太了解,所以,准备这段时间专攻分词算法原理,大家有补充,或者建议,欢迎留言。
最大匹配法是指以词典为依据,取词典中最长词长度作为第一次取字数量的长度,在词典中进行扫描。例如:词典中最长词为“中华人民共和国”共7个汉字,则最大匹配起始字数为7个汉字。然后逐字递减,在对应的词典中进行查找。
最大匹配法主要包括正向最大匹配法(FMM,Forward Maximum Matching)、反向最大匹配法(BMM, Backward Maximum Matching)和双向最大匹配法,均是基于词典的。
缺点:
优化:
为提升扫描效率,还可以跟据字数多少设计多个字典,然后根据字数分别从不同字典中进行扫描。
正向即从左往右取词,取词最大长度为词典中长词的长度,每次右边减一个字,直到词典中存在或剩下1个单字。
比如:
sentence = ‘我们在野生动物园玩’
user_dict = [‘我们’, ‘在’, ‘在野’, ‘生动’, ‘野生’, ‘动物园’, ‘野生动物园’, ‘物’,‘玩’]
词典最大长度 max_len = 5
第1轮扫描
第1次:“我们在野生”,扫描词典,无
第2次:“我们在野”,扫描词典,无
第3次:“我们在”,扫描词典,无
第4次:“我们”,扫描词典,有
扫描中止,输出第1个词为“我们”,去除第1个词后,开始第2轮扫描
第2轮扫描
第1次:“在野生动物”,扫描词典,无
第2次:“在野生动”,扫描词典,无
第3次:“在野生”,扫描词典,无
第4次:“在野”,扫描词典,有
扫描中止,输出第2个词为“在野”,去除第2个词后,开始第3轮扫描
第3轮扫描
第1次:“生动物园玩”,扫描词典,无
第2次:“生动物园”,扫描词典,无
第3次:“生动物”,扫描词典,无
第4次:“生动”,扫描词典,有
扫描中止,输出第3个词为“生动”,去除第3个词后,开始第4轮扫描
第4轮扫描
第1次:“物园玩”,扫描词典,无
第2次:“物园”,扫描词典,无
第3次:“物”,扫描词典,有
扫描中止,输出第4个词为“物”,去除第4个字后,开始第5轮扫描
第5轮扫描
第1次:“园玩”,扫描词典,无
第2次:“园”,扫描词典,无
扫描中止,输出第5个词为“园”,去除第5个字后,开始第6轮扫描
第6轮扫描
第1次:“玩”,扫描词典,有
扫描中止,输出第6个词为“玩”, ,整体扫描结束。
最终分词结果为:“我们/在野/生动/物/园/玩”。
FMM算法python代码如下:
def FMM_func(user_dict, sentence): """ 正向最大匹配(FMM) :param user_dict: 词典 :param sentence: 句子 """ # 词典中最长词长度 max_len = max([len(item) for item in user_dict]) start = 0 while start != len(sentence): index = start+max_len if index>len(sentence): index = len(sentence) for i in range(max_len): if (sentence[start:index] in user_dict) or (len(sentence[start:index])==1): print(sentence[start:index], end='/') start = index break index += -1
定义字典和例句,调用FMM方法,具体python代码如下
user_dict = ['我们', '在', '在野', '生动', '野生', '动物园', '野生动物园', '物','园','玩']
sentence = '我们在野生动物园玩'
FMM_func(user_dict, sentence)
则FMM输出结果为:
我们/在野/生动/物/园/玩/
反向即从右往左取词,其他逻辑和正向相同。句子和字典与1.1中相同。
第1轮扫描
第1次:“生动物园玩”,扫描词典,无
第2次:“动物园玩”,扫描词典,无
第3次:“物园玩”,扫描词典,无
第4次:“园玩”,扫描词典,无
第5次:“玩”,扫描词典,有
扫描中止,输出第1个词为“玩”,去除第1个词后,开始第2轮扫描
第2轮扫描
第1次:“野生动物园”,扫描词典,有
扫描中止,输出第2个词为“野生动物园”,去除第2个词后,开始第3轮扫描
第3轮扫描
第1次:“我们在”,扫描词典,无
第2次:“们在”,扫描词典,无
第3次:“在”,扫描词典,有
扫描中止,输出第3个词为“在”,去除第3个词后,开始第4轮扫描
第4轮扫描
第1次:“我们”,扫描词典,有
扫描中止,输出第4个词为“我们”,去除第4个词后,整体扫描结束。
最终分词结果为:“我们/在/野生动物园/玩”。
BMM算法python代码如下:
def BMM_func(user_dict, sentence): """ 反向最大匹配(BMM) :param user_dict:词典 :param sentence:句子 """ # 词典中最长词长度 max_len = max([len(item) for item in user_dict]) result = [] start = len(sentence) while start != 0: index = start - max_len if index < 0: index = 0 for i in range(max_len): if (sentence[index:start] in user_dict) or (len(sentence[start:index])==1): result.append(sentence[index:start]) start = index break index += 1 for i in result[::-1]: print(i, end='/')
定义字典和例句,调用FMM方法,具体python代码如下
user_dict = ['我们', '在', '在野', '生动', '野生', '动物园', '野生动物园', '物','园','玩']
sentence = '我们在野生动物园玩'
BMM_func(user_dict, sentence)
则BMM输出结果为:
我们/在/野生动物园/玩/
双向最大匹配法:FMM和BMM两种算法都分词一遍,然后根据大颗粒度词越多越好,非词典词和单字词越少越好的原则,选取其中一种分词结果输出。
如:“我们在野生动物园玩”
正向最大匹配法,最终分词结果为:“我们/在野/生动/物/园/玩”,其中,总分词数6个,单个词为3。
逆向最大匹配法,最终分词结果为:“我们/在/野生动物园/玩”,其中,总分词数4个,单个词为2。
选择标准:
因此最终输出为逆向结果。
参考链接:
https://blog.csdn.net/qq_41500251/article/details/88665875
https://blog.csdn.net/SMith7412/article/details/8813819
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。