Compact suffix trees resemble PATRICIA tries : limiting distribution of depth - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 1993

Compact suffix trees resemble PATRICIA tries : limiting distribution of depth

B. Rais
  • Function : Author
Wojciec Szpankowski
  • Function : Author

Abstract

Suffix trees are the most frequently used data structure in algorithms on words. Despite this, little is known about their behavior in a probabilistic framework. In this paper, we consider the depth of a compact suffix tree, also known as the PAT tree, under some simple probabilistic assumptions. In fact, for the case of an asymmetric alphabet, 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 over statistically independent strings. In other words, the limiting distribution for the depth in a PAT tree storing n suffixes is normal.
Fichier principal
Vignette du fichier
RR-1995.pdf (330.65 Ko) Télécharger le fichier

Dates and versions

inria-00074677 , version 1 (24-05-2006)

Identifiers

  • HAL Id : inria-00074677 , version 1

Cite

Philippe Jacquet, B. Rais, Wojciec Szpankowski. Compact suffix trees resemble PATRICIA tries : limiting distribution of depth. [Research Report] RR-1995, INRIA. 1993. ⟨inria-00074677⟩
91 View
40 Download

Share

Gmail Facebook Twitter LinkedIn More