概况
本文是一篇实验报告，主要介绍了这几天以来我对拼音输入法的设计和思考。
算法实现基于字的二元模型，使用基于 sina news 的汉语语料库进行模型训练。
对于拼音到汉字的转换，目前算法可以轻松实现 80% 以上的准确率。
Git 仓库地址：https://github.com/Konano/homework_input_method/tree/master/release
算法初步实现
一、对训练数据的处理
原语料库文件为 JSON 格式，一条 JSON 信息包含一条新闻。但每条新闻并不是单纯地由汉字构成，其内混杂了各种标点符号、数字、字母等非汉字字符，很难被直接利用，所以在训练前需要对原始语料进一步处理。
我将 JSON 的新闻内容提取出来后，将数字、字母和各种字符删去。其中的难点在于如何区别中文标点符号和汉字，在 ANSI 编码下中文标点符号和汉字都为双字节，最后在多次查验后确定了中文标点符号的编码范围，从而将其去除。
经过处理，便得到了可直接使用的句子片段。
二、训练
调用 training.exe 程序进行训练，主要是统计训练数据中单字出现频率和相邻二字所组成的二元组频率，分别保存到 1-gram 和 2-gram 文件内。拼音方面则是直接使用了提供的拼音汉字表。
三、实现解码算法
解法算法使用了 Viterbi 算法，该算法基于动态规划思想；并使用最大似然估计作为其概率。为了解决样本数量较少的问题，我还引入了 Laplace 平滑，缓解数据稀疏所带来的问题。
进一步改进
一、多音字处理
在对第一版程序（v1）进行测试后发现，转换结果中多音字的错误尤其多。这可能是由于训练的时候未对语料进行正确注音导致。
于是我调用了 python 下的 pypinyin 对语料进行注音。同时为了提升多音字注音正确性，我先调用了 python 下的「结巴分词」对语料进行分词再注音。训练的时候不再以单字作为基本单位，而是以单字单音作为基本单位，这样便将多音字分成多个单体，从而避免多音字内生僻读音的概率受常用读音的影响。
二、句首句尾概率
训练的时候进一步统计了每个字在句首和句尾的频数。假如给句首和句尾多定义一个特殊字符的话，出现在句首和句尾的情况也可以看成是一种二元关系。解码的时候充分利用此信息，能使得转换后的句子开头和结尾不会太突兀。
三、增加训练集
由于训练集多为新闻，在转换非新闻的句子（例如日常用语）的时候准确率就十分一般。所以我搜集了另外一些日常用语作为训练集的补充。
四、基于字的三元模型
尝试更高阶的 HMM 模型。训练的时候增加对相邻三字所构成的三元组的频数统计。难点在于不同三元组的数量过多，很难在程序内全部存下。我采取的解决方案是，先统计单个子训练集内出现的三元组信息，并有序输出到外部文件内；再对多个外部文件进行合并，取频数前 5,000,000 的三元组并储存。解码的时候以相邻二字为状态，并使用 Viterbi 算法解码。
五、基于词的一、二元模型
基于处理语料时的分词，我初步实现了基于词的一、二元模型的算法。由于词与词的二元关系实在过于庞大，在训练时采用了和处理字的三元关系一样「先单个再合并」的做法。解码方面则依旧使用 Viterbi 算法。
六、平滑算法
在处理字三元组和词二元组的时候，数据稀疏性的问题越发突出，于是尝试使用 Good-Turing 估计和 Katz 回退法取代最大似然估计来计算其出现概率。
实验效果
由于作业附件并没有提供测试数据，于是我手动从最近的新闻中摘录了一些新闻片段组成了测试集，单字个数 4880，句子总数 122。各版本测试结果如下：
| 准确率 | |
|---|---|
| 1.字二元模型 | 82.541% |
| 2.字二元模型 + 一 | 84.8566% |
| 3.字二元模型 + 一 + 二 | 84.9795% |
| 4.字二元模型 + 一 + 三 | 84.7336% |
| 5.字二元模型 + 一 + 二 + 三 | 84.6721% |
| 6.字三元模型 + 一 + 二 | 74.629% |
| 7.词一元模型 + 一 + 二 | 61.6598% |
| 8.词二元模型 + 一 + 二 | 86.168% |
| 9.词二元模型 + 一 + 二 + 六 | 72.9158% |
从测试结果能够得到的信息有：
- 对于多音字的处理可以看出是有效果的，准确率有所提高。
- 第 2 个和第 4 个的比较中可以看出新增和测试集（多为新闻）交集较小的训练集（多为日常用语）会降低准确率。当然实验结果两个版本准确率只相差了 0.1%，也不排除是数据正常误差导致。
- 字三元模型的准确率反而比最基本的字二元模型准确率要低。个人认为有三点原因：一是数据稀疏性；二是数据量过大无法全部储存；三是可能程序内三元 Viterbi 算法实现有误。
- 尝试给字二元和词二元模型更换平滑算法，换成 Katz 回退法，但是准确率反而下降了近 10%。尚不清楚是什么原因导致的。
总结 & ToDo
- 训练语料对于算法的影响十分明显。若训练语料和测试集是不同情景下的句子，则算法准确率便会大打折扣。今后可考虑用与测试集同类的训练语料进行训练。
- 对于训练语料的处理同样重要。原算法对语料库的处理方法实现起来简单粗暴。但一个完整的句子在这种分割下也变得破碎不堪，并没有很好利用标点符号两端字符连接的信息等。
- 若考虑最简单的储存方式，字二元模型的数据库大小在未压缩的情况下已经有 33ＭB 左右，所以可在数据库压缩方面做进一步的改进。对于字多元模型和词多元模型可采取舍弃频数较少的多元关系信息来缩小数据库。
- 今后可以尝试用各种平滑算法解决数据稀疏问题。
- 可以尝试完善基于字的三元模型的算法，和实现基于字的四元模型或基于词的三元模型的算法。
- 解码算法方面还有许多问题需要思考，比如音节切分歧义、大规模解码算法的剪枝、更高阶的 N 元模型的解码算法等。
