基于汉字二元模型的拼音输入法实现

已上传gitee：https://gitee.com/wu-xiaonan-18/pinyin_shurufa.git

基本思路

拼音输入

要将输入的全拼转化为汉字，就需要建立“拼音—汉字”的映射关系。考虑到汉字中*“谐音字”*（读音相同或仅有语调不同，下同）数量众多，因此拼音输入法需要有强大的检索预测能力，类似于人在实际语境中会根据上下文来判断拼音对应的汉字，计算机也需要通过文本的前后文环境来找到概率最大的对应汉字，实现预测。

二元模型

现代汉语一大特点为双音节词频极高——据《现代汉语频率词典》统计，使用频率最高的9000词中6285词为双音节词。

针对汉语词汇的双音节化，采用二元模型来预测汉字的输入是适合的，即针对每个拼音，只考虑其前一个字与其的关系，此即一系列的Markov过程，每一个汉字的选择只对后一个汉字有影响。

实际上，在实际语境中，大部分的字也只会和相邻的字产生联系；至于联系较远处的字的影响，在此处先不展开。在当下的汉语环境中，二元模型是合适的。

条件概率与频率近似

考虑单个字，则输出的汉字$x_i$与输入的拼音$y_i$有关系

也即在给定拼音$y_i$的条件下，输出最有可能的汉字$x_i$，一般的，以该谐音字在语料库中的频率来近似概率。 $$ x_i= argmax\\ P(x_i|y_i) $$
考虑两个字，则针对第一个字取$x_1$的情况，取第二个字为$x_2$的概率为 $$ P(x_2|x_1y_2)=\frac{P(x_1x_2y_2)}{P(x_1y_2)} $$ 事件$x_2$包含$y_2$，故 $$ P(x_2|x_1y_2)=\frac{P(x_1x_2)}{P(x_1y_2)} $$ 以$F(x)$表示x字出现的频率（数据库中的次数），则以频率近似概率，有 $$ P(x_2|x_1y_2)=\frac{F(x_1x_2)}{F(x_1y_2)} $$ 此式意为：在第一个字取$x_1$，第二个字的拼音为的$y_2$情况下，第二个字取$x_2$的概率等于汉字$x_1x_2$出现的次数除以“第一个字为$x_1$，第二个字的拼音为$y_2$”这个情况出现的次数。

特别需要注意的是，上式中的$x_1x_2$与$x_1y_2$是事件“两个事件依次发生”，而不可以拆成两个独立事件。
考虑一整句话，在此模型下应通过选择，使得整句话的字出现概率最大，也即 $$ x_1\cdots x_n= argmax\\ P(x_1\cdots x_n|y_1\cdots y_n) $$ 考虑到前字不受后字影响，后字只受前一个字的影响，故概率 $$ \begin{align*}

P(x_1\cdots x_n|y_1\cdots y_n) &=P(x_1|y_1)P(x_2|x_1y_2)\cdots P(x_n|x_{n-1}y_n)\\ &=\frac{F(x_1)}{F(y_1)} \frac{F(x_1x_2)}{F(x_1y_2)}\cdots \frac{F(x_{n-1}x_n)}{F(x_{n-1}y_n)}

\end{align*} $$ 要使该概率最大，则需要选择$x_i$使得上式频率比最大。
考虑到事件$x_1y_2$可能没有出现过，考虑将其平滑化，有 $$ P^*(x_2|x_1y_2)=(1-\alpha) \frac{P(x_1x_2)}{P(x_1y_2)}+\alpha\frac{P(x_2)}{P(y_2)} $$ 其中$\alpha$是人为引入的一个$[0,1]$的系数，一般取得较小，且可以通过训练调整，甚至针对不同的情况，比如对不同的汉字拼音$y_i$引入不同的$\alpha_i$。

综上，需要在给定拼音的情况下逐字搜索，得到整句话最可几的汉字排列。

动态规划-Viterbi算法

按照上述模型，依据拼音串输出汉字串的过程是一个典型的动态规划问题——

最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质；
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关；
子问题重叠性质：指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。

在本问题中，根据前一个字以及本字拼音来确定本字，即为一个一阶的隐式马尔科夫过程。

对于要求的式子 $$ \begin{align}

P(x_1\cdots x_n|y_1\cdots y_n) &=P(x_1|y_1)P(x_2|x_1y_2)\cdots P(x_n|x_{n-1}y_n)\notag\ &=\frac{F(x_1)}{F(y_1)} \frac{F(x_1x_2)}{F(x_1y_2)}\cdots \frac{F(x_{n-1}x_n)}{F(x_{n-1}y_n)}

\end{align} $$

