Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depth

Authors

Abstract

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.

Keywords

Volume 3, Issue 2
November 2004
Pages 139-148
  • Receive Date: 23 July 2022
  • Revise Date: 25 May 2024
  • Accept Date: 23 July 2022