基于动态规划的整句输入法

一般来说,我们不会在用动态规划算法求解的问题上称呼它为“动态规划”,而是称之为“隐马尔可夫模型”,不过,如果我们单纯用动态规划算法来求解一个普通的有向无环图,那么就只能说是动态规划了……

这次我们要来说的,是基于词库的整句输入法。而不是基于状态转移的隐马尔可夫模型求解。

词库

由于不需要模型,我们的整句输入是基于词汇的,就需要一个词库。这个词库里应该记录了普通人大部分的常用词汇,而且有一点就是词频(权重)一定要是正确的。

原理

你可以这样理解,当你输入一串拼音的时候,每一个音会对应一大堆的中文字,如果每一个字单独来看,就会有太多的字与之对应——这就是所谓的重码了。而对应词库的话,如果用户输入的是一个词汇,那么我们就优先命中词库,这样一来,由于词汇的码比较长,那么重码的概率和数量就大大减少了,再配合词频,我们就能得到一个比较符合常理的候选字序列供用户选择了。

可是整句呢?当用户输入了太长而无法从词库中匹配到词汇的时候,我们该怎么办呢?

整句计算

简单版

照着上文中的原理,我们顺着思路想想看,这么长的句子,我们可以考虑把它们拆分开,比如从前往后,依次匹配能找到的最大(长)词汇,那么整句输入就可以实现了!

比如你输入了 luo/ge/shu/ru/fa/ke/neng/shi/qi/jin/wei/zhi/zui/hao/yong/de/shu/ru/fa

那么我就按照从前往后依次遍历每一个音,找到最可能的那个,这是可能的一种结果,答案取决于你的词库有多烂:

罗格/输入法/可能是其/近卫/致最好用/的/输入法

显然,这距离我们想要的东西还差了很远。如果你做成这样就发布,那么用户得打死你。所以,我们换一种思路,还是依次匹配最长的可能的词,但不会自动匹配所有,从第一个能匹配到的词汇开始,暂停计算让用户自己去选择合适的候选字。

好吧,这样虽然不算是完整的智能整句输入,但是如果配合用户词库,那么勉强能用的,如果你的词库数据又比较全,那么效果应该也不差。

进阶版

那么,就这样了吗?当然不是,你看我们还没有用到题目中的“动态规划”呢。其实仔细想一想,我们的词库,有着准确的词频,该怎么给它利用起来呢?我们通过算法,把词库的词频进行规划,将词频转换为权重,词的权重大于字的权重。

这样一来,我们在把所有可能的组合一一列举,然后把每一个词的词频相乘,最后得到结果越大,那么语句中词汇就越多,同时还能找到最优的组合(整体词频最大),这样应该就差不多了。

比如 luo/ge/shu/ru/fa

我们用的词库是这样的:

  • 落格:0.11;罗格:0.15;罗哥:0.13
  • 个数:0.15;格数:0.13
  • 输入:0.21;淑如:0.19
  • 儒法:0.09
  • 输入法:0.29
  • 发:0.05;法:0.03

那么结果就可能有这些(部分):

  1. 罗格/输入法 —— 0.15*0.29 = 0.0435
  2. 落格/输入法 —— 0.11*0.29 = 0.0319
  3. 罗格/输入/发 —— 0.15*0.21*0.05 = 0.001575
  4. 落格/输入/发 —— 0.11*0.21*0.05 = 0.001155

你看,这下就可以得到更优质一点的解了,虽然看上去和简单版一样能够得到“罗格输入法”,但上文是无脑匹配,那么很有可能会将后边的词比如“迄今为止”,给拆到了前一个词里。但在我们现在的高级算法里,会计算“迄今为止”的权重,它要比“可能是其”更高,那么就不会被拆开了,配合权重,我们就能极大概率地避免高频词汇被拆的情况。

 

维特比算法

维特比可能是应用最为广泛的动态规划算法了吧,从数字通信到语言分词,无一例外。所以,我们同样在这里使用它。不过,我们不是数学家,单纯去研究这个算法恐怕不是很有必要,所以算法问题暂时揭过不提,主要还是来看看如何用它来给我们的整句求解。

毕竟,要计算整句中所有的可能的词汇组合,穷举是一个 SB 的行为,短了还行,用户输入了10个字呢?50个字呢?

我们从一串音的头部开始,依次遍历整个语句,找到能在词库里找到的所有开始,然后拿它们生成图的开始,比如还是我们的 luo/ge/shu/ru/fa ,我们假定词库里没有“落格输入法”这个词汇,那么可能的开始就会有:

  • 咯(等等等一系列单字)
  • 落格
  • 罗格
  • 罗哥
  • 罗格书

将这些依次建立路径的起始,然后依次遍历图的每一条路径,再重复这个过程,直到结束,这样,我们就能得到所有可能的组合了,由于我们将计算的问题转化为了篱笆网络的有向图,配合动态规划算法,我们可以将计算复杂度极大地降低,让我们的算法得以运行。

溢出

由于可能句子会很长,那么你可能在计算的时候遇到一个问题,就是权重太小以至于计算机的精度不够导致结果不正确。这里我简单说下,那就是使用对数。比如一个很小的值 0.000000000000232,对数的结果就是 −12.6345120151091 ,这样就可以避免一个很小的数和很大的数互相操作而被丢弃。我们使用对数的加法代替原本权重的乘法即可。

总结

单纯用动态规划+词库来实现整句输入,理解起来不是很难,实现也很简单,这也是落格输入法一直在使用的算法——毕竟快!相对于隐马尔可夫模型基于字的求解,显然,词汇的重码数量小多了!

不过前提也高,要词库尽可能的大,否则词库中不存在的词无法参与计算;要求你的词频符合实际且质量高,否则计算出的结果差强人意。

另外,我们文中并没有讨论拼音分词的问题,由于落格输入法是双拼输入法,所以目前得益于双拼的特性我还没有面临这个问题,全拼拼音是变长的,最好的办法是给它们进行编码,同时涉及到拼音的分词问题,这就是另外一块的知识了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注