考虑到上述过程中$\frac{F(x_1x_2)}{F(x_1y_2)}$累乘求解比较困难，先化为累加 $$ \begin{align}

P_{-ln}(x_1\cdots x_n|y_1\cdots y_n) &=-ln(P(x_1\cdots x_n|y_1\cdots y_n))\notag\ &=-ln(\frac{F(x_1)}{F(y_1)})-\sum_{i=1}^{n-1} ln(\frac{F(x_ix_{i+1})}{F(x_iy_{i+1})})

\end{align} $$ 进而转化为求$P_{-ln}$的极小值。

同时，由于直接搜索对应开销过大（时间复杂度$O(n^T)$，n为每一个拼音对应的汉字数，T为句子长度），因而采用Viterbi算法：

图中的有向线段的数值代表在前字（比如$x_1$）的条件下一个字为$y_1$的负对数概率，要寻找到一条概率最大的路径，也即$P_{-ln}$最小路径（以下简称最短路径，对应路径值即为概率和）。

假设S到e的最短路径经过$y_1$，则最短路径必然是S到$y_1$的最短路径+$y_1$到e的最短路径，否则用更大的路径替换上述路径，总路径更大。

因此，从前往后计算路径值，只需要依次计算第$T_i$步各点到第$T_{i+1}$步各点的最短路径，不断拼接即可，时间复杂度时间复杂度$O(n^2T)$。

实现过程

汉字、拼音预处理

针对实验涉及的汉字表，由于只有6763个汉字，故考虑直接给所有汉字按照《一二级汉字表》中的顺序标号，而非采用字符串的方式存储，这样查询更加方便。

采用字典存储各个汉字对应的序号（《拼音汉字表》与《一二级汉字表》汉字顺序不同，因《拼音汉字表》中有多音字重复出现，为了统计同音字而以《拼音汉字表》为准建立字典）：

