输入法开发——实战<二>检词算法

输入法出词的算法看似复杂，微软选择的算法是相对低开销且高效的一种。

通过行为分析，步骤大致分为三步：

一、完全匹配

二、词频建议

三、补全出词

前两步是必须有的，第三个只有五笔有。

通过一个小工具 WubiLex 可以导出五笔的 Lex 词库文件（目前的windows无法直接查看该文件）

一个词的组成有四个部分：编码、词、权重、顺序

一个词可能的多个编码，但权重不变

一个权重只能有一个

一个顺序只能有一个

如：

a            工 19829    1

aaa        工 19829    3

aaaa      工 19829    12

多个码可以很好的解决简码检索的问题，根据编码匹配程度给出结果。拼音的算法也是相似的。不同的只有句拼，这个需要一定的机器学习能力。

权重用来表示词频，顺序作为算法的提示、补充。

主体上的算法是：1、匹配用户词库；2、匹配主词库（使用链表的话无需太在意顺序，但小心重复）

匹配用户词库是非常简单的，就是完全匹配。智能学习就是在这个词库中添加词条。

匹配主词库就有点难度了：

1、完全匹配

这一步是相对简单的，编码相同就可以。然后根据权重排序。

2、词频建议

这一步是难点

先取码，从编码的第一条开始遍历

例：码：a

从 a--- 第一个开始，到 azzz(安全最大) 或 ayyy(五笔实际) 最后一个结束

在 a--- 编码中找到权重最小的作为第一个，记权重作 c（提前备表）

然后在下一编码中

取出顺序最小的，如果其权重小于 c 跳转至下一编码，

否则，输出 其中权重大于 c 的权重最小的一个词，将新的权重写入 c 进入下一编码 重复此步

步骤大致如此（未去除重复）一个词是不能在候选中出现再次的，需要剔除重复的候选。

码：ab

在 ab-- 编码中找到权重最小的

从 ab-- 第一个开始，到 abzz(安全最大) 或 abyy(五笔实际) 最后一个结束

其它步骤是相同的, 但是开销是相对小很多的。

完成了以上步骤，还有补全一步，这一步是可选的

如果，编码中字母相同，将其补为4个相同字母组成的编码

a -> aaaa, b -> bbbb

最后，要按 匹配 > 权重 的方法排序候选

再插入用户词汇，如果它们存在。

五笔中 z 键作用不尽相同，各各实现均有所差异。但是注意，z 是第一个字母时，尽量不要提供有候选参与的功能。

实际的输入法不能每次都从文件中读取词库，当然不是不行，而是开销过大。

词库应当由维护输入法的进程建立通道供输入法动态获取。