双数组Trie树索引的可操作性研究被引量：2

Research on the Operability of the Double-Array Trie Structure

下载PDF

导出

摘要双数组是组织和实现Trie树的一种数据结构。双数组Trie树索引实现的是一种线性时间复杂度的搜索机制,因此被广泛的应用于信息检索和中文分词等领域。然而双数组Trie树索引建立后不易于更新,限制了这种索引的现实应用。在前人的双数组Trie树优化索引构造的基础上,分析了插入和删除操作的所有可能情况,提出了对双数组Trie树索引进行相关操作的算法。最后分析了其时间和空间开支,并用实验结果证明了其可行性。

作者廖敏褚颖娜宋继华

机构地区北京师范大学信息科学与技术学院

出处《计算机系统应用》 2009年第10期53-56,52,共5页 Computer Systems & Applications

基金国家社科基金(05BYY022)

关键词信息检索 TRIE树双数组稳定词空间开支

分类号 TP311.12 [自动化与计算机技术—计算机软件与理论] TP311.13 [自动化与计算机技术—计算机软件与理论]

引文网络
相关文献

参考文献4

1Aoe J.An Efficient Digital Search Algorithm by Using a Double-Array Structure. IEEE Transactions on Soft ware Engineering. 1989,15(9): 1066 - 1077.
2王思力,张华平,王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报,2006,20(5):24-30. 被引量：29
3Oono M, Atlam ES. A fast and compact elimination method of empty elements from a doublearray structure. Software-Practice and Experience, 2003, 33(8):1229 - 1249.
4Yata S, Oono M, A compact static double- array keeping character codes. Information Processing and Management, 2007,43(3):237 - 247.

二级参考文献10

1马哲,姚敏.一种改进的基于PATRICIA树的汉语自动分词词典机制[J].华南理工大学学报（自然科学版）,2004,32(z1):28-31. 被引量：3
2刘群,张华平,俞鸿魁,程学旗.基于层叠隐马模型的汉语词法分析[J].计算机研究与发展,2004,41(8):1421-1429. 被引量：198
3Douglas C.Schmidt.GPERF:A Perfect Hash Function Generator[Z].1999.
4Theppitak Karoonboonyanan.An Implementation of Double-Array Trie[Z],http://linux.thai.net/～ thep/datrie/datrie,html,2003.
5Jun-Ichi Aoe,Katsushi Morimoto,Takashi Sato,An Efficient Implementation of Trie Structures[J].SoftwarePractice and Experience.1992,22 (9):695-721.
6Aoe,J.An Efficient Digital Search Algorithm by Using a Double-Array Structure[J].IEEE Transactions on Software Engineering.1989,15 (9):1066-1077.
7路志英,林孔元,郭祺,段广玉.中文切分词典的最大匹配索引法[J].天津大学学报,1999,32(5):599-603. 被引量：4
8孙茂松,左正平,黄昌宁.汉语自动分词词典机制的实验研究[J].中文信息学报,2000,14(1):1-6. 被引量：118
9杨文峰,陈光英,李星.基于PATRICIA tree的汉语自动分词词典机制[J].中文信息学报,2001,15(3):44-49. 被引量：30
10李庆虎,陈玉健,孙家广.一种中文分词词典新机制——双字哈希机制[J].中文信息学报,2003,17(4):13-18. 被引量：108

共引文献28

1乐娟.基于Trie树的京剧术语语义词典[J].计算机工程,2011,37(S1):30-32. 被引量：3
2杨来,何清,许立达,史忠植.Dynamic Hash TRIE算法的研究与分析[J].广西师范大学学报（自然科学版）,2008,26(1):134-138.
3高艳萍,于红,尹祥贵,綦孝姬,王春永,赵志强.基于双数组Trie树的渔业领域分词研究[J].安徽农业科学,2008,36(11):4788-4790.
4赵欢,朱红权.基于双数组Trie树中文分词研究[J].湖南大学学报（自然科学版）,2009,36(5):77-80. 被引量：16
5吴晶晶,荆继武,聂晓峰,王平建.一种快速中文分词词典机制[J].中国科学院研究生院学报,2009,26(5):703-711. 被引量：16
6王世昆,李绍滋,柯逍.基于遗传算法和舍伍德思想的双数组Trie树改进[J].计算机工程与应用,2009,45(29):128-130. 被引量：3
7褚颖娜,廖敏,宋继华.一种基于统计的分词标注一体化方法[J].计算机系统应用,2009,18(12):55-58. 被引量：3
8吴龙,吴健,任红民.基于双数组Trie树的嵌入式TTS系统研究[J].现代机械,2010(4):67-70.
9张硕果,汪成亮.结合CRFs的词典分词法[J].计算机系统应用,2010,19(11):115-118. 被引量：1
10魏博诚,王爱平,沙先军,王永.一种消除中文分词中交集型歧义的方法[J].计算机技术与发展,2011,21(5):60-63. 被引量：4

同被引文献18

1温滔,朱巧明,吕强.一种快速汉语分词算法[J].计算机工程,2004,30(19):119-120. 被引量：19
2王思力,张华平,王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报,2006,20(5):24-30. 被引量：29
3李江波,周强,陈祖舜.汉语词典的快速查询算法研究[J].中文信息学报,2006,20(5):31-39. 被引量：25
4廖述梅,万常选,徐升华.XML信息检索探究[J].情报学报,2007,26(2):229-234. 被引量：6
5Carmel D, Maarek Y, Soffer A. XML and information re- trieval= a SIGIR 2000 workshop [J]. ACM SIGIR Forum, 2000,34(1) :31-36.
6Fuhr N,Govert N, Kazai G, et al. INEX= initiative for the evaluation of XML retrieval[M]//Liu L, Ozsu T M. Engy- elopedia of Database System. New York Springer, 2009: 1531-1537.
7关辉.利用XSLT实现XML文档格式的转换[J].福建电脑,2009,25(3):181-181. 被引量：2
8赵欢,朱红权.基于双数组Trie树中文分词研究[J].湖南大学学报（自然科学版）,2009,36(5):77-80. 被引量：16
9王世昆,李绍滋,柯逍.基于遗传算法和舍伍德思想的双数组Trie树改进[J].计算机工程与应用,2009,45(29):128-130. 被引量：3
10连剑波,刘任,刘杰.XML数据库在蔬菜病虫害信息发布平台中的应用[J].安徽农业科学,2010,38(4):2178-2180. 被引量：3

引证文献2

1钟金琴,辜丽川.基于XML的农作物病虫草害数据检索系统的研究[J].合肥工业大学学报（自然科学版）,2013,36(8):943-947.
2徐国天,张铭.网络安全态势感知中Trie树关键词高速匹配算法研究[J].信息网络安全,2019(4):55-62. 被引量：9

二级引证文献9

1简玲,叶天鹏,林祥,谢方军.多源融合的大数据网络安全态势感知平台研究与探索[J].信息网络安全,2020(S02):139-143. 被引量：9
2董坤,张海霞,刘艳梅,李洋.宽带卫星网络安全态势感知技术研究[J].信息网络安全,2020(S02):98-101. 被引量：3
3张建平,李洪敏,贾军,卢敏.一种基于流量与日志的专网用户行为分析方法[J].信息安全研究,2020,6(9):783-790. 被引量：6
4韩磊,胡建鹏.基于关键词Trie树的GCC抽象语法树消除冗余算法[J].计算机科学,2020,47(9):47-51. 被引量：6
5贾军,李洪敏,张建平.基于匹配热度的混合模式匹配方法研究[J].网络新媒体技术,2021,10(5):23-29.
6漆良蕃.智慧图书馆基于用户行为分析的安全态势平台设计研究[J].信息网络安全,2021(S01):208-211.
7张国萍.基于大数据的网络信息传输安全态势感知算法[J].电子设计工程,2022,30(12):185-188. 被引量：9
8肖英,赵林洁,张宇,屈晓芳.支持快速索引的高效大数据存储结构[J].计算机应用与软件,2024,41(3):28-33. 被引量：1
9刘泽洋,王万齐,卢文龙.基于知识图谱的铁路工程实体信息表达方法与应用[J].铁道建筑,2024,64(5):157-162.

1董辉.基于单向增长链表的关联规则挖掘算法研究[J].长江大学学报（自科版）（上旬）,2012,9(1X):110-112.
2刘钊江,钟思琦,殷源.基于数据流的结构化功能安全分析方法[J].铁道通信信号,2016,52(2):16-20.
3田娟,杨晓明.计算机辅助翻译软件在翻译实践中的可操作性研究[J].自动化与仪器仪表,2016(5):12-14. 被引量：7
4陈安军,李国梁,谢蕾.冗余度机器人速度方向可操作性研究[J].信阳师范学院学报（自然科学版）,2003,16(3):273-275.
5林朝晖,于俊清,何云峰,管涛,艾列富.高维分布式局部敏感哈希索引方法[J].计算机科学与探索,2013,7(9):811-818. 被引量：9
6窦建武,余跃庆.柔性机器人协调操作的力可操作性研究[J].北京工业大学学报,2000,26(3):10-15. 被引量：4
7梁晓玲.计算机技术在煤炭产业物流业的应用[J].山西能源与节能,2004(1):21-22. 被引量：2
8王卓,刘大昕,冯晓宁.基于框架的软构件后缀索引构造方法研究[J].哈尔滨工程大学学报,2006,27(1):107-111. 被引量：1
9陈安军,马学文.双臂机器人机构力方向可操作性研究[J].机械设计与制造,2005(1):107-109. 被引量：1
10陶勖恒.科技期刊自主全文上网的可操作性研究[J].中国科技期刊研究,2000,11(2):99-102. 被引量：9

计算机系统应用

2009年第10期

浏览历史

内容加载中请稍等...

双数组Trie树索引的可操作性研究被引量：2

参考文献4

二级参考文献10

共引文献28

同被引文献18

引证文献2

二级引证文献9

相关作者

相关机构

相关主题

浏览历史

双数组Trie树索引的可操作性研究 被引量：2

参考文献4

二级参考文献10

共引文献28

同被引文献18

引证文献2

二级引证文献9

相关作者

相关机构

相关主题

浏览历史

双数组Trie树索引的可操作性研究被引量：2