Faster searching in tries and quadtrees—An analysis of level compression
作者： Arne Andersson , Stefan Nilsson
DOI: 10.1007/BFB0049399
关键词:
摘要: We analyze the behavior of level-compressed trie, LC-trie, a compact version standard trie data structure. Based on this analysis, we argue that level compression improves performance both tries and quadtrees considerably in many practical situations. In particular, show LC-tries can be great use for string searching compressed text.
springer.com
sci-hub.se 参考文章(19)
Peter Kirschenhofer, Helmut Prodinger, Some Further Results on Digital Search Trees international colloquium on automata languages and programming. pp. 177- 185 ,(1986) , 10.1007/3-540-16761-7_67
Philippe Flajolet, Mireille Regnier, Dominique Sotteau, Algebraic Methods for Trie Statistics North-holland Mathematics Studies. ,vol. 109, pp. 145- 188 ,(1985) , 10.1016/S0304-0208(08)73107-4
Gaston H Gonnet, Handbook of algorithms and data structures ,(1984)
L. Devroye, A note on the average depth of tries Computing. ,vol. 28, pp. 367- 371 ,(1982) , 10.1007/BF02279819
Philippe Flajolet, On the performance evaluation of extendible hashing and trie searching Acta Informatica. ,vol. 20, pp. 345- 369 ,(1983) , 10.1007/BF00264279
Eric Slud, Entropy and maximal spacings for random partitions Probability Theory and Related Fields. ,vol. 41, pp. 341- 352 ,(1978) , 10.1007/BF00533604
Boris Pittel, Paths in a random digital tree: limiting distributions Advances in Applied Probability. ,vol. 18, pp. 139- 155 ,(1986) , 10.2307/1427240
Amihood Amir, Gad M Landau, Uzi Vishkin, Efficient pattern matching with scaling Journal of Algorithms. ,vol. 13, pp. 2- 32 ,(1992) , 10.1016/0196-6774(92)90003-U
Arne Andersson, Stefan Nilsson, Improved behaviour of tries by adaptive branching Information Processing Letters. ,vol. 46, pp. 295- 300 ,(1993) , 10.1016/0020-0190(93)90068-K
Arne Andersson, Stefan Nilsson, Efficient implementation of suffix trees Software - Practice and Experience. ,vol. 25, pp. 129- 141 ,(1995) , 10.1002/SPE.4380250203