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.
Jacquet,P. , McVey,B. and Szpankowski,W. (2022). Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth. Journal of the Iranian Statistical Society, 3(2), 139-148.
MLA
Jacquet,P. , , McVey,B. , and Szpankowski,W. . "Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth", Journal of the Iranian Statistical Society, 3, 2, 2022, 139-148.
HARVARD
Jacquet P., McVey B., Szpankowski W. (2022). 'Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth', Journal of the Iranian Statistical Society, 3(2), pp. 139-148.
CHICAGO
P. Jacquet, B. McVey and W. Szpankowski, "Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth," Journal of the Iranian Statistical Society, 3 2 (2022): 139-148,
VANCOUVER
Jacquet P., McVey B., Szpankowski W. Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth. JIRSS, 2022; 3(2): 139-148.
Journal of the Iranian Statistical Society