|
发表于 2003-6-23 19:24:39
|
显示全部楼层
最初由 james_su 发表
如果用外存的话,我觉得还不如直接使用现有的数据库系统,像 xsim 那样。这样可以把主要精力放在中文匹配算法上,而不是数据库搜索算法上。
而且我觉得 3M 多的内存对现代计算机来说不算什么。scim-chinese 由于使用了 unicode,占的内存还要多很多,目前大概在 10M 左右,但 scim-chinese 以 10M 内存的代价实现了基本可用的整句输入,相对于智能狂拼这种上百兆的大家伙就不算什么了。
而且在真实输入系统里面,对算法性能的需求会远远高于你这样的实验系统。试想:如果要得到流畅的整句输入,用户每敲一个按键就必须把所有已经输入过的所有按键都从新分析匹配一遍,因为没准下一个按键就会使得已经输入的拼音串和词库里面一个词匹配上了。假设词库里面的最长词是16个字,那么至少最近的16个拼音键必须要重新分析匹配。
另外,真正耗时的算法是拼音串的智能匹配,也就是怎么把拼音串正确的转换为汉字串。用户每敲一个键,这个工作就必须重新做一遍。你试一下 scim-chinese 就知道了。当你输入的时候,所有预编辑汉字都会根据新输入的内容实时的自动匹配。
这样一来你就可以估计一下你的算法是否满足要求了。如果你在词库中搜索一个拼音串的时间是 1 ms 的话,用户输入一个20字左右的句子,平均估计得按100个键,也就是说最少必须搜索100次词库,但实际上搜索次数要比这个大得多,大概需要上千次,具体原因你可以先想想。这样算下来 1ms 的搜索时间就显得非常慢了。因为后期的匹配算法的复杂度大概要比这个高一个数量级。
说到数据库的问题。这个话题就太多了。我在给diy添加数据库功能的早期,我就经常在想:在Windows下的某个程序员,如果有资料,如果有一个access数据库,当然懂一点ime api的话,在不考虑系统移植,不考虑内存,不考虑效率的情况下,是个人都能写出拼音输入法。有什么不比一个sql还有效么?
我今天才知道xsim使用的是数据库。呵呵,看来我并不孤独。我之所以要自己写一个数据库,是有其目的的。一方面,我可以完全控制索引的方式。另一方面,我每写一个程序都想给自己留下一个可纪念的东西。
在索引实现中怕的不是字多,而是字少。16个字的输入,太理想了。当然这是对于一个16个字的词组来说。在数据库模式下,而且是在拼音这种情况下。主要的问题是1和2的问题。1表示输入的第一个字,2表示输入的第一个2个汉字的词组。这是最困难的。再往下,重码率级低。基本上不要考虑了。
1的问题现在已经很好的解决的。我使用冗余索引花费了1M的文件空间解决了这个问题。而且再1的情况下,不用任何排序。2的问题是我今天研究的主体。呵呵,我正再矛盾中。
10M的空间,实在是太奢侈了。说实在的,我现在的14万的记录的空间文件空间是5.7M。这里面有14万的汉字或词组,还有32万的索引。
如果我开了一个6M的缓存,速度不会很慢的。另外,对于GBK中的大多数内容来说,是不会使用的,为什么么把它们加载到内存中哪?你完全可以使用一个缓慢增长机制呀。
如果从这一点来看,使用定制数据库还是可行的。用户如果想使用1M的空间,慢一点它也知道原因。呵呵,我使用过的设备,从来就没有低于512M。我开个20M的缓冲,我也理解。 |
|