非主流自然语言处理——遗忘算法系列（三）：分词
老憨发表于 2016-04-23 02:23:19
一、前言
前面介绍了词库的自动生成的方法，本文介绍如何利用前文所生成的词库进行分词。
二、分词的原理
分词的原理，可以参看吴军老师《数学之美》中的相关章节，这里摘取Google黑板报版本中的部分：
从上文中，可以知道分词的任务目标：给出一个句子S，找到一种分词方案，使下面公式中的P（S）最大：
不过，联合概率求起来很困难，这种情况我们通常作马尔可夫假设，以简化问题，即：任意一个词wi的出现概率只同它前面的词 wi-1 有关。
关于这个问题，吴军老师讲的深入浅出，整段摘录如下：
另外，如果我们假设一个词与其他词都不相关，即相互独立时，此时公式最简，如下：
这个假设分词无关的公式，也是本文所介绍的分词算法所使用的。
三、算法分析
问：假设分词结果中各词相互无关是否可行？
答：可行，前提是使用遗忘算法系列（二）中所述方法生成的词库，理由如下：
分析ICTCLAS广受好评的分词系统的免费版源码，可以发现，在这套由张华平、刘群两位博士所开发分词系统的算法中假设了：分词结果中词只与其前面的一个词有关。
回忆我们词库生成的过程可以知道，如果相邻的两个词紧密相关，那么这两个词会连为一个粗粒度的词被加入词库中，如：除“清华”、“大学”会是单独的词外，“清华大学”也会是一个词，分词过程中具体选用那种，则由它们的概率来决定。
也就是说，我们在生成词库的同时，已经隐含的完成了相关性训练。
关于ICTCLAS源码分析的文章，可以参看吕震宇博文：《天书般的ICTCLAS分词系统代码》。
问：如何实现分词？
答：基于前文生成的词库，我们可以假设分词结果相互无关，分词过程就比较简单，使用下面的步骤可以O(N)级时间，单遍扫描完成分词：
逐字扫描句子，从词库中查出限定字长内，以该字结尾的所有词，分别计算其中的词与该词之前各词的概率乘积，取结果值最大的词，分别缓存下当前字所在位置的最大概率积，以及对应的分词结果。
重复上面的步骤，直到句子扫描完毕，最后一字位置所得到即为整句分词结果。
3、算法特点
3.1、无监督学习；
3.2、O(N)级时间复杂度；
3.3、词库自维护，程序可无需人工参与的情况下，自行发现并添加新词、调整词频、清理错词、移除生僻词，保持词典大小适当；
3.4、领域自适应：领域变化时，词条、词频自适应的随之调整；
3.5、支持多语种混合分词。
四、演示程序下载
演示程序与词库生成的相同：
五、联系方式：
1、QQ：老憨 244589712
2、邮箱：gzdmcaoyc@163.com