分词算法的原理及简单实现(一)

简介

分词工具也算是接触过一点了,目前工作上主要用到的一个是MMSEG,另一个是jieba分词。对于分词,可不能就简单的调调接口,所以现在就来看一看分词算法的相关原理,并尝试实现一个简单的分词工具。

算法原理

MMSEG

MMSEG基于字符串匹配,即扫描字符串,使用如正向/逆向最大匹配,最小切分等策略,也就是基于词典。具体使用的时候,通常是多种算法合用,或者一种为主、多种为辅,同时还会加入词性、词频等属性来辅助处理(运用某些简单的数学模型)。

MMSEG的主要思想是每次从一个完整的句子里,按照从左向右的顺序,识别出多种不同的3个词的组合,然后根据下面的4条消歧规则,确定最佳的备选词组合。

  • 备选词组合的长度之和最大
  • 备选词组合的平均词长最大
  • 备选词组合的词长变化最小
  • 备选词组合中,单字词的出现频率统计值最高

正向最大匹配

对输入的句子从左至右,以贪心的方式切分出当前位置上长度最大的词,组不了词的字单独划开。其分词原理是:词的颗粒度越大,所能表示的含义越精确。

逆向最大匹配

原理与正向最大匹配相同,但顺序不是从首字开始,而是从末字开始,而且它使用的分词词典是逆序词典,其中每个词条都按逆序方式存放。在实际处理时,先将句子进行倒排处理,生成逆序句子,然后根据逆序词典,对逆序句子用正向最大匹配。

双向最大匹配

将正向最大匹配与逆向最大匹配组合起来,对句子使用这两种方式进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则,按最小集处理。

jieba分词

项目的介绍信息来看,简单来说,分三步:

  • 基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
  • 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合;
  • 对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法。

算法关键点

无论是 MMSEG 还是jieba分词,都免不了基于字典数据对输入句子的拆分的工作,主要的区别在于根据字典进行拆分后,如何选出合适的字词组合方式。接下来就仔细看一下jieba分词实现的各个细节。

前缀词典

不同于MMSEG中使用Trie树来存储前缀词典,jieba分词的python实现中采用的是基本的集合来存储前缀词典,项目的issue中提到过这个问题。

Trie树算法介绍:数据结构之Trie树,至于为什么Trie树的效率不如前缀词典,这个有待探讨。

生成有向无环图(DAG)

有向无环图,directed acyclic graphs,简称DAG。有向无环图的构建方式如下:

从前往后依次遍历文本的每个位置,对于位置k,首先形成一个片段,这个片段只包含位置k的字,然后就判断该片段是否在前缀词典中,

  1. 如果这个片段在前缀词典中,
    1. 如果词频大于0,就将这个位置i追加到以k为key的一个列表中;
    2. 如果词频等于0,如同第2章中提到的“北京大”,则表明前缀词典存在这个前缀,但是统计词典并没有这个词,继续循环;
  2. 如果这个片段不在前缀词典中,则表明这个片段已经超出统计词典中该词的范围,则终止循环;
  3. 然后该位置加1,然后就形成一个新的片段,该片段在文本的索引为[k:i+1],继续判断这个片段是否在前缀词典中。
“去北京大学玩”这个句子构成的有向无环图

查找最大概率路径

在有向无环图中寻找最大概率路径,实际上是一个动态规划问题。这里就不多说动态规划了,可以参考这篇文章《算法笔记——动态规划》。为了求解这个动态规划问题,需要弄清楚:最优子状态与状态转移方程。

对于最大概率路径的求解,最优子状态是从起点到指定的一个节点的最大概率值。状态转移方程是:

当前节点的最大概率值 = max(当前节点前一个节点的最大概率值 + 当前节点到前一个节点的概率值)

利用HMM处理未登录词

对于一些垂直领域而言,比如地图数据,新词的增长并不会很快,通过词典分词是一种比较稳妥的手段。但是在某些领域,尤其是 UGC 占主要组成的领域,例如用户评价数据,二手商品数据,词典无法及时的覆盖到新词,会影响到分词的效果,进而影响到搜索的效果。同时,新词的发现在内容推荐方面也起到一定的作用。

HMM的内容太多,这里说不下。关于HMM的内容在文章《HMM的知识点》中进行详细的介绍。

参考资料

发表评论

您的电子邮箱地址不会被公开。