汉语词典的快速查询算法研究.pdfVIP

中 文 信 息 学 报 第20卷 第5期 JOURNALOFCHINESEINFORMATIONPROCESSING Vol·20No·5 文章编号 ：1003—0077(2006)05—003I一09 汉语词典的快速查询算法研究 李江波，周 强，陈祖舜 (清华大学计算机系 智能技术与系统国家重点实验室，北京 100084) 摘要：汉语词典查询是中文信息处理系统的重要基础部分，对系统效率有重要的影响。本文对汉语词典 查询算法研究作了简要回顾，设计实现了基于双数组TRIE机制的汉语词典查询算法，并提 出了基于双编码 机制的词典查询算法。最后以逐字二分法查询性能为基准，使用这两种词典询机制进行 了词语直接查询和分 词查询两种应用的性能测试。经过实验分析 ，双数组TRIE机制的词典查询算法在查询速度上提高明显，查 询速度约是逐字二分法的5倍。双编码机制的的词典查询算法查询速度有一定提高，而且调整机制更加 灵活。 关键词：计算计应用；中文信息处理；汉语词典查询；双数组TRIE；双编码算法 中图分类号：TP391 文献标识码：A A StudyonFastAlgorithm forChineseDictionaryLookup LIJiang—bo，ZHOUQiang，CHENZu—shun (TheStateKeylaboratoryofIntelligentTechnologyandSystems． DepartmentofComputerScienceandTechnoloyg，TsinghHaUniversity，Beijing100084，China) Abstract：Thedictionary mechanism servesasoneofthebasiccomponentsinChinese information processingsys— tems．Itsperfomr anceinfluencestheperfomr nacesofthesesystemssignificnatly．Inthispaper，wereview thealgo- rithmsforChinesedictionarylookupatfirst，htendesing andimplementaChinesedictionarybasedonDouble—Array TRIE mechnaism ，nadpresentanewChinesedictionarybasedonDoubleCodingmechnaism．Inhteend，wecomprae theirspacena dtimecomplexityexperimentallywiththebinary—seek—by—characters mechnaism．ItCna beseenthatthe ChinesedictionarybasedonDouble—ArrayTRIEmechanism impmveshtespeedobviously． Keywords：computerapplication；Chinese infomr ationprocessing；Chinesedictionarylookup；doub le—arrayTRIE； doublecod ingalgorithm 1 引言 在汉语信息处理系统中，汉语词典查询是一个重要的基础环节，在整个处理过程中都需要频 繁地访问词典以获得汉语词语知识，因而汉语词典的快速查询是整个处理系统效率的关键所在。 针对词典查询方法，前人作了大量工作，并形成了许多汉语词典组织结构和相应的查询算法。 早期的词典组织构造主要是基于传统Hash方法，文献 [1]中采用的方法就是一个典型应 用，这种方法的关键技术是 Hash函数的设计，采用合理的方式来调节数据块的分配，控制均匀 性，减少冲突，提高空间利用率，由于磁盘读取，这种方法在速度上存在较大局限。 收稿 日期 ：2005—06—20 定稿 日期 ：2006—07—16 基金项 目：国家 自然科学基金资助项 目；欧盟 FP6项 目ALVIS的科技部配套经费资助