自制输入法：拼音输入法与HMM

拼音输入法

输入法的基本功能是将键盘输入序列映射到另一种文字序列，例如键盘按下nihao这五个键，程序输出汉字“你好”。中文用户最常用的输入法应该是拼音输入法，现在来试试用Python写一个最简单的拼音输入法。

# 首先找一本汉字字典，然后把这个字典变成Python中的字典（

code_table = {
  'a': ['啊']
  'ai': ['爱', '艾', '哎'],
  # ...
}

用户每输入一个拼音，就在这个字典里查找对应的字，然后让用户从这个汉字列表里面选一个。这个输入法一次只能打一个字，如果要打词语，打句子呢？再去找汉语词典、成语词典、歇后语大全，然后把这些信息通通存起来吗？这是个办法，但是我们无法穷尽所有可能的中文组合，总会有不在数据库中的句子或词组，如何创造一个当前数据库中没有的句子或词组呢？可以先将用户输入的拼音拆分，找出所有在现有数据库中存在的单字或词语，然后做一个排列组合。问题是，汉字存在大量的同音字，因此拼音输入法的重码率非常高，例如ni可能对应了几十个汉字，拼音序列越长，可能的组合就越多，能不能把最有可能的组合排在前面？

隐马尔可夫模型（Hidden Markov Model, HMM）

这部分的介绍是ChatGPT帮忙写的，建议读者阅读一些相关文章，如一文搞懂HMM^[1]

当我们在输入汉字时，汉字之间的关系是非常重要的。我们可以认为汉字之间存在着“亲缘关系”，有些汉字之间“关系很近”，例如在一篇文章中，“我”字的后面很可能是“的”字，“的”字的后面很可能是“是”字，这种关系称为二元关系。

HMM是一种能够建模序列数据的统计模型，能够考虑当前时刻的可见状态（拼音）和上一个时刻的隐含状态（汉字）之间的关系。在拼音输入法中，我们可以利用HMM来学习汉字之间的“亲缘关系”，并且根据输入的拼音序列来预测最有可能的汉字序列。

具体地说，在HMM中，我们使用一个二元模型来建模汉字之间的关系。在二元模型中，每个汉字只和它的前一个汉字有关，也就是说，每个汉字的出现概率只与它的前一个汉字出现的概率有关。这种模型非常适合用于建模汉字之间的“亲缘关系”。

通过训练HMM模型，我们可以学习汉字之间的转移概率和汉字对应拼音的概率。这些概率可以帮助我们预测给定拼音序列的最有可能汉字序列。因此，在拼音输入法中，我们可以使用HMM来帮助我们生成最有可能的汉字序列，从而实现自然的中文输入。

训练HMM

假设现在有一些原始中文语料（例如所有中文维基百科的词条文本），如何训练一个隐马尔可夫模型呢？首先我们要解决什么问题呢，就是对于一个给定的拼音序列（可见状态链），我们知道有多少种隐含状态（可能的汉字），知道每一个汉字出现在另一个汉字后面的概率（转换状态），知道汉字对应的拼音的概率（输出概率），求最有可能的汉字序列（隐含状态链）。

根据我们的需求，开始训练HMM，首先可以把文章分割成一个个的句子，给每一个字都标注上拼音。遍历每一个句子，计算以下信息：

• 初始概率I(W1)：每个字W1出现在句子开头的概率，等于出现的次数/所有句子数
• 转换概率T(W1 -> W2)：每个字W1的下一个字是字W2的概率，等于W1后是W2的次数/W1后是任意字的次数
• 输出概率E(W -> Y1)：每个字W的可能的拼音Y1的概率，等于字拼音为Y1的次数/字出现次数，不是多音字的话，这个概率就是1

简化模型

由于汉字和拼音的数量很多，为了简要说明，在这里我假设中文的世界里只有三个拼音，九个汉字：

from collections import defaultdict

w1 = '你', '泥', '尼'
w2 = '号', '好', '毫'
w3 = '压', '鸭', '呀'

init_prob = {
    '你': 0.6, '泥': 0.3, '尼': 0.1
}

trans_prob = {
    '你': {
        '号': 0.1,
        '好': 0.7,
        '毫': 0.2,
    },
    '泥': {
        '号': 0.3,
        '好': 0.3,
        '毫': 0.4,
    },
    '尼': {
        '号': 0.4,
        '好': 0.3,
        '毫': 0.3,
    },
    '号': {
        '压': 0.2,
        '鸭': 0.2,
        '呀': 0.6,
    },
    '好': {
        '压': 0.1,
        '鸭': 0.2,
        '呀': 0.7,
    },
    '毫': {
        '压': 0.3,
        '鸭': 0.3,
        '呀': 0.4,
    },
}

