同步操作将从 伍小南18/基于汉字二元模型的拼音输入法实现 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Woo wrnthu@163.com
已上传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$。
综上,需要在给定拼音的情况下逐字搜索,得到整句话最可几的汉字排列。
按照上述模型,依据拼音串输出汉字串的过程是一个典型的动态规划问题——
在本问题中,根据前一个字以及本字拼音来确定本字,即为一个一阶的隐式马尔科夫过程。
对于要求的式子 $$ \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}$ } 在建立汉字序号字典时不考虑多音字
$dict_{pinyin}$ = {“$y_1$”, 同音字“$x_{11}x_{12}\cdots x_{1n}$”对应的汉字序号 $[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
数据结构如下
考虑到汉字个数较少,二字词组的规模也不大,故考虑采用二维矩阵来存储汉字词组“$x_1x_2$”出现的频率
注:
采用二维矩阵存储汉字词组,先在字典上搜索汉字$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} $$
平滑处理,最后取负对数,将[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个汉字编号
(《拼音汉字表》与《一二级汉字表》汉字顺序不同,因《拼音汉字表》中有多音字重复出现,汉字表以《一二级汉字表》为准)
拼音序号字典
按照《拼音汉字表》建立各个拼音对应的汉字字典
语料库
训练模型
建立的汉字字典、拼音序号字典,以及根据语料训练形成首字词典、尾字词典和二字词典,以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个字的概率各不相同);对于能够提前分割语句、串联语义的模型,尾字问题更加重要。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。