%0 Journal Article
%A Jacquet, Philippe
%A McVey, Bonita
%A Szpankowski, Wojciech
%T Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth
%J Journal of the Iranian Statistical Society
%V 3
%N 2
%U http://jirss.irstat.ir/article-1-108-en.html
%R
%D 2004
%K Digital trees, limiting distribution, Patricia trie, suffix tree.,
%X Suffix trees are the most frequently used data structures in algorithms on words. In this paper, we consider the depth of a compact suffix tree, also known as the PAT tree, under some simple probabilistic assumptions. For a biased memoryless source, we prove that the limiting distribution for the depth in a PAT tree is the same as the limiting distribution for the depth in a PATRICIA trie, even though the PATRICIA trie is constructed from statistically independent strings. As a result, we show that the limiting distribution for the depth in a PAT tree built over n suffixes is normal.
%> http://jirss.irstat.ir/article-1-108-en.pdf
%P 139-148
%& 139
%!
%9
%L A-10-1-41
%+
%G eng
%@ 1726-4057
%[ 2004