使用HMM【隐马尔科夫模型】实现简单拼音输入法

问题导读：
1、什么是隐马尔科夫模型？
2、如何通过拼音推测汉字？
3、如何理解前向概率Viterbi算法？

之前写过一篇使用语言模型进行中文分词的博客，本篇在之前写的语言模型的基础上，通过隐马尔科夫模型实现简单的拼音输入法，即输入一组拼音，我们把它转换成中文。

一、隐马尔科夫模型

首先我们来说一下什么是马尔科夫链，简单的说，任何一组我们可以观察到的连续序列，比如连续一个星期的天气状况，都可以称为马尔科夫链。

马尔科夫链的最主要特性是，假设当前节点的状态（比如今天的天气），只与之前N个连续状态相关（比如之前一个星期的天气状况），通过这个性质和大量的统计，我们就可以根据最近几天的天气预测未来一天的天气了。
那么什么是隐马尔科夫模型呢？

比如你有一个朋友在美国，他会每天告诉你他今天做了什么（打球、跑步或呆在家里），你要通过他的这些活动推测过去一周内他们那边的天气。这里你朋友的活动对你来说是可以观察到的，即观察序列，而过去一周的天气是隐藏序列，那么这个通过观察序列推测隐藏序列的模型，就是隐马尔科夫模型。

隐马尔科夫模型的“隐”就体现在“隐藏序列”这个概念里。

二、通过拼音推测汉字

很明显，我们的拼音输入法的观察序列就是用户的输入拼音，比如”wo shi zhong guo ren”，我们要推测出用户想要输入的是“我是中国人”，这是个很典型的隐马尔科夫模型：

如上图所示，我们根据给定的观察对象O，获得一个概率最大的序列S*。我们所知道的数据有：

1, 所有观察对象的值

2, 隐藏序列的马尔科夫模型概率，这是通过统计获得的

3, 隐藏状态到观察状态的概率，比如 “晴天”(隐藏状态) 到 “出去玩”(观察状态)的概率

我们要求的是S*各个状态的连续概率最大的那个序列。

三、前向概率Viterbi算法

我们把隐藏序列中的一个节点的每一种可能取值都画出来的话，我们会发现这其实是一个有向图寻找最优路径的问题：

H、O、S都是当前节点可能的取值（比如hao拼音可能有好、号、耗等汉字）。而对于这种寻找最优路径的问题，我们可以通过动态规划的思想去考虑，假设σt(k)表示第t个位置对应的汉字是k，s表示隐藏序列，o表示观察序列，M表示当前隐藏节点的可能取值，那么：

上式中的bk(ot+1)

表示从隐藏节点k到观察序列t+1的发射概率，α_{l,k}表示l到k的马尔科夫状态转移概率。

写出了递归式，这个动态规划程序就容易写了。

四、实现

既然我们是一个有向图，那么闲来构造图中的所有节点：
[mw_shl_code=applescript,true]class GraphNode(object):
"""有向图中的节点"""
  def __init__(self, word, emission):
# 当前节点所代表的汉字（即状态）
self.word = word
# 当前状态发射拼音的发射概率
self.emission = emission
# 最优路径时，从起点到该节点的最高分
self.max_score = 0.0
# 最优路径时，该节点的前一个节点，用来输出路径的时候使用
self.prev_node = None
class Graph(object):
  """有向图结构构造器"""
  def __init__(self, pinyins, im):
"""根据拼音所对应的所有汉字组合，构造有向图"""
self.sequence = []
for py in pinyins:
   current_position = {}
   # 从拼音、汉字的映射表中读取汉字及汉字到拼音的发射概率
   for word,emission in im.emission[py].items():
      node = GraphNode(word, emission)
      current_position[word] = node
   self.sequence.append(current_position)[/mw_shl_code]

核心的viterbi算法为：
[mw_shl_code=applescript,true]def viterbi(self, t, k):
"""
   第t个位置出现k字符的概率，记为p_t(k)
"""
if self.get_key(t,k) in self.viterbi_cache:
   return self.viterbi_cache[self.get_key(t,k)]
node = self.graph.sequence[t][k]
if t == 0:
   # 从统计语言模型中获得转移概率
   state_transfer = self.lm.get_init_prop(k)
   # 获得发射概率
   emission_prop = self.emission[self.pinyins[t]][k]
   # 计算当前节点的概率得分
   node.max_score = 1.0 * state_transfer * emission_prop
   self.viterbi_cache[self.get_key(t,k)] = node.max_score
   return node.max_score
# 获得前一个状态所有可能的汉字
pre_words = self.graph.sequence[t-1].keys()
# 对当前节点分贝与前一个节点的所有可能汉字进行计算，获得概率最大的那个
for l in pre_words:
   state_transfer = self.lm.get_trans_prop(k, l)
   emission_prop = self.emission[self.pinyins[t-1]][l]
   score = self.viterbi(t-1, l) * state_transfer * emission_prop
   if score > node.max_score:
      node.max_score = score
      node.prev_node = self.graph.sequence[t-1][l]
self.viterbi_cache[self.get_key(t,k)] = node.max_score
return node.max_score[/mw_shl_code]

由于完整代码牵扯的东西太多，包括语言模型、汉字拼音映射表，这里就不在全部贴出来了，不过有了上面两部分代码，其实其他的也很容易谢了，就是加载进去而已。
输出效果：
[mw_shl_code=applescript,true]ocalhost:HMM roy$ python InputMethod.py
loading words
hashing bi-gram keys
hashing single word keys
zhong wen shu ru fa
中文输入发
ren min ri bao ri ren min
人民日报日人民
zhong hua ren min gong he guo
中华人民共和国
localhost:HMM roy$[/mw_shl_code]
第一组输入的有一个错字，主要是因为语料库不够完善，可能“入法”两个字的概率小于“入发”两个字了，不是大问题。

来源：搜不狐