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

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

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

词库

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

原理

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

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

整句计算

简单版

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

比如你输入了 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 ，这样就可以避免一个很小的数和很大的数互相操作而被丢弃。我们使用对数的加法代替原本权重的乘法即可。

总结

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

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

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

本文由 落格博客 原创撰写：落格博客 » 基于动态规划的整句输入法

转载请保留出处和原文链接：https://www.logcg.com/archives/2338.html