拼音整句识别的维特比算法优化
不知从什么时候开始，整句识别成为了拼音输入法的标配，几乎每一款输入法都有整句输入功能。重码量巨大的拼音输入也因此逐渐打败形码输入，成为绝大部分人的选择。本以为如此标配的东西应该比较容易实现。但在处理时却发现，要做到「能用」的标准并不容易。难点到不在算法本身，因为其核心算法大都是基于比较公开的隐含马尔可夫模型下的维特比算法。困难在于，如何能生成一个优质的词库数据，以及如何权衡准度、速度和空间占用。折腾了一段时间，终于达到凑合能用的水平。
维特比算法
什么是维特比（viterbi）算法？先看一段百度百科的定义：
维特比算法是一种动态规划算法用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。
那么，用听得的懂的话应该如何说呢？简单来说就是，现在你想了解某个东西所处的真实状态是什么，但又没办法直接掌握，或者说没能力直接获取，可供你判断的的信息只有这个东西表现出来的一些外在特征。比如，你不知道一个公司的内部的动作情况，但你观察他的股价，可以做一个大致的估计。说准确点就是，给定一个确定的观测序列，如何找出最有可能对应这一观测的状态序列。因此，维特比算法主要用于信息解码，如语音识别，无线通信等。比如，给了一串语音，如何去计算其最可能对应的文字是什么。
既然是说拼音的整句识别，那就再举一个输入法的例子。当用户输入拼音串「dui'bu'qi」时，面对那么多的中文重码，如何知道用户想要的文字是什么呢？你可能觉得这很容易啊，一定是「对不起」嘛，这还用得着复杂的算法？弄个词库就行了嘛！可如果是「qin'ai'de'gu'ke'ni'hao」呢，或者是「xie'lou'guo'jia'ji'mi'zui'zui'ming'cheng'li」或呢，做为人类的你还能一下子看出来吗？对于计算机，也不能把所有语言都放入词库吧？
一阶假设下的维特比算法
一阶隐含马尔可夫模型下的算法是最简单的形式，其核心是通过几个概率的加总来计算出一个最有可能出现的隐藏状态。这些因素是：起始状态概率「观测值对应状态概率、从前一个状态到下一个状态的概率。根据这些概率，计算出一个概率最高状态序列，即最有可能出现的状态。先上一个高大上的公式装一装：
初始条件 ： $\delta _1(i) = \pi(i)b_i(O_1)$
迭代公式： $\delta_t(j)=\max \limits_{1\le i \le N}[\delta_{t-1}(i)a_{ij}]b_j(O_j)$ \quad 2\le t \le T, 1\le j \le N$
公式上看好像是很高深的算法，但其实，逻辑上还是非常简单的。维特比算法主要是计算每一种状态序列的概率，而 $\delta$ 就是表示状态概率的变量。其中，下标为观测的时刻，对于拼音整句识别而言，就是观测到了第几个音，括号内的变量表示状态。所以$\delta_1(i)$ 就是第一个音对应的状态 $i$ 的概率。就整句识别而言，状态就是「字」，即「字」$i$ 的概率。初始状态下的概率只取决于两个变量，一是状态 $i$ 做为开头的概率 $\pi(i)$，二是观测到音$O_j$ 出现状态 $i$ 的概率$b_i (O_1)$。
有了初始条件，就可以开始计算下一个状态 $j$ 的概率 $\delta_2 (j)$ 。这一概率主要取决于三个因素。一是上一状态 $ i $ 的概率，二是从状态 $i$ 到状态 $j$ 的概率，三是观测音出现状态 $j$ 的概率。因为这一步只考虑上一状态对当前状态的影响，所以称为一阶模型。
按照迭代公式，就可以计算出所有可能状态序列的权重，从中选择出来最大的就是维特比算法的最优路径结果。当然，完整的算法公式还有一个逆推最优路径的算子表示。不过，那个对于理解算法核心并不是特别重要，所以就不再故弄玄虚了。
如果这样还没不太明白，那就以「dui'bu'qi」为例，简单的说明一下。
第一步，先计算初始概率$\delta_1$。这一概率取决于两个因素。一是第一个音「dui」可能出现的字的概率。假设这个音有「对，队，堆」三个字，且出现的概率分别为「0.5, 0.3, 0.2」。二是每一个字做为起始的概率，假设其分别为「0.6, 0.2, 0.2」。那么，三个可能状态「对，队，堆」的概率就是二者相乘，即「0.3, 0.06, 0.04」。
第二步，计算第二音时的状态概率 $\delta_2$。这一概率取决于三个因素，一是第二个音「bu」可能出现的字的概率，假设这个音只有「不，部」两个字，且出现的概率分别为「0.6, 0.4」。二是从第一字过渡到第二字的概率，假设从「对」到「不」的概率为 0.7，从「对」到「部」的概率为 0.3，从「队」到「不」的概率为 0.2，对「队」到「部」的概率为 0.8，从「堆」到「不」的概率为 0.6，从「堆」到「部」的概率为 0.4。三是前一个状态的概率， 这个上一步已经计算。把三个概率相乘就得到序列 2 时所有状态的概率，即「对不，对部，队不，队部，堆不，堆部」的概率分别为「0.126, 0.036, 0.0072, 0.0192, 0.0144, 0.0064」。
第三步，按类似的方法计算第三个音对就所有状态的概率。假设「qi」只对应一个字「起」。且上一状态「不，部」到「起」的转移概率分别为「0.6, 0.4」。那么所有可能状态序列的概率，即「对不起，对部起，队不起，队部起，堆不起，堆部起」的概率分别为「0.0756, 0.0144, 0.00432, 0.00768, 0.00864, 0.00256」
第四步，选择概率最大即为最优序列路径。因此，「对不起」可做为「dui'bu'qi」的首选，「对部起」可做为次选，「堆不起」可做为三选。
可以看到，在假设重音字这么少的情况下，计算量已经不小。如果考虑到每个音可能对应十多个汉字，且拼音串较长，那么，看似简单的整句识别，其背后的查询和计算量也是相当庞大的。而且一阶模型的计算结果还远达不到基本可用的标准。
二阶假设下的维特比算法
一阶HMM下的维特比算法虽然逻辑简单且处理容易，但应用在拼音整句识别上，其准确率并不能令人满意。比如，当你看到前一个字是「立」，且紧跟其后的拼音是「ji」时，估计绝大部分人会得到「立即」这个词。但是，如果你这时又知道前前一个字是「鹤」时，你肯定马上会说，「ji」这个音应该是「鸡」字，而且你甚至还能猜出来后面的字肯定是「群」。可见，如果使用二阶的HMM，那么，可以很大程度的改善准确性。
还好的是，二阶HMM下的维特比算法也不算复杂。其中，前两个音时因为没有涉及到二阶的问题，所以计算方式与一阶是一样的。从第三个字开始，状态概率 $\delta$ 的迭代公式就需要考虑前前一个字的情况：
$\delta_t(k)=\max \limits_{1\le i \le N}[\delta_{t-1}(i)(\alpha a_{j,k}+\beta a_{ij,k})]b_k(O_k)$
$\alpha + \beta = 1$
上式中，$k$ 为当前状态，$ i, j$ 分别为状态 $k $ 的前一个状态和前前一个状态。这时，当前字的状态概率就不是只取决于前一个字的情况，而是同时取决于前一个状态到当前状态的转移概率 $a_{j,k}$，以及前两个字到当前状态的转移概率 $b_{ij,k}$，这两个概率通过 $\alpha$ 和 $\beta$ 两个系数归一化。这两个系数的取值可根据自己的语料库进行调整，原则上应该是和 $\beta$ 大于 $\alpha$，在我的测试中使用 $0.9$ 和 $ 0.1$ 。
和一阶模型相比，二阶算法主要是增加了一个从前两个状态到当前状态的转移概率矩阵。仅此一点就可以大幅度的提高识别的准确性。但同时，仅增加的这一个库，也会给算法的空间复杂度和时间复杂度带来很大的麻烦。
空间与准确的权衡
二阶假设下的准确性确实得到了很大的改善，但增加的空间复杂度和时间复杂度也是惊人的。
先说空间复杂度。中文GB2312标准有汉字6763个，那么两两之间的转移概率矩阵就是一个包含 $6763 \times 6763$ 元素的矩阵。如果每个转移概率用一个double类型存储，那么完整存储共需要接近350兆的硬盘空间。如果再考虑二阶转移矩阵，那完整存储需要占用约 $6763^3\times 3$ 字节的硬盘空间，大约是2000多GB。别说是手机设备，即使是PC端也是不可想像的事情。
减少转移矩阵的空间占用主要有两个途径。
第一，删除一些极不常用的汉字。拼音的整句识别主要用于聊天场景下的日常应用，基本不会用于专业性很强的文字输入。当然，你也可以在这些环境中使用，但想必即使是百度、搜狗这种大厂的输入法也难以让你满意（这些大厂输入法可能会借助所谓的云输入来提高准确性）。因此，一些非常用汉字就可以从转移矩阵中删除了，如「猃鲕泐瀵礻灬」等，这些字可能你根本就不认识，可能你一辈子也用不上，有些甚至根本就不是正常的汉字。那么，应该删除哪些呢？中文的一级汉字和二级汉字共约3500个，这些是日常使用最多的汉字。如果整句识别只考虑这些汉字，可以大大降低转移矩阵的空间占用。一阶可以减少近75%，二阶可以减少85%左右。
第二，删除矩阵中转移概率为 0 的元素，以及一些概率极低的元素。理论上，任意两个汉字之间都有转移的可能存在，比如「入电」可能是「放入电饭煲」、「出键」可能是「呼出键盘」、「移应」可能是「移动应用」。只有想不到，没有不可能。就好像任意给出一组两字组合，都有可能造出句子一样。当然，理论上如此，但实际上还是有概率的高低之分。有些转移的概率高，如「我们」「中国」这种常用词语，有些转移概率极低，如「我圳」「天塑」等，这些估计很难想出是哪此词语的连接。对于那些一辈子可能都用不到的转移概率就可以统一给定一个默认值，这样又可以删除矩阵中的大量元素。那么，这种删除的依据是什么呢？这取决于生成词库的语料有多大。就一阶而言，在我的测试中，删除了转移中当前状态不足10次的转移、前一状态总共不足80次的转移，以及转移概率小于 $3\times 10^{-4}$ 的转移。具体代码如下：
for f in list(transition_one.keys()):
sum = 0
for t in list(transition_one[f].keys()):
if transition_one[f][t] < 11:
del transition_one[f][t]
for t in list(transition_one[f].keys()):
sum += transition_one[f][t]
if sum <= 80:
del transition_one[f]
continue
else:
for t in list(transition_one[f].keys()):
if (float(transition_one[f][t]) / float(sum)) < 3e-04:
del transition_one[f][t]
就二阶而言，删除了转移中当前状态不足10次的转移、前一状态总共不足30次的转移，以及转移概率小于 $1\times 10^{-2}$ 的转移。具体代码如下：
for fm in list(transition_two.keys()):
sum = 0
for t in list(transition_two[fm].keys()):
if transition_two[fm][t] < 11:
del transition_two[fm][t]
for t in list(transition_two[fm].keys()):
sum += transition_two[fm][t]
if sum <= 30:
del transition_two[fm]
continue
else:
for t in list(transition_two[fm].keys()):
if (float(transition_two[fm][t]) / float(sum)) < 1e-02:
del transition_two[fm][t]
经过上面两种方法的优化，一阶转移矩阵占用空间控制在了 40M 以内，二阶转移矩阵的空间占用控制在了 160M 左右，基本达到了可以接受的范围。当然，这和百度搜狗等还有很大差距，毕竟人家是大公司，还有云词库。
时间与准确的权衡
拼音的整句识别，准确肯定是第一要求，是最重要的指标，没有准确一切都没有意义。如果只是准确这一个目标，那二阶维特比算法已经算是基本可用了。但如果将算法用在输入法中，只是准确就显得不够了。
输入法应用场景下的时间成本
输入法是一个特殊的应用环境，打字人想要的体验是按下键盘，马上就有反应，而不是要等一下才能看到结果。用专业一点的语言叫「上屏速度」一定要快。这个速度要达到用户基本感觉不出来的水平。换句话说就是，不能让用户感觉出是经过大量计算后得到的结果。而应该是和打英文字母差不多快才行。面对打字速度越快的用户，这种要求就会越高。
要快到什么程度，用户才会感觉不出来呢？一般来说，至少要在200毫秒以内，即0.2秒。最好是能控制在100毫秒以内。
那么，直接将上面提到的维特比算法用在整句识别中，一次计算需要多长时间呢？当然，这受到多种因素的影响，包括CPU性能，存储方式，拼音串长度，以及拼音串中包含哪些音，计算时保留几条路径，等等。平均而言，在一台不太慢的机器上，15个音的识别，大概需要1到2秒。可以想像一下如果应用在输入中会是一种什么体验。
分析一下时间的消耗源不难发现，用时最多的并不是计算本身，而是数据查询。而且，数据查询的时间消耗并不是因为检索算法不好，而是因为查的次数太多。毕竟检索用的都数据库的B+树，时间复杂度是 $O(1)$ 的。
不算五个音调的区别，中文共有400多个发音，即使只考虑3500多个常用汉字，平均每个音也有近10个汉字。若按此平均值计算，一个包含10个音的拼音串，将有 $10^{10}$ 条路径。即使计算过程只考虑5条最优的，一次识别也计算了近500条路径。按运气最好的情况算，每条路径至少也需要一阶和二阶矩阵各查一次，共计最少需要查询1000次以上。如果是遇到重码较多且每回都需要查两遍的倒霉情况，一个包含15-20个音的识别，大概需要查询1万到2万次，比如包括「shi」「ji」「fu」等这些重码较多的音。其中，「shi」有55个汉字，「ji」有57个汉字「fu」有46个汉字。
这成千上万次查询如果全在内存中操作也还能勉强接受。但那么，输入法将占用200M的内存甚至更多的内存，这显然是不能接受的。因此，只能将词库放在数据库中，最常用的本地数据库就是sqlite了。做一个简单的测试就会知道，sqlite查询1000的时间大约是300毫秒。如果是1万次，就需要2-3秒。如果一个输入法按下一个字母，2 秒后才能看到要输入的内容，这种输入法肯定也不会有用户了。
优化一：建立存在转移的数据库
查询次数过多的一个原因就是重码过多，即一个音对应的可能状态太多。仔细分析不难发现，我们更需要的是能和前一个字存在较高转移可能的字。其他不可能存在转移的字会因概率较低而在后续的计算中被抛弃。因此，查询和计算这些状态就是一种浪费。比如，「ji」这个音有57种可能，但如果前一个状态是「立」，而和「立」存在一阶转移的「ji」则有「即基机鸡纪集及极技计济」这11个。当然，其他字在理论上也是有可能的，只是概率较低，已经在空间复杂度的优化中将其删除了。
为了能有的放矢的进行查询，就需要建立一个从字到音存在转移的数据库。该数据库可包含两个字段，「字+音」为索引字段，「可能的状态字符串」为待查询的字段。这样，在每次查询时，先检索该数据库，获得当前观测「音」的所有可能状态，然后再进行计算。这样平均可节省近一半的时间消耗。
如果使用一阶的可能转移数据库，是不是也需要建立一个二阶的呢？答案是否定的。第一，由于二阶的数据比一阶的稀松，这个数据库可能会占用很大的空间，大约和二阶转移矩阵的大小差不多。第二，二阶存在的前提是一阶一定存在，所以当一阶转移不存在时，二阶自然不用再查询。第三，一阶存在的都已经是重要是转移，这些重要的转移二阶存不存在都要查。
优化二：合并查询，减少数据库IO
查询次数过多的第二个原因是使用了二阶模型。因此，在不优化的情况下，最坏时，每一个可能的状态需要进行 4 次查询，即 4 次数据库IO。①检索一阶转移的概率。②一阶转移不存在，则检索前一状态到当前音的默认转移概率。③检索二阶转移概率。④二阶转移不存在，则检索前两状态到当前音的默认转移概率。即使考虑到一阶不存在，二阶必然不存在，最少也要检索两次，多的时候需要检索三次。由此可见，如果每一种可能状态所需的概率，可以通过一次IO得到，那么，在理论上就可以减少一半的查询量，可能提高50%以上的速度。
以「对不起」为例，先来看看最普通的SQL查询方式。
假设一阶转移概率矩阵的表（ONE）类似如下结构：
| ID | Weight |
|---|---|
| 不default | 2.213e-7 |
| 不起 | 0.0085 |
| 不其 | 0.0003 |
| 不期 | 0.0004 |
| 不齐 | 0.0005 |
假设二阶转移概率矩阵的表（TWO）类似如下结构：
| ID | Weight |
|---|---|
| 对不default | 4.2112 |
| 对不住 | 0.0302 |
| 对不对 | 0.0488 |
| 对不起 | 0.2814 |
| 对不上 | 0.0107 |
当看到前两个状态是「对不」，且当前音为「qi」时，查询「起」字的转移概率，就会涉及到下面四个SELECT：
SELECT WEIGHT FROM ONE WHERE ID = '不起'
SELECT WEIGHT FROM ONE WHERE ID = '不default'
SELECT WEIGHT FROM TWO WHERE ID = '对不起'
SELECT WEIGHT FROM TWO WHERE ID = '对不default'
第一条查询从「不」到「起」的概率，如果有，就用第三条查询从「对不」到「起」的概率，如果有就可以开始计算加权概率了。
如果一阶查不到，那就要用第二条查询从「不」到所有其他状态的默认概率，然后开始计算加权概率。
如果一阶查到，但二阶没有从「对不」到「起」的转移概率，就需要用第四条查询从「对不」到其他所有状态的默认概率。
总之，不管遇到什么情况，查两次是必须的。
那么，如何才能一次把所有从「对不」到「起」可能用到的转移概率都获取呢？最容易想到的应该是存储过程了。然而，可惜的是，sqlite这种小型的本地数据库并不支持。第二个能想到的就是视图，可考虑通过把表ONE和表TWO建立连接的方式，实现一次查询。比如，把表TWO的ID字段的后两个字符与表ONE相同的连接起来，这需要用到SUBSTR函数：
CREATE VIEW ONE_TWO AS SELECT ONE.ID AS ONE_ID, ONE.WEIGHT AS ONE_WEIGHT, TWO.ID AS TWO_ID, TWO.WEIGHT AS TWO_WEIGHT FROM ONE, TWO WHERE ONE.ID==SUBSTR(TWO.ID,2,2)
这样大概可以得到类似下面的视图：
| ONE_ID | ONE_WEIGHT | TWO_ID | TWO_WEIGHT |
|---|---|---|---|
| 不起 | 0.0085 | 对不起 | 0.2814 |
这样已经可以初步的实现一次查询出两个关键的转移概率，已经可以满足当一阶二阶转移都存在的情况，而且速度也还不错。而且，对于一阶二阶都不存在情况，也可以查到两个默认值。
然而，比较麻烦是，如果一阶存在，二阶不存在。如果想在能查到「不起」的同时，还能查到「对不default」，这可能就需要建立一个从表TWO到表ONE的左连接，而不是内连接了。可惜的是，这样的视图将非常之大，大到查询的速度会变的相当慢。
为了实现一次IO的目标，后来甚至还考虑过使用UNION来拼接表，但最终都失败了。至此，想用视图来解决该问题的设想已经无路可走。
在想要放弃的时候，抱着试一试的心态做了一回直接在两个表查询：
SELECT ONE.ID AS ONE_ID, ONE.WEIGHT AS ONE_WEIGHT, TWO.ID AS TWO_ID, TWO.WEIGHT AS TWO_WEIGHT FROM ONE, TWO WHERE ONE.ID='不起' AND TWO.ID ='对不起'
上面这个查询涉及到两个表，但并没有进行表接连，而且查询的条件还用AND进行连接。本以为这样的查询得不到想要的结果，但没想到，居然成功的查询需要的记录，而且是仅有一条。
那么，如何能同时查询没有转移时的默认值呢？在上面这个SQL语句的基础上其实就很容易实现了。只需要增加两个查询条件即可：
SELECT ONE.ID AS ONE_ID, ONE.WEIGHT AS ONE_WEIGHT, TWO.ID AS TWO_ID, TWO.WEIGHT AS TWO_WEIGHT FROM ONE, TWO WHERE ONE.ID IN ('不起', '不default') AND TWO.ID IN ('对不起', '对不default')
这样，最多一次可以查询到4条记录，即一阶、一阶默认、二阶和二阶默认。此时已经成功了99%。剩下的1%是一种特殊情况。在具体的测试中发现：当二阶转移的前置条件不存在时（如上例中的「对不」整个都不存在），自然就不存在「对不default」这个记录，那么整个表TWO就等于没有任何符合规则的记录，这直接导致查询结果为空，不论一阶转移是否存在。
为了避免这一问题，在表TWO中插入一条记录「ID」为「-」。
并将「-」放入表TWO的查询条件中。
SELECT ONE.ID AS ONE_ID, ONE.WEIGHT AS ONE_WEIGHT, TWO.ID AS TWO_ID, TWO.WEIGHT AS TWO_WEIGHT FROM ONE, TWO WHERE ONE.ID IN ('不起', '不default') AND TWO.ID IN ('对不起', '对不default','-')
这样，根据不同的情况，一次最多可以查到6条记录。如果不存在一阶的转移，就只有3条记录，即没有ONE_ID为「不起」的记录。二阶的情况与此类似。
| ONE_ID | ONE_WEIGHT | TWO_ID | TWO_WEIGH |
|---|---|---|---|
| 不default | 2.21e-7 | - | 0.0001 |
| 不default | 2.21e-7 | 对不default | 4.21e-5 |
| 不default | 2.21e-7 | 对不起 | 0.2814 |
| 不起 | 0.0085 | - | 0.0001 |
| 不起 | 0.0085 | 对不default | 4.21e-5 |
| 不起 | 0.0085 | 对不起 | 0.2814 |
到这里已经基本成功了。不过在操作中还可以再进一步。从上面6条记录可以看到，真正需要的只是最后一条。而且，若二阶不存在，那么记录 3 和 6 将没有，需要的仍然是最后一条记录。若二阶转移的前置条件都不存在，那么记录 2、3、5、6 将没有，但需要的仍然是最后一条记录。若连一阶都不存在，那就只剩下记录1，此时仍然是需要最后一条。
上面这个查询是按 ONE_ID 和 TWO_ID 的升序排列。所以，只要按降序排列，取第一条记录即可。本来还想用类似 SQL 中 TOP 语法的 LIMIT。但测试中发现，LIMIT 的效率极低，不清楚背后的原因。最后选择取到第一条记录就跳出循环。
关于查询的优化还有一点要提。在优化中，也曾经试过把表 ONE 和表 TWO 合并起来。这样就可以在一个表中完成查询，也能做到一次IO。但这种处理方式在筛选数据时相对麻烦，需要把查到的记录全部读出才能选择。所以，在速度上还是差一些。
优化三：提前剔除权重过小的路径
最后，还有一个小大不小的优化。说其不大不小，是因为在某些情况下可以大幅度提高效率，但在某些时候也可能基本上没有效果。
在维特比算法每次保留的最优路径中（比如5条），如果有一条路径的概率比最高的80%还低，那么，基本可以预期，其后不论会有多高概率的状态出现，都很难再改变其被抛弃的结果。因此，还不如早早抛弃，避免查询带来的时间消耗。
当然，至于是抛弃小于最高的 80% 的路径，还是抛弃小于最高的 50% 的路径，这就取决于语料库的情况了。
经过上面三个方面的优化，在iPhone 6s上，对于 20 个字以内的整句识别，其速度基本可以控制在 200 毫秒以内，总算是达到基本可用的要求。当然，过多的抛弃路径和删除词库，是会在一定程度上导致准确率的下降。这些问题就只能通过慢慢的优化词库来解决了。
尾巴
许多算法是公开的，甚至是有开源代码的。如果只是为了学习，这些算法和代码应该已经足够了。但如果要在特殊场景下应用，增加了时间和空间的要求，那么，简单粗暴的使用这些算法可能并不能另人满意。这些感觉上并不复杂的东西，当不断追求细节上的极致时，将会变得越来越难。