# 没有多音字，就默认输出概率emiss_prob[字][拼音]全为1
emiss_prob = defaultdict(lambda: defaultdict(lambda: 1))

暴力求解

对于一个拼音序列['ni', 'hao', 'ya']，我们可以先根据每一个拼音对应的所有的可能的字，得出所有可能的汉字序列（隐含状态链），然后我们对每一个可能的隐含状态链，求这个隐含状态链得到相应的可见状态链（确定的拼音序列）的概率，给出概率最大的那个隐含状态链就可以了。设这个概率为P，在这个例子里P等于I(W1) * E(W1 -> 'ni') * T(W1 -> W2) * E(W2 -> 'hao') * T(W2 -> W3) * E(W3 -> 'ya')。例如对于“你好呀”三个字，概率P为“你”字出现在句子开头的概率，乘以“你”的拼音是“ni”的概率，乘以“你”的下一个字是“好”的概率，乘以“好”的拼音是“hao”的概率，乘以“好”的下一个字是“呀”的概率，乘以“呀”的拼音是“ya”的概率。

import itertools


def count_prob(group):
    (c1, c2, c3) = group
    prob = init_prob[c1] * emiss_prob[c1]['ni'] * trans_prob[c1][c2] * emiss_prob[c2]['hao'] * trans_prob[c2][c3] * emiss_prob[c3]['ya']
    return (prob, ''.join(group))

result = sorted([count_prob(i) for i in itertools.product(w1, w2, w3)], key=lambda x: x[0], reverse=True)
for i in result:
    print(f"text: {i[0]} prob: {i[1]}")

"""
result:
text: 0.294 prob: 你好呀
text: 0.084 prob: 你好鸭
text: 0.063 prob: 泥好呀
text: 0.054 prob: 泥号呀
text: 0.048 prob: 你毫呀
text: 0.048 prob: 泥毫呀
text: 0.042 prob: 你好压
text: 0.036 prob: 你号呀
text: 0.036 prob: 你毫压
text: 0.036 prob: 你毫鸭
text: 0.036 prob: 泥毫压
text: 0.036 prob: 泥毫鸭
text: 0.024000000000000004 prob: 尼号呀
text: 0.020999999999999998 prob: 尼好呀
text: 0.018 prob: 泥号压
text: 0.018 prob: 泥号鸭
text: 0.018 prob: 泥好鸭
text: 0.012 prob: 你号压
text: 0.012 prob: 你号鸭
text: 0.012 prob: 尼毫呀
text: 0.009 prob: 泥好压
text: 0.009 prob: 尼毫压
text: 0.009 prob: 尼毫鸭
text: 0.008000000000000002 prob: 尼号压
text: 0.008000000000000002 prob: 尼号鸭
text: 0.006 prob: 尼好鸭
text: 0.003 prob: 尼好压
"""

维特比算法

暴力求解的方法对于拼音序列比较短的情况还可以接受，但是对于长度较长的拼音序列，可能性的组合数会非常大，计算复杂度会指数级增长，因此需要一种高效的算法来解决这个问题。现在再一次回顾一下暴力求解的过程，只是这次分三步来算:

prob_map = {}

# 首先让拼音序列只有“ni”，对应的只有w1这三个可能的汉字
count = 0
for c in w1:
    prob_map[c] = init_prob[c] * emiss_prob[c]['ni']
    count += 1

print(prob_map)
print(f"计算次数：{count}")

# 现在拼音序列加上“hao”，对应的可能的汉字数量为w1和w2的笛卡尔积，有9种可能
count = 0
for (c1, c2) in itertools.product(w1, w2):
    prob_map[f"{c1}{c2}"] = init_prob[c1] * emiss_prob[c1]['ni'] * trans_prob[c1][c2] * emiss_prob[c2]['hao']
    count += 1

print(prob_map)
print(f"计算次数：{count}")

# 第三步，拼音序列加上“ya”，对应的可能的汉字序列有27种可能
count = 0
for (c1, c2, c3) in itertools.product(w1, w2, w3):
    prob_map[f"{c1}{c2}{c3}"] = init_prob[c1] * emiss_prob[c1]['ni'] * trans_prob[c1][c2] * emiss_prob[c2]['hao'] * trans_prob[c2][c3] * emiss_prob[c3]['ya']
    count += 1

print(prob_map)
print(f"计算次数：{count}")

