拼音纠错就是将用户输入的汉语拼音进行纠错,这个貌似说跟没说一个样。打个比方吧,用户输入zhege(这个)的时候,不小心输成了zhrge。这个时候就需要拼音纠错将zhr ge自动识别成zhe ge,因为完整的拼音zh后面不可能跟着r。

最近在看关于HMM模型的书,突然想到拼音纠错问题可以使用HMM来解决。道理很简单,将正确的拼音,比如zhege,作为内部状态序列;将用户的输入,比如zhrge,作为观测序列,建立HMM后使用viterbi算法从观测序列取猜测最有可能的内部序列就实现了纠错的过程。这样就是一个很典型的隐马模型了,每个内部状态都有一定的几率产生正确的或者错误的观测结果,比如内部状态e,有一定几率产生正确的观测结果e,也有可能产生错误的观测结果r,这个就是发射矩阵(Emit Matrix);在拼音中h后面有一定的概率是e,但是后面是r的概率就接近于0了,这个就是HMM里面的转移矩阵(Trans Matrix)。

为了简单的实现用HMM模型实现拼音的纠错,进行三个假设

  • 所有输入的拼音均为完成的拼音,比如zhege,但是zheg或者zge就不是完整的拼音
  • 所有可能出错的按键均为某输入的按键的旁边两个键,比如e只可能错误的输入成r或者w,h只可能错成g或者j
  • 任何汉字的拼音的出现都是独立的,就比如zhe和ge是独立的(虽然现实中是有关系的,zhe后面出现ge的概率很大),相互的出现对彼此都没有影响

有了以上的两个假设,问题解决起来就方便多了。转移矩阵可以从Google输入法的词库文件中训练出来,而发射矩阵需要自己定义,将每个按键本身和旁边两个键的概率自己设定一下就可以了,比如

'b': {'b': prob_t_c, 'v': prob_t_i, 'n': prob_t_i},
'c': {'c': prob_t_c, 'x': prob_t_i, 'v': prob_t_i},
'd': {'d': prob_t_c, 's': prob_t_i, 'f': prob_t_i},
'e': {'e': prob_t_c, 'w': prob_t_i, 'r': prob_t_i},
....

这里的prob_t_c就是正确的概率,prob_t_i就是错误的概率。如果取prob_t_c = 0.8, prob_t_i = (1 - prob_t_c) / 2 = 0.1的话,那么b就有0.8的概率被正确输入,而有0.1的概率分别被错误的输入成v和n。关于prob_t_c到底取多少才是最优的这个问题没有取深究过,不过使用了一组数据小观测了一下在30%错误率情况下取prob_t_c = 0.8效果最佳。

此外,为了解决拼音的切分问题,将可能作为拼音结尾的几个字母分成两种状态。即出现在拼音首部以及中部的状态x,和只出现在拼音尾部的状态x’。其中状态x’的转移概率向量为起始状态(’^’)的转移概率向量,因为这里假设汉字的拼音是独立的,zhe这个拼音结束以后,任何的字母的出现的概率与最开始某字母在拼音首部出现的概率是一样的;x’的发射概率向量与x的发射概率向量是相同的。这样就可以解决拼音的切分问题了。比如shen,从e状态转移到n’状态就表示拼音结束,而从e状态转移到n状态则表示拼音还没有结束。

将HMM模型解决好后,就可以使用viterbi算法根据观测序列取猜测最有可能的内部序列来完成纠错了。

以下是纠错的结果(prob_t_c = 0.8的情况下):

30%单个字母错误率的情况下,1-viterbi算法召回率约为68%,3-viterbi算法召回率约为89%,虽然数据看上去让人很伤心,但是实际上测试数据中包括了大量比如wenguachisnvo这种错的离谱的拼音,就算是人也不能很容易的猜出正确的结果(wen’hua’chuan’bo’)。总体上来说还是不错的。

10%单个字母错误率情况下3-viterbi算法召回率则达到了95%.

如果想再提高正确率的话,简单的办法由两种。第一是使用n>3的n-viterbi算法,第二则是使用阶数更高的HMM模型。不过任何一种带来的时间/空间复杂度的提升都是指数级别的。

相关代码放在了https://github.com/ling0322/hmm-pinyin里面,其中result.txt为10%单个ziu错误概率情况下的运行结果,result2.txt为30%下的运行结果。