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