汉语词典查询是中文信息处理系统的重要基础部分,对系统效率有重要的影响。本文对汉语词典查询算法研究作了简要回顾,设计实现了基于双数组TRIE机制的汉语词典查询算法,并提出了基于双编码机制的词典查询算法。最后以逐字二分法查询性能为基准,使用这两种词典询机制进行了词语直接查询和分词查询两种应用的性能测试。经过实验分析,双数组TRIE机制的词典查询算法在查询速度上提高明显,查询速度约是逐字二分法的5倍。双编码机制的的词典查询算法查询速度有一定提高,而且调整机制更加灵活。
Abstract
The dictionary mechanism serves as one of the basic components in Chinese information processing systems. Its performance influences the performances of these systems significantly. In this paper, we review the algorithms for Chinese dictionary lookup at first, then design and implement a Chinese dictionary based on Double-Array TRIE mechanism, and present a new Chinese dictionary based on Double Coding mechanism. In the end, we compare their space and time complexity experimentally with the binary-seek-by-characters mechanism. It can be seen that the Chinese dictionary based on Double-Array TRIE mechanism improves the speed obviously.
关键词
计算计应用 /
中文信息处理 /
汉语词典查询 /
双数组TRIE /
双编码算法
{{custom_keyword}} /
Key words
computer application /
Chinese information processing /
Chinese dictionary lookup /
double-array TRIE /
double coding algorithm
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 王秀坤,李政,简幼良,刘剑基. 基于Hash方法的机器翻译词典的组织与构造[J]. 大连理工大学学报, 1996, (3) : 352 - 355.
[2] 孙茂松,左正平,黄昌宁. 汉语自动分词词典机制的实验研究[J]. 中文信息学报, 2000, 14 (1) : 1 - 6.
[3] 李庆虎,陈玉健,孙家广. 一种中文分词词典新机制——双字哈希机制[J]. 中文信息学报, 2003, 17 (4) : 13 - 18.
[4] 杨文峰,陈光英,李星. 基于PATRICIA tree的汉语自动分词词典机制[J]. 中文信息学报, 2001, 15 (3) : 44 - 49.
[5] 严蔚敏,吴伟民. 数据结构[M]. 北京:清华大学出版社, 1992.
[6] Aoe, J. An Efficient Digital Search Algorithm by Using a Double-Array Structure [J]. IEEE Transactions on Software Engineering. 1989, (9).
[7] Theppitak Karoonboonyanan. An Implementation of Double-Array Trie. http://linux.thai.net/thep/datrie/datrie.html.
[8] 欧几里德算法. http://www.nhyz.org/nhxi/suanfa /main.htm
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金资助项目(60173008);欧盟FP6项目ALVIS的科技部配套经费资助
{{custom_fund}}
PDF(202 KB)
