摘要: Andersson and Nilsson have already shown that the average depth Dn of random LC-tries is only Θ(log* n) when keys are produced by a symmetric memoryless process, = O(log logn) process asymmetric. In this paper we refine second estimate showing asymptotically (with n ⇒ ∞): ∼ 1/η log logn, where number inserted in trie, η - log(1 h/h-∞), h -p p q entropy binary, source with probabilities p, 1 (p≠q), h-∞ min(p, q).
core.ac.uk
elsevier.com
reznik.org 参考文章(24)
Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching Addison Wesley Longman Publishing Co., Inc.. ,(1998)
Stefan Nilsson, Gunnar Karlsson, Fast address look-up for internet routers BC '98 Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications. ,vol. 121, pp. 11- 22 ,(1998) , 10.1007/978-0-387-35378-4_2
Arne Andersson, Stefan Nilsson, Faster searching in tries and quadtrees—An analysis of level compression Algorithms — ESA '94. pp. 82- 93 ,(1994) , 10.1007/BFB0049399
L. Devroye, A note on the average depth of tries Computing. ,vol. 28, pp. 367- 371 ,(1982) , 10.1007/BF02279819
Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences ,(2001)
Donald Ervin Knuth, Sorting and Searching ,(1973)
Y.A. Reznik, W. Szpankowski, Improved behaviour of tries by the "symmetrization" of the source data compression conference. pp. 372- 381 ,(2002) , 10.1109/DCC.2002.999975
Philippe Flajolet, Robert Sedgewick, Digital search trees revisited SIAM Journal on Computing. ,vol. 15, pp. 748- 767 ,(1986) , 10.1137/0215054
Luc Devroye, Wojcieh Szpankowski, Probabilistic behavior of asymmetric level compressed tries Random Structures and Algorithms. ,vol. 27, pp. 185- 200 ,(2005) , 10.1002/RSA.V27:2
Philippe Flajolet, Andrew Odlyzko, Singularity analysis of generating functions SIAM Journal on Discrete Mathematics. ,vol. 3, pp. 216- 240 ,(1990) , 10.1137/0403019