自制输入法：拼音输入法与HMM
拼音输入法
输入法的基本功能是将键盘输入序列映射到另一种文字序列，例如键盘按下nihao这五个键，程序输出汉字“你好”。中文用户最常用的输入法应该是拼音输入法，现在来试试用Python写一个最简单的拼音输入法。
# 首先找一本汉字字典，然后把这个字典变成Python中的字典（
code_table = {
'a': ['啊']
'ai': ['爱', '艾', '哎'],
# ...
}用户每输入一个拼音，就在这个字典里查找对应的字，然后让用户从这个汉字列表里面选一个。这个输入法一次只能打一个字，如果要打词语，打句子呢？再去找汉语词典、成语词典、歇后语大全，然后把这些信息通通存起来吗？这是个办法，但是我们无法穷尽所有可能的中文组合，总会有不在数据库中的句子或词组，如何创造一个当前数据库中没有的句子或词组呢？可以先将用户输入的拼音拆分，找出所有在现有数据库中存在的单字或词语，然后做一个排列组合。问题是，汉字存在大量的同音字，因此拼音输入法的重码率非常高，例如ni可能对应了几十个汉字，拼音序列越长，可能的组合就越多，能不能把最有可能的组合排在前面？
隐马尔可夫模型（Hidden Markov Model, HMM）
这部分的介绍是ChatGPT帮忙写的，建议读者阅读一些相关文章，如一文搞懂HMM
当我们在输入汉字时，汉字之间的关系是非常重要的。我们可以认为汉字之间存在着“亲缘关系”，有些汉字之间“关系很近”，例如在一篇文章中，“我”字的后面很可能是“的”字，“的”字的后面很可能是“是”字，这种关系称为二元关系。
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的所有路径中概率最大的那一条路径的概率），然后逐个时刻进行计算，直到计算到最后一个时刻，得到概率最大的隐含状态链。
计算方法如下：
- 在t=1时刻，对于每个隐含状态i，令V[1][i] = I(W1) * E(W1 -> yi)；
- 在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是隐含状态数（拼音对应汉字数），拼音对应的汉字状态数不会太多，因此当拼音序列越长的时候，暴力解法的时间复杂度就随指数级别增长，相比之下维特比算法就更高效了。
实践中的一些问题
以上已经实现了一个维特比算法的核心部分，但是如果真的要做一个可以用的输入法程序，还是存在不少实践上的问题的，未来有空可以再单独写一些文章来谈一谈。
语料处理问题
- 注音不准确
直接从互联网上获取的语料，如维基百科文本、百度贴吧文本，这些中文文本本身是没有拼音标注的，人工一个个去标未免太麻烦，这里可以利用一些汉字转拼音的程序去做，但是有一些多音字比较麻烦，程序生成的未必是正确读音。
- 语料文本太杂
原始语料里可能存在英文、阿拉伯数字混杂的情况，如果直接不处理它们，难免会造成失真，例如“今天8号”，去掉阿拉伯数字，就变成“号”紧跟在“天”字后面了，影响了转换概率的计算。如何去处理它们又是个复杂的问题，例如混在中文中的时间“1070-1138年”、“12:59分”，需要想个办法妥善处理。
真实世界的输入
在算法的核心部分，我们一直把输入的拼音当作一个序列，序列中的每一个元素刚好是一个单字的拼音，然而实际输入法中，用户输入一一串字符串，如“jintiantianqibucuo”，还需要有个办法能把拼音拆分开，拆分的时候也有问题，如“tian”是一个整体还是“ti”和“an”两个拼音呢？
与时俱进
互联网的发展也促进了语言文字的发展，每隔一段时间都会涌现一批新的“热门词条”，是不是要不停地更新语料？语料库越来越大，训练出来的模型参数越来越大，是不是磁盘空间占用，程序的内存占用也会水涨船高？模型的精度是否随着语料库的增长而线性增长？
计算问题
最后一个问题是计算的平滑处理。在维特比算法中，浮点数的计算是一个非常重要的部分。由于计算机的存储精度有限，因此在计算转移概率时需要进行平滑处理，以避免数值上溢或下溢的问题。
除了计算机的存储精度有限之外，还有一些其他原因也会导致计算平滑处理的必要性。
一方面，语言是非常复杂和多变的，不可能完全覆盖所有情况。当我们遇到一些新词或者生僻字时，由于缺乏足够的数据来支持计算，就会出现概率值为0的情况。这时候如果不进行平滑处理，就会导致整个模型的预测结果出现很大的偏差。
另一方面，语料库的大小和质量也会影响到计算平滑处理的必要性。如果我们的语料库比较小，很容易就会出现数据稀疏的情况，导致一些概率值为0。而如果我们的语料库质量较差，比如存在大量的噪声和错误数据，那么这些错误数据也会影响到模型的精度，因此需要进行平滑处理来弥补这些问题。