锐英源精品开源，禁止转载和任何形式的非法内容使用，违者必究

安卓输入法码表词典实现

词典的功能是很清楚的:对于一个给定的拼音输入,给出一个候选词集合.

对于这个功能,有多种数据结构可以实现,刚开始时曾经考虑过基于哈希树的设计,每个节点表示一个拼音音节,节点内包含从各节点到这里的音节路径对应的候选词.每个节点的子节点用哈希表的方式进行索引,key就是对应的音节.这样的结构事实证明不论是构建还是查找都是很快的(在开发机上用java编写的代码从开始构建一个9万词的树到完成一次查找耗时不到100ms),但是内存占用较多,9万词的词库文件是1.6m,整棵树大概需要27m的内存.虽然理论上这样的树结构去掉了一些冗余信息,应该更小才对,但是每个节点用到的各种数据结构和对象的额外开销太大(优化后还有200字节左右),是节点本身存储信息(10字节左右)的十几倍,因此才导致这么大的空间占用.

如果是在PC上实现这样一个输入法,其实是不用考虑这些内存占用的(27m内存对于当前的主流配置来说可以忽略不计).但是无奈我们是在Android进行开发,在不同配置的机型下dalvik虚拟机限制每个程序的最大堆空间在40m~50m,如果光一棵树就占去了27m,再加上一些其他的对象,以及UI方面的资源,很轻易的就会超过这个上线.事实上我们在优化之前连3万词的词库都无法顺利建成(out of memory),并且及时在优化后,总占用空间也达到了38m左右,在建树过程中不停地要进行gc操作(因为初始时整个堆空间只分配了大约10m),使得整个过程非常慢,大约需要10s左右,对于用户来说是不能忍受的.

为了解决内存上的问题,最后还是改为使用哈希表来进行词典的表示,但是每个词的key不是它所对应的拼音,而是它所对应的拼音所计算出来的code,是一个长整型.公式很简单,就是把拼音的每一个字母从a~z分别当成数字1~26,把整个拼音串看成是一个26进制数,将它转换成10进制后得到的就是对应的code.这一方面是为了节省空间(即使用char类型来表示,平均每个拼音串的长度也是超过7的,再加上’\0’还占去一位,就超过long的64比特了,更别提用string来标示了).这样还有一个好处,就是在分析词典文件时与查询候选词时,可以用长整型的传递来代替字符串的传递,可以省去构建字符串的时间.

由于候选词的key是拼音串对应的code,因此和拼音的切分是无关的.因此正如切音部分中提到的,对于”xian”这个输入,既能查到”先”,又能查到”西安”.

最后再提一下,由于在dalvik虚拟机下不仅遇到了内存问题,执行效率也遇到了很大的问题,对于一个9万行的词典文件,光是这个9万次的循环就需要2s(在循环体是空的情况下).并且开始时还使用了String中的split方法,事实证明它也非常的慢,并且还很占空间,但是即使重写了一个用来解析词典每一行的方法后,总体执行效率仍然不理想.最后没有办法,只能把词典这部分的代码迁移到C++上,通过JNI来完成java中其他部分的代码和词典的通信.