|
OALib Journal期刊
ISSN: 2333-9721
费用：99美元
|
|
|
|
利用频率特征的Trie树索引快速构造算法
DOI: 10.13190/jbupt.201302.84.232, PP. 84-88
Keywords: 索引构造,快速算法,Trie树,字符频率,双数组Trie
Abstract:
随着物联网技术的日益成熟和云计算标准的确立以及各种智能终端的大规模出现,互联网数据呈指数增加,为数据建立索引至关重要,为此提出一种基于词频的Trie树索引快速构造算法,首先对索引字符串进行排序,然后对排序文件进行预处理,预处理生成一个三元组,分别由相同字符横向偏移、纵向偏移及字符组成.快速算法依次扫描预处理数据的每一列,根据三元组的偏移跳过相同的字符前缀.实验结果显示,本算法的时间明显少于传统构造算法,优于Aoe的双数组Trie构造算法.
| [1] | Patascale Data Storage Institute. NERSC file system statistics . Berkeley: NERSC, 2007.
|
| [2] | Felix E. Static survey of file system statistics . Pittsburgh: Environmental Molecular Sciences Laboratory, 2007.
|
| [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 //17th 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.
|
Full-Text
|
|
Contact Us
service@oalib.com QQ:3279437679 
WhatsApp +8615387084133
|
|
