双向最大匹配算法

双向最大匹配算法 

简介#

双向最大匹配方法是基于词典的分词方法，按照一定的策略将分析的汉字串与字典里面的词条进行匹配，若在词典中找到某个字符串，则匹配成功。

根据扫描的方向可以分为正向最大匹配算法和逆向最大匹配

正向最大匹配算法（MM）#

正向的方向定义是从字符串下标0到字符串末尾位置，取出字串与字典进行匹配

初始化最大匹配长度MaxLen，当前位置pos（初始为0），处理结果为result

0.令len = MaxLen，取出pos到pos+len的子串，查找字典

1.若匹配到，则将子串添加到result中，在保证不超出边界范围的情况下，pos = pos + len，向后匹配，len更新为0，回到步骤0处

2.若未在词典中找到该子串，len--（len>1），继续查找字典，若len == 1，则取出剩余子串，返回0步骤

2的步骤类似于：

你好吗

你好

你

这样的机制

逆向最大匹配（RMM）#

方法与正向类似，但方向相反

方向为从最后向前推进，即待匹配字符串长度-1的位置，取MaxLen，每次未匹配上则减去最前一个字

如：

你好吗

好吗

吗

这样的机制

双向最大匹配（BM）#

双向最大匹配算法的原理就是将正向最大匹配算法和逆向最大匹配算法进行比较，从而选择正确的分词方式

比较原则/步骤：

1.比较两种匹配算法的结果

2.如果分词数量结果不同：选择数量较少的那个

3.如果分词数量结果相同

​ 1.分词结果相同，返回任意一个

​ 2.分词结果不同，返回单字数较少的一个

​ 3.若单字数也相同，任意返回一个

为什么需要双向匹配#

根据研究，中文90%左右的句子，正向匹配和逆向匹配全然重合，但是存在9%句子两种切分方法得到的结果不一样，单期中必然存在一个是正确的，仅有1%的句子，重合部分是错的（或都不正确）