前面介绍了词库的自动生成的方法，本文介绍如何利用前文所生成的词库进行分词。

　　分词的原理，可以参看吴军老师《数学之美》中的相关章节，这里摘取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、支持多语种混合分词。

　　演示程序与词库生成的相同：

　　下载地址：遗忘算法（词库生成、分词、词权重）演示程序.rar

　　1、QQ：老憨 244589712

　　2、邮箱：gzdmcaoyc@163.com

　　本文介绍利用牛顿冷却模拟遗忘降噪，从大规模文本中无监督生成词库的方法。

　　　　算法分析，先来考虑以下几个问题

　　　　问：目标是从文本中抽取词语，是否可以考虑使用遗忘的方法呢？

　　　　答：可以，词语具备以相对稳定周期重复再现的特征，所以可以考虑使用遗忘的方法。这意味着，我们只需要找一种适当的方法，将句子划分成若干子串，这些子串即为“候选词”。在遗忘的作用下，如果“候选词”会周期性重现，那么它就会被保留在词库中，相反如果只是偶尔或随机出现，则会逐渐被遗忘掉。

　　　　问：那用什么方法来把句子划分成子串比较合适呢？

　　　　答：考察句中任意相邻的两个字，相邻两字有两种可能：要么同属于一个共同的词，要么是两个词的边界。我们都会有这样一种感觉，属于同一个词的相邻两字的“关系”肯定比属于不同词的相邻两字的“关系”要强烈一些。

　　　　数学中并不缺少刻划“关系”的模型，这里我们选择公式简单并且参数容易统计的一种：如果两个字共现的概率大于它们随机排列在一起的概率，那么我们认为这两个字有关，反之则无关。

　　　　如果相邻两字无关，就可以将两字中间断开。逐字扫描句子，如果相邻两字满足下面的公式，则将两字断开，如此可将句子切成若干子串，从而获得“候选词”集，判断公式如下图所示：

　　　　

　　　　公式中所需的参数可以通过统计获得：遍历一次语料，即可获得公式中所需的“单字的频数”、“相邻两字共现的频数”，以及“所有单字的频数总和”。

　　　　问：如何计算遗忘剩余量？

　　　　答：使用牛顿冷却公式，各参数在遗忘算法中的含义，如下图所示：

　　　　牛顿冷却公式的详情说明，可以参考阮一峰老师的博文《基于用户投票的排名算法（四）：牛顿冷却定律》。

　　　　

　　　　问：参数中时间是用现实时间吗，遗忘系数取多少合适呢？

　　　　答：a、关于时间：

　　　　　　可以使用现实时间，遗忘的发生与现实同步。

　　　　　　也可以考虑用处理语料中对象的数量来代替，这样仅当有数据处理时，才会发生遗忘。比如按处理的字数为计时单位，人阅读的速度约每秒5至7个字，当然每个人的阅读速度并不相同，这里的参数值要求并不需要特别严格。

　　　　　　b、遗忘系数可以参考艾宾浩斯曲线中的实验值，如下图（来自互联网）

　　　　

　　　　　　我们取6天记忆剩余量约为25.4%这个值，按每秒阅读7个字，将其代入牛顿冷却公式可以求得遗忘系数：

　　　　

　　　　　　注意艾宾浩斯曲线中的每组数值代入公式，所得的系数并不相同，会对词库的最大有效容量产生影响。

二、该算法生成词库的特点

　　这里“遗忘”不是笔误，这个系列要讲的“遗忘算法”，是以牛顿冷却公式模拟遗忘为基础、用于自然语言处理（NLP）的一类方法的统称，而不是大名鼎鼎的“遗传算法”！

　　在“遗忘”这条非主流自然语言处理路上，不知不觉已经摸索了三年有余，遗忘算法也算略成体系，虽然仍觉时机未到，还是决定先停一下，将脑中所积梳理成文，交由NLP的同好们点评交流。

　　能够从未知的事物中发现关联、提炼规律才是真正智能的标志，而遗忘正是使智能生物具备这一能力的工具，也是适应变化的利器，“遗忘”这一颇具负能量特征的家伙是如何实现发现规律这么个神奇魔法的呢？

　　让我们从巴甫洛夫的狗说起：狗听到铃声就知道开饭了。

　　铃声和开饭之间并不存在必然的联系，我们知道之所以狗会将两者联系在一起，是因为巴甫洛夫有意的将两者一次次在狗那儿重复共现。所以，重复是建立关联的必要条件。

　　我们还可以想像，狗在进食的时候听到的声音可能还有鸟叫声、风吹树叶的沙沙声，为什么这些同样具备重复特征声音却没有和开饭建立关系呢？

　　细分辨我们不难想到：铃声和开饭之间不仅重复共现，而且这种重复共现还具备一个相对稳定的周期，而其他的那些声音和开饭的共现则是随机的。

　　那么遗忘又在其中如何起作用的呢？

　　　　1、所有事物一视同仁的按相同的规律进行遗忘；

　　　　2、偶尔或随机出现的事物因此会随时间而逐渐淡忘；

　　　　3、而具有相对稳定周期重复再现的事物，虽然也按同样的规律遗忘，但由于周期性的得到补充，从而可以动态的保留在记忆中。

　　在自然语言处理中，很多对象比如：词、词与词的关联、模板等，都具备按相对稳定重现的特征，因此非常适用遗忘来处理。

　　那么，我们用什么来模拟遗忘呢？

　　提到遗忘，很自然的会想到艾宾浩斯遗忘曲线，如果这条曲线有个函数形式，那么无疑是模拟遗忘的最佳建模选择。遗憾的是它只是一组离散的实验数据，但至少让我们知道，遗忘是呈指数衰减的。

　　另外有一个事实，有的人记性好些，有的人记性则差些，不同人之间的遗忘曲线是不同的，但这并不会从本质上影响不同人对事物的认知，也就是说，如果存在一个遗忘函数，它首先是指数形式的，其次在实用过程中，该函数的系数并不那么重要。

　　这提醒我们，可以尝试用一些指数形式的函数来代替遗忘曲线，然后用实践去检验，如果能满足工程实用就很好，这样的函数公式并不难找，比如：退火算法、半衰期公式等。

　　有次在阮一峰老师的博客上看关于帖子热度排行的算法时，其中一种方法使用的是牛顿冷却定律，遗忘与冷却有着相似的过程、简洁优美的函数形式、而且参数只与时间相关，这些都让我本能想到，它就是我想要的“遗忘公式”。

　　在实践检验中，牛顿冷却公式，确实有效好用，当然，不排除有其他更佳公式。

四、已经实现的功能