$dict_{char}$ = { “汉字$x_1$”：对应序号$c_{1}$ } 在建立汉字序号字典时不考虑多音字
- key = char “$x_1$”，value = int $c_{1}$
$dict_{pinyin}$ = {“$y_1$”，同音字“$x_{11}x_{12}\cdots x_{1n}$”对应的汉字序号 $[c_{11},\cdots c_{1n}]$
- key = string “$y_1$”，value = list $[c_{11},\cdots c_{1n}]$

语料预处理

对于语料库，编写函数读取文件夹下文件名，并依次打开文件读取内容。

对于读取的内容，采用正则表达式以空格替换非汉字后，采用空格分隔语料

one_line = re.sub('([^\u4E00-\uF7FE])', ' ', text[line_i]).split()

对于语料库中出现的词组，建立概率数据库。

用list来存储首字、尾字的频率（尾字用来平滑处理，实际上与单字频率几乎一致）。考虑到语句中的第一个字是一个词语的首字，可能因词语在句中位置不同而在句中各个位置出现，但不可能作为最后一个字出现（否则语义上也不是首字）。

程序改进前统计每句话的非最后一字作为首字概率。

改进后引入jieba分词，将语句处理为各个词语后统计词语首字，以此获得更准确的首字概率。

def jieba_split(str_list):

    # 把list化为str会多出许多分隔符号
    sen_str = str(str_list)
    # replace替换"["、"]"、" "、"'"
    sen_str = sen_str.replace("[", "").replace("]", "").replace("'", "").replace(",", "").replace(" ", "")
    sen_jieba = jieba.cut(sen_str, cut_all=False)
    sen_list_jieba = ' '.join(sen_jieba).split()
    return sen_list_jieba

数据结构如下

$list_{first_hanzi}[1]=n_{1}$ { “汉字$x_1$”作为非句中最后一字出现的次数$n_{1}$ }
- int $n_{1}$
$list_{last_hanzi}[2]=n_{2}$ { “汉字$x_2$”作为次字出现的次数$n_{2}$ }
- int $n_{2}$

考虑到汉字个数较少，二字词组的规模也不大，故考虑采用二维矩阵来存储汉字词组“$x_1x_2$”出现的频率

$list_{words}[1][2]=n_{12}$ { “汉字词组$x_1x_2$”出现的次数$n_{12}$ }
- int $n_{12}$

注：

采用二维矩阵存储汉字词组，先在字典上搜索汉字$x_1x_2$对应数字，耗时O(logn)；再在list上找到对应值，耗时O(1)，总耗时O(logn)；

对比采用字典来存储汉字词组的方案，由于字典采用散列存储，故字典法先搜索首字$x_1$，耗时O(logn)；再搜索末字$x_2$，耗时O(logn)，总耗时O(logn)。

两种方法时间复杂度相同，而二维矩阵更加直观，相比起来字典法节省的空间开销（因为诸多汉字之间不存在一起出现的情况）并不多，故采用二维矩阵的数据结构来存储词频。

再将$list_{words}$的频数归一化，即将出现次数n替换为$p_{12}=\frac{n_{12}}{\sum_i n_1n_{2i}}$，那么概率 $$ \begin{align}

P(x_2|x_1y_2) &=\frac{F(x_1x_2)}{F(x_1y_2)}\notag\ &=\frac{F(x_1x_2)}{\sum_i F(x_1x_{2i})}\notag\ &=p_{12} \end{align} $$

$list_{words}[1][2]=n_{12}$ { “汉字词组$x_1x_2$”出现的次数$n_{12}$ } float $p_{12}$

平滑处理，最后取负对数，将[0,1]的概率值转化为了非负的（实际上恒正的），概率越大对应的“距离”越远的路径值。概率若为0则取float(“inf”)。

这种处理方式是将所有的字到字的转移概率都记录在表，后续计算动态规划时只需要查表，是一种牺牲预处理时间，换取计算时间的方法；同时，这种方法也会导致多音字的转移概率对应不上（但实际上影响较小）。

转移矩阵

对于每个字$x_1$以及其后继$x_2$，遍历$x_2$的拼音对应字后，查询$list_{words}$,可以得到转移矩阵

$p_{11}$	$p_{12}$	$\cdots$	$p_{1n}$
$p_{21}$	$p_{22}$	$\cdots$	$p_{2n}$
$\cdots$	$\cdots$	$\cdots$	$\cdots$
$p_{11}$	$p_{11}$	$\cdots$	$p_{mn}$

对应图中的路径值。

动态规划

对于句长为$T$的拼音句，从首字概率出发，需要经过$T-1$步计算到最后一个字。

其中，每一步计算的字$x_1x_2$，都将字$x_{1i}$的路径值与字$x_{2i}$的路径值相加，对每个字$x_{2i}$取最小值，比如上图中取$y_{1}$的路径值为$min{3+5, 4+7}=8$，并记录每个字取最小值时的先驱（即前一个字的序号），便于回溯路径。

最后得到将路径值最小的路径，倒序推出路径，对照汉字表，即可输出汉字句子。

实验环境

编程语言：python 3.7.0

配置了Anaconda 4.5.11

依赖库

库	版本
numpy	1.21.6
scipy（查看稀疏矩阵用，与代码内容无关）	1.1.0
jieba	0.42.1

文件架构

架构

本次作业文件架构如下：

——|corpus

语料库，其中新浪新闻未打包提交

————|十九大.txt

————|二十大.txt

————|2016-02.txt（未上传）

————|...

————|2016-11.txt（未上传）

——|data

数据文件夹，存放测试文件

————|input.txt

————|output_std.txt

————|output.txt

——|src

源文件，存放汉字、拼音表；中间的训练文件（pkl格式）；python源代码

————|拼音汉字表

————|一二级汉字表

————|dict_char.pkl

————|dict_pinyin.pkl

————|list_first_hanzi.pkl

————|list_words.pkl（300+MB，未上传）

————|preprocess.py

————|get_output.py

————|statistics.py

——|pic

markdown文件的存放图片文件夹

——|README.md

使用说明

python源代码主要包含三个.py文件，preprocess文件进行预处理，get_output根据data文件夹中的input文件计算得到output文件，statistics文件统计输出结果的正确率等信息。

运行preprocess得到词概率表等数据，再运行get_output得到输出结果，最后运行statistics，在命令行打印正确率等统计信息。

数据与语料库

汉字序号字典

按照《一二级汉字表》中的汉字顺序为6763个汉字编号

（《拼音汉字表》与《一二级汉字表》汉字顺序不同，因《拼音汉字表》中有多音字重复出现，汉字表以《一二级汉字表》为准）
拼音序号字典

按照《拼音汉字表》建立各个拼音对应的汉字字典
语料库
1. 语料库\sina_news_gbk文件夹下所有文件
2. 党的十九大、二十大报告
3. 百度百科
训练模型

建立的汉字字典、拼音序号字典，以及根据语料训练形成首字词典、尾字词典和二字词典，以pkl文件存储

结果分析

语料训练

用时 597.4830963611603 s

大小 349 MB

使用jieba分词后训练时间大大增长，用时 2031.184s，大小不变。

语料检验

引入jieba分词统计首字前

检验语料	运行时间	字准确率	整句准确率
课程检验语料（α=0）	2.59 s	0.5983	0.00593
课程检验语料（α=0.05）	2.59 s	0.6015	0.00610

引入jieba分词统计首字后

检验语料	运行时间	字准确率	整句准确率
课程检验语料（α=0）	2.59 s	0.5992	0.00632
课程检验语料（α=0.05）	2.59 s	0.6101	0.00654

平滑处理中的α是一个需要调节的参数，由于训练过程较长，本次作业中只尝试了α=0，0.05，0.1，0.2，0.5，选择了结果最好的0.05。后续如果可以优化算法，提升预处理的效率，可能可以更好地调节α的值，来获得更高的准确率。
通过jieba分词来处理首字问题，在原有的二元模型下，对字的准确率虽不到2‰，但对整句话的准确率提高了6.6%。可见对于首字问题，引入jieba分词来统计首字是有一定优化的。

这在二元模型的程序下提升可能不太明显，但这是一项除了改进模型（比如换为三元模型，或者语义关联模型等）之外的优化方法，有优化意义。

改进模型

观察错误的句子可以发现，二元模型对拼音输入的误判率还是较高的，比如“我上学去了”会识别为“我上学区了”，因为存在概率较大的词语“学区”。因此可以考虑三元甚至四元模型，比如三元模型，只需要将二元模型中的二维频率矩阵改为三维矩阵，然后在动态规划时初始概率矩阵为前二字，之后每个字维护前两个字到该字的路径和即可。四元模型同理。

另外也可以引入语义关联模型——例句“用女字旁的她试试”显然是很难输出“她”的（我先用的微软输入法也不行），这需要更多优化。

多音字问题

由于多音字的存在，在归一化频率时存在一个字需要被归一化多次的情况。这个问题是非常广泛的——6763个字对应的拼音列表汉字有9000多，即差不多一半的字都是多音字。

同时这也是最致命的问题——一个多音字的概率该按照哪个读音来计算。由于存在平滑化处理，若$\alpha$偏大，则多音字容易通过其它高频读音而在低频拼音中显著性突出。

本次作业程序考虑的是，计算一个矩阵统计频率后，另设一个矩阵计算概率，在归一化过程中，概率矩阵存储频率矩阵的字的各个读音的归一化情况，取其大者。
在统计二字词组词频时，会因为部分词频为0，在归一化时出现0/0的现象，因此原本程序在normalization中不除以sum，而是跳过归一化、平滑化、对数化而直接将其赋值为float（“inf”），但后续发现错误——因为多音字的存在，在一个多音字的读音$y_1$词频为0，被置为无穷大后另一拼音$y_2$的词频就变为无穷大了，继而报错。

解决办法是，处理过程中保持词频为0，接着平滑化，最后对整体（而非前面的遍历过程中）对数化。

数据处理问题

词频过高时，采用用双精度无法表达，故在语料过多的时候，考虑先对频率矩阵对数化，最后平滑化。
以上求转移概率矩阵的时候，平滑化处理可以调参$\alpha$，这个值难以找到最优。
在转移概率矩阵的求解过程中，直接对频率矩阵进行归一化、平滑化、负对数化，牺牲预处理的时间换取了大量的拼音输出时间，这在检验文本较大时更明显，但同时带来了一个问题——矩阵存储的频率是多音字的某一读音对应的频率，可能存在问题，但考虑到平滑化处理，这个问题得到了一定的缓解，同时这个问题也值得后续继续思考解决。

首字问题与尾字问题

句中首字与其他位置的字的概率是不同的，严格来说，同一个字在二字词中的一字和二字概率也是不同的。有的字在开头出现概率大，在末尾出现概率小。

考虑到输入语句中的第一个字一定是一个词语的首字，但句中的其他字也可能是其他词语的首字，因为词语在句中位置不同，故“词语首字”可能在句中各个位置出现——但不可能作为最后一个字出现（否则语义上也不是首字）。

对于首字概率，本程序最初是统计每句话的非最后一字，计算首字概率。

改进后的版本引入了jieba库，对语料进行分词，进而可以较好地给词语分块，区分首字和尾字，更准确地计算首字概率（建立初始概率矩阵）和尾字概率（计算平滑化矩阵）。

同时，在句中的字，作为词语的尾字的概率也是与首字不同的；但是二元模型中一个句中的字一定同时是首字和尾字，故存在模型的局限性，本模型中也只是去除了每句话的首字来统计尾字概率，这几乎与单字概率相同。对于三元模型，尾字问题会更明显一些（第1，2，3个字的概率各不相同）；对于能够提前分割语句、串联语义的模型，尾字问题更加重要。

djyos / 基于汉字二元模型的拼音输入法实现

基于汉字二元模型的拼音输入法实现