"""
result:
{'你': 0.6, '泥': 0.3, '尼': 0.1}
计算次数：3
{'你': 0.6, '泥': 0.3, '尼': 0.1, '你号': 0.06, '你好': 0.42, '你毫': 0.12, '泥号': 0.09, '泥好': 0.09, '泥毫': 0.12, '尼号': 0.04000000000000001, '尼好': 0.03, '尼毫': 0.03}
计算次数：9
{'你': 0.6, '泥': 0.3, '尼': 0.1, '你号': 0.06, '你好': 0.42, '你毫': 0.12, '泥号': 0.09, '泥好': 0.09, '泥毫': 0.12, '尼号': 0.04000000000000001, '尼好': 0.03, '尼毫': 0.03, '你号压': 0.012, '你号鸭': 0.012, '你号呀': 0.036, '你好压': 0.042, '你好鸭': 0.084, '你好呀': 0.294, '你毫压': 0.036, '你毫鸭': 0.036, '你毫呀': 0.048, '泥号压': 0.018, '泥号鸭': 0.018, '泥号呀': 0.054, '泥好压': 0.009, '泥好鸭': 0.018, '泥好呀': 0.063, '泥毫压': 0.036, '泥毫鸭': 0.036, '泥毫呀': 0.048, '尼号压': 0.008000000000000002, '尼号鸭': 0.008000000000000002, '尼号呀': 0.024000000000000004, '尼好压': 0.003, '尼好鸭': 0.006, '尼好呀': 0.020999999999999998, '尼毫压': 0.009, '尼毫鸭': 0.009, '尼毫呀': 0.012}
计算次数：27
"""

可以发现，最终的概率是一个乘法运算的结果，根据我小学数学的知识，如果两个正数相乘，那这两个数越大，结果就应该越大。如果说我们在第二步计算的时候，不再考虑所有的排列组合，而是直接把第一个字固定为上一步求出来的概率最大的“你”，是不是就能保证结果是最大的呢？毕竟只要是正数相乘（这里的概率显然都是正数），那么乘上一步的最大值，一定比乘上一步不是最大的值得到的概率值要大！

现在来介绍一下维特比算法，维特比算法是一种动态规划的算法，可以在计算量相对较小的情况下，得到概率最大的隐含状态链。维特比算法的思路是，对于每个时刻，计算到达该时刻的所有隐含状态链中概率最大的那一个，直到计算到最后一个时刻，得到最终的概率最大的隐含状态链。

具体地，我们定义一个矩阵V，其中V[t][i]表示在时刻t，隐含状态为i的最大概率（也就是到达状态i的所有路径中概率最大的那一条路径的概率），然后逐个时刻进行计算，直到计算到最后一个时刻，得到概率最大的隐含状态链。

计算方法如下：

1. 在t=1时刻，对于每个隐含状态i，令V[1][i] = I(W1) * E(W1 -> yi)；
2. 在t>1的时刻，对于每个隐含状态i，计算V[t][i]：

V[t][i] = max(V[t - 1][j] * T(j -> i) * E(i -> yi))

其中max操作表示求最大值，j表示上一个时刻的隐含状态，T(j -> i)表示从j状态到i状态的转移概率，E(i -> yi)表示i状态对应的汉字输出为yi拼音的概率。最后，在所有时刻中，找到概率最大的隐含状态链。

obs = ['ni', 'hao', 'ya']

V = { k: {} for k in range(len(obs))}
# 加一个look back方便回溯
look_back: list[tuple[float, str]] = [ (0, '') for _ in obs ]

count = 0

# 时刻0
t = 0
for c in w1:
    prob = init_prob[c] * emiss_prob[c]['ni']
    V[t][c] = prob
    if prob > look_back[t][0]:
        look_back[t] = (prob, c)
    count += 1

t += 1
# 时刻1
for (pinyin, words) in zip(obs[1:], (w2, w3)):
    for c in words:
        (prev_max_prob, prev_state) = look_back[t - 1]
        cur_prob = prev_max_prob * trans_prob[prev_state][c] * emiss_prob[c][pinyin]
        V[t][c] = cur_prob
        if cur_prob > look_back[t][0]:
            look_back[t] = (cur_prob, c)
        count += 1

    # 时刻+1
    t += 1

print(f"V：{V}")
print(f"最可能的隐状态链：{[c for (_, c) in look_back]}")
print(f"最大概率：{look_back[-1][0]}")
print(f"结果字符串：{''.join(c for (_, c) in look_back)}")
print(f"计算次数：{count}")

"""
result:

V：{0: {'你': 0.6, '泥': 0.3, '尼': 0.1}, 1: {'号': 0.06, '好': 0.42, '毫': 0.12}, 2: {'压': 0.042, '鸭': 0.084, '呀': 0.294}}
最可能的隐状态链：['你', '好', '呀']
最大概率：0.294
结果字符串：你好呀
计算次数：9
"""

可以发现循环的次数比暴力解法要少，维特比算法的时间复杂度为O(T * N^2)，暴力解法的时间复杂度是O(N^T)，其中T是时刻数（拼音序列长度），N是隐含状态数（拼音对应汉字数），拼音对应的汉字状态数不会太多，因此当拼音序列越长的时候，暴力解法的时间复杂度就随指数级别增长，相比之下维特比算法就更高效了。