利用频率特征的Trie树索引快速构造算法

doi:10.13190/jbupt.201302.84.232

北京邮电大学学报 ›› 2013, Vol. 36 ›› Issue (2): 84-88.doi: 10.13190/jbupt.201302.84.232

利用频率特征的Trie树索引快速构造算法

张启飞¹, 吴吉义^1,2, 李文娟^1,3, 吕红兵¹, 潘雪增¹

1. 浙江大学计算机科学与技术学院, 杭州 310027; 2. 杭州师范大学电子商务与信息安全重点实验室, 杭州 310036; 3. 杭州师范大学钱江学院, 杭州 310036

收稿日期:2012-09-29 修回日期:2013-01-18 出版日期:2013-04-30 发布日期:2013-03-25
通讯作者: 潘雪增 E-mail:xzpan@cs.edu.zju.cn
作者简介:张启飞（1984-），男，博士生，Email：zhangfeezju@gmail.com；潘雪增（1942-），男，教授，博士生导师
基金资助:
国家高技术研究发展计划项目（2008AA010A323）；国家自然科学基金项目（60773182）

A Fast Trie Tree Index Construction Algorithm Using Frequency Characteristic

ZHANG Qi-fei¹, WU Ji-yi^1,2, LI Wen-juan^1,3, LV Hong-bing¹, PAN Xue-zeng¹

1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;<br>2. Key Laboratory of E-Business and Information Security, Hangzhou Normal University, Hangzhou 310036, China;<br>3. College of Qianjiang, Hangzhou Normal University, Hangzhou 310036, China

Received:2012-09-29 Revised:2013-01-18 Online:2013-04-30 Published:2013-03-25

摘要/Abstract

摘要：

随着物联网技术的日益成熟和云计算标准的确立以及各种智能终端的大规模出现,互联网数据呈指数增加,为数据建立索引至关重要,为此提出一种基于词频的Trie树索引快速构造算法,首先对索引字符串进行排序,然后对排序文件进行预处理,预处理生成一个三元组,分别由相同字符横向偏移、纵向偏移及字符组成. 快速算法依次扫描预处理数据的每一列,根据三元组的偏移跳过相同的字符前缀. 实验结果显示,本算法的时间明显少于传统构造算法,优于Aoe的双数组Trie构造算法.

关键词: 索引构造, 快速算法, Trie树, 字符频率, 双数组Trie

Abstract:

With maturity of "the Internet of things" and establishment of cloud computing national standards, kinds of terminals appear quickly, and huge amounts of datas generation exponentially increase, so its crucial to construct index for the data. A fast Trie-tree index construction algorithm is proposed. All the strings are sorted and then the sorted strings are preprocessed, and after that a matrix with the element of triple is generated, consisting of the character, the horizontal and vertical offset of the character. The fast algorithm scans each column in turn and skips the repeated rows and columns with the same prefix according to offset value in triple array. The experimental results show that the fast algorithm significantly reduces the construction time compared with traditional algorithm and the performance is better than Aoes double-array Trie construction algorithm.

Key words: index construction, fast algorithm, Trie-tree, character frequency, double-array Trie

中图分类号:

TP338.8

张启飞, 吴吉义, 李文娟, 吕红兵, 潘雪增. 利用频率特征的Trie树索引快速构造算法[J]. 北京邮电大学学报, 2013, 36(2): 84-88.

ZHANG Qi-fei, WU Ji-yi, LI Wen-juan, LV Hong-bing, PAN Xue-zeng. A Fast Trie Tree Index Construction Algorithm Using Frequency Characteristic[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2013, 36(2): 84-88.

参考文献

[1] Patascale Data Storage Institute. NERSC file system statistics . Berkeley: NERSC, 2007. http://pdsi.nersc.gov/filesystem.htm.
[2] Felix E. Static survey of file system statistics . Pittsburgh: Environmental Molecular Sciences Laboratory, 2007. http://www.pdsi-scidac.org/fsstats/index.html.
[3] Inglis J. Inverted indexes and multi-list structures [J]. The Computer Journal, 1974, 17(2): 59-63.
[4] Monz C, Rijke M de. Inverted index construction. 2002. http://staff. science. uva. nl/~christof/courses/ir/ transparencies/cleanw-05. pdf.
[5] Knuth D E. The art of computer programming vol.3 sorting and searching [M]. Massachusetts: Addison-Wesley, 1973: 481-505.
[6] Aho A V, Ullman J D, Hopcroft J E. Data structures and algorithms [M]. Massachusetts: Addison-Wesley, 1983: 201-220.
[7] Standish T A. Data structure techniques [M]. Massachusetts: Addison-Wesley, 1980: 111-130.
[8] 张明波, 陆锋, 申排伟, 等. R树家族的演变和发展[J]. 计算机学报, 2005, 28(3): 289-300. Zhang Mingbo, Lu Feng, Shen Paiwei, et al. The evolvement and progress of R-tree family[J]. 2005, 28(3): 289-300.
[9] Comer D, Sethi R. The complexity of Trie index construction //17^th Annual Symposium on Foundations of Computer Science. Houston: , 1976: 197-207.
[10] Knuth D E. The art of computer programming vol.2, fundamental algorithms [M]. Massachusetts: Addison-Wesley, 1972: 295-304.
[11] Fredkin E. Trie memory [J]. Communication of the ACM, 1960, 3(9): 490-499.
[12] Johnson S C. YACC-Yet another compiler computing science technical report 32 . NJ: Bell Lab, 1975: 1-34.
[13] Aho A V, Sethi R, Jeffrey D U. Compilers: principles, techniques, and tools [M]. Boston: Addison-Wesley Press, 1986: 109-189.
[14] Aoe J. An efficient digital search algorithm by using a double-array structure [J]. IEEE Transactions on Software Engineering, 1989, 15(9): 1066-1077.
[15] Cohen D. Introduction to theory of computing[M]. New York: John Wiley & Sons, 1990: 31-83.

利用频率特征的Trie树索引快速构造算法

A Fast Trie Tree Index Construction Algorithm Using Frequency Characteristic

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价