拼音输入法实验报告
计 53
张正彦
2014010515
1 算法思路
拼音输入法问题定义 求使得 P (S) =
∏
n
i=1
P (w
i
|w
i−1
) 最大的句子。
字的二元模型 在字的二元模型中,我们通过语料去学习 P (w
i
|w
i−1
),这里 w
i
代表着一个汉字,
i = 1, 2, ..., n,n 的大小为一二级汉字表的大小。但是我们输入的是一串拼音,对于长度为 L 的拼
音串,可以表示为 V
1
, V
2
, ..., V
L
,其中 V
i
代表一个音节,在确定汉字表的情况下,我们的拼音表的
大小 m 也是确定的。对于每个字来说,它只会对应一个或者多个拼音。通过这样的分析,我们便可
以把字的二元模型转换为一个一阶隐马尔科夫模型。
一阶隐马尔科夫模型 在一阶隐马尔科夫模型中,用 a
ij
来表示由状态 i 转移到状态 j 的概率,也
就是我们的 P (w
i
|w
i−1
)。与此同时,用 b
jk
来表示在状态 j 时表现为可使特征 k 的概率,但通过语
料库我们是无法得到字与拼音之间的概率关系的。所以在这里为了简化问题,我假设只要拼音表中
没有这种对应则 b
jk
就为 0,有对应则为 1,暂时不做对于多音字的处理。
求解最大概率的隐状态 如果暴力枚举,再选取最大,这里的时间复杂度为 O(n
T
T ) 这里 n 是汉字
的个数,T 为序列的长度,这个时间复杂度是不可接受的。所以这里我使用了 viterbi 算法,它巧
妙的利用了一阶马尔可夫模型下一个状态只和当前状态有关的特性,将时间复杂度降到了 O(n
2
T )。
算法的基本思路就是从 T=1 时开始计算若以隐状态 w
i
结尾时,生成 V
1
, V
2
, ..., V
j
的最大概率,这
里 j 为当前计算序列的长度。这样算 V
1
, V
2
, ..., V
j
概率只要知道 V
1
, V
2
, ..., V
j−1
概率就行了。
实现过程
• 根据词表对汉字进行编号,并且与汉字的读音文件结合,构建一个新的 lookup 文件,便于之
后的使用
• 对于文本中的二元关系进行计数,保存为 n ∗ n 的矩阵形式
• 读取统计的数据后,使用 laplace 平滑,避免出现一些次数为 0 的二元组影响结果
• 在算最大关系序列时使用了 viterbi 算法,较快完成了计算并进行预测
2 实验效果
正确长句
• 系统对于人们来说并不是一个陌生的名词
• 全国人民代表大会在北京人民大会堂隆重召开
• 深度学习技术推动了人工智能的发展
• 特朗普希望不久和中国国家主席面对面会晤
• 为了方便大家测试自己的拼音输入法的性能
1
评论0