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. & 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., & 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 & 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.
