#输入法项目设计与测试文档 ##关键技术 1）通信模型：输入法技术符合通信模型的概念，其概念图如下： （S1,S2,S3,…） （O1,O2,O3…） 信息，上下文 ---------> 传递的信息---------->接收的信息 （发送者） (编码) （解码） （接受者） 通信6要素：发送者（信息源）、信息、接受者，上下文和编码
2）N gram模型：该模型基于这样一种假设，第N个词的出现只与前面N-1个词相关，而与其它任何词都不相关，整句的概率就是各个词出现概率的乘积。这些概率可以通过直接从语料中统计N个词同时出现的次数得到。常用的是二元的Bi-Gram和三元的Tri-Gram。二元模型可以引出HMM模型（本系统没有用到）。二元模型的计概率公式如下： P(Wi|Wi-1) = #（Wi-1，Wi）/ #（Wi-1）
3）平滑：其中比较好用的就是古德图灵平滑，原理是看不见的事件不认为概率为0，因此需要分配一定的概率给看不见的事件，因此看得见的概率小于1，需要根据“越不可信的统计折扣越多的方法”降低可见事件的概率。本系统要采用的平滑是Add-delta，通过增加一个小于1的正数λ，来平滑。高阶n-gram的概率估计可以求助于低阶n-gram的概率估计值，这两种方法进行平滑。
4）Zip定律： 假设语料库中出现r次的词有Nr个，则r越大，Nr越小。 5）贝叶斯公式：以信息论为基础和贝叶斯公式想结合求： P（O1,O2,O3…| S1,S2,S3,…）* P(S1,S2,S3,…)最大 因为实现比较复杂所以就先求了最大的P(S1,S2,S3,…)，然后再求出最大的P（O1,O2,O3…| S1,S2,S3,…），O1,O2,O3…就为最大的的输出信息。 6）前缀树字典：是一种有序树数据结构，哈希树的变种。与二叉查找树不同，树中节点不存储与节点关联的键，而是通过树中的位置定义键。一个节点的所有子孙节点拥有与该节点相同的字符串前缀，根节点与空字符串相关联。并不是每个节点都与值关联，仅叶节点和部分内部节点与值关联。 7）有向无环图：在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图） 8）动态规划：因为可能性太多，所以为了求一个最大的P(S1,S2,S3,…)通过动态规划计算出全局最大的路径。动态规划的主要**是通过局部最大找到全局最大。 9）维特比算法：因为计算P（O1,O2,O3…| S1,S2,S3,…）时，通过wo shi yi ge ren的有向无环图的可能性有65592800种，为了不进行遍历，通过维特比算法得到最大的P（O1,O2,O3…| S1,S2,S3,…），维特比算法也是一种动态规划。（可能不太符合老师的要求，但是简化了计算的过程） 10）软件测试：软件测试的经典定义是：在规定的条件下对程序进行操作，以发现程序错误，衡量软件质量，并对其是否能满足设计要求进行评估的过程。 ##各个文件主要功能概述： 1） cp.py,cphz.py统计语料库中每个字出现的次数，并且将它保存到cp.txt和cphz.txt中。 2） dict.py是将py.txt中的字音转换字典读到内存中，已经集成到model.py中。 3） train.py统计语料库中每个字出现的次数，并且将它保存到train.txt中。 4） ylk3.txt是语料库的源文件。 5） model.py本输入法核心文件。
1） get_py方法获得字音的字典。 2） get_cp方法获得字频。 3） get_train方法获得二元模型频率。 4） prefix方法获得前缀树组。 5） input方法输入拼音字符串。 6） getdag方法获得拼音字符串的有向无环图。 7） db方法通过动态规划获得最有可能的拼音序列 8） translate方法将最有可能的拼音序列转化为以列表形式展现的拼音。 9） vtb方法通过将拼音序列获得最有可能的汉子输出。 最后通过ID选择相应的汉子序列。