双数组Trie树算法优化及其应用研究.pdfVIP

中 文 信 息 学 报 第20卷 第5期 JOURNALOFCHNIESENIFORMATIONPROCESSNIGVol.20No.5 文章编号;1003一0077(2006)05一0024一07 双数组Trie树算法优化及其应用研究 王思力’,2，张华平’,2，王斌， (1中国科学院计算技术研究所，北京 100080;2.中国科学院研究生院，北京 100039) 摘要:本丈对双数组Trie树(Double-ArrayTrie)算法提出了一种优化策略，即在来用Trie树构造数组的过 程中，优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时，进一步 减少数据稀疏，提高空间利用率。我们基于该优化算法实现了一个词典管理程序，并与利用其他索引机制的 词典进行了实验对比。实验结果表明，利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他 索引机制的词典，而且存储数据的空间占用也比较小。 关键词:计算机应用;中文信息处理;双数组;Trie树;词典;分词 中图分类号二TP391.1 文献标识码:A ResearchofOptimizationonDouble-ArrayTrieanditsApplication WANGSi-li.Z，ZHANGHua-ping2，WANGBin (InstitutionofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,China; GraduateSchooloftheChineseAcademyofSciences,Beijing100080,China) Abstract:ThispaperproposesanimprovedstrategyforthealgorithmofDouble-ArrayTriethatis,thenodewithmost childnodesispraessedfirstlywhenconstructingthearray.Thisstrategycanreducethedatasparsenessandkeepthe searchefficiencymeanwhile.WeimplementaprogramforlexiconmanagementbaseontheimprovedDouble-Array Trieandcompareitwithotherindexmechanisms.TheresultsclearlyshowthattheimprovedDouble-Array-Triealg-o rithmhasamuchhighersearchspeedandneedsasmallerspacefordatastorethanotherindexmachanisms. Keywords;computerapplication;Chineseinformationprocessing;Double-Array;TRIE;lexicon;wordsegmentation 1 引言 对于大量数据的存储和有哪些信誉好的足球投注网站，目前通常都采用索引结构来实现。一般常用的索引结构包 括线性索引表、倒排表、散列(Hash)表以及各种有哪些信誉好的足球投注网站树。 线性索引是一种静态的索引结构，不利于更新，每当做依次更新时需要改变索引表中各个 索引项的位置。倒排表也是静态索引，它与线性索引表一样，有哪些信誉好的足球投注网站其中数据的时候都只能顺序 有哪些信誉好的足球投注网站或者折半有哪些信誉好的足球投注网站。 散列(Hash)方法则是在表项的存储位置与它的关键码之间建立一个确定的对应函数关 系HHhaassho()，使每个关键码与结构中的一个存储位置相对应 〔〕‘。有哪些信誉好的足球投注网站时只需要对表项的关键码 进行函数计算，求得的函数值即是表项的存储位置，避免了多次关键码比较，因此有哪些信誉好的足球投注网站速度比 收稿日期:2005-08-28 定稿日期;2006-07一11 基金项目:国家973项目资助(2004CB318109);国家242信息安全计划资助课题成果(2005C36);中国 科学院计算所知识创新工程资助 作者简介:王思力(1981-)，男，硕士研究生，主要研究方向为自然语言处理，中文信息检索. 24 较快。由于有可能经过散列函数的计算，把不同的关键