基于词库的双向最大匹配算法_飞书词库匹配算法是什么

基于词库的双向最大匹配算法

本文介绍了基于词库的双向最大匹配算法。该算法实现简单，分词效果依赖于词库。在词库相当的情况下，分词效果不错。某些情况下甚至强于基于隐马尔科夫模型的智能分词。

 

      【双向最大匹配算法】从名字上来看（顾名思义），就是以最大匹配为原则、以双向的切分为方法进行汉子切分。本文所举得所有例子均是在词库足够完整的情况下进行的。

 

什么叫以最大匹配为原则?

       最大匹配原则就是在词库中找到最长匹配字符串作为一个单词。如“我出生在中华人民共和国”，以最大匹配原则进行分词则分词结果为“我”、“出生”、“在”、“中华人民共和国”，而不是“我”、“出生”、“在”、“中华”、“人民”、“共和国”。

 

什么是双向切分？

       要说双向切分算法就不得不说下正向切分算法以及逆向切分算法。

 

       先说正向切分算法。正向切分算法其实就是按照人得自然阅读顺序对一句话进行词库切分。即从前往后进行词匹配。如“中国的首都是北京”这句话，可以如下步骤进行切分：

       1：取出词库中以“中”开头的词；

       2：取出词库中以“中国”开头的词；

       3：取出词库中以“中国的”开头的词；

       4：第三步取词为空，所以分出词“中国”。

       5：对接下来的字符串重复1-5步骤，直到字符串扫描完毕。

 

       分词完毕之后结果为：“中国”、“的”、“首都”、“是”、“北京”。

       为简化理解难度我采用了”以**为开头的词“这样的说法，但是在代码中实现时这样的方式运算量较大，速度较慢，为提高取词效率，建议采用多叉树结构，进行词库的存储，下同。

 

       正向切分的缺点是什么？其实只要看对下面这句话的切分就知道了。

       “我出生在河北省会”

       按照正向切分且以最大匹配为原则进行切分，结果为：“我”、“出生”、“在”、“河北省”、“会”。这显然是不对的。其实在汉语中这样的例子有很多，如:“在野生动物园”（在野、生动、物、园）、“技术和服务”（技术、和服、务）等。所以有人提出了逆向切分算法。

 

       逆向切分算法在实现上来说完全就是正向切分算法那一套。只是词库是逆向词库，对于切分语句的切分顺序为从后往前切。还以“我出生在河北省会”为例，切分步骤如下：

       1：找出反向词库中以“会”为开头的词；

       2：找出反向词库以“会省”为开头的词；

       3：找出反向词库以“会省北”为开头的词；

       4：第三步取词为空，所以取词“会省”；

       5：对接下来的字符串重复1-5步骤，直到字符串扫描完毕。

 

       分完词之后的结果为“会省”、“北河”、“在”、“生出”、“我”。对结果以及词进行翻转，则结果为“我”、“出生”、“在”、“河北”、“省会”。

可以看到逆向的分词结果较正向的分词结果更为准确。但是这个准确并非是分词算法上有了提高，仅仅是因为利用了汉语的习惯而已。既然使用了相同的算法，所以逆向切分的缺点跟正向的相同，如对“长春药店”就有可能分出“长”、“春药店”这样的词。

 

       因为正向切分以及逆向切分的缺点（其实就是一个缺点），人们提出了双向切分算法。双相切分算法就是使用正向切分一次、逆向切分一次。如果两次切分结果一样的话就好说了，随便选一个结果就可以。

但是如果切分不一样的话使用那一次的切分结果呢？这就涉及到了结果的选取原则问题。老夫以为切分词应该遵守以下原则：

       1：最大匹配原则：上面一直在说这个，老夫认为使用这个原则的原因是词的字数越多，表示的含义越丰富、对于一条语句分出来的词也就越少，相对的，准确性也就会越高。

       2：词库中没有的单字词越少越好。这个原则有点依赖于词库了，至少词库中应该有一些常用的单字成词的字吧，比如：“你”、“我”、“他”、“和”、“的”、“了”等。使用这个原则的原因可以从上面提到的“技术和服务”这个例子看出来：

正向结果：技术、和服、务

逆向结果：技术、和、服务

       虽然分出来的结果单字词都是一个，但是，逆向的单字词”和“在词库中存在，所以我们选择返回逆向切分结果。

 

       虽然双向切分算法的分词准确度大大提高了，但是双向切分算法并不是一个智能算法，这是由算法的基因决定的。但是双向最大匹配算法确实可以解决大多数的中文分词问题（依赖于词库）。只要有一个差不多（实在不知道该怎么形容，只好使用差不多这个词了）的词库（这类的词库在网上很容易就能搞到手），使用如此简单的一个算法，却解决了一个如此复杂的问题，这本身也是一个非常美妙的事情。

 

       今就到这，关于智能分词算法，等忙过这段时间在整理吧。