Compact suffix trees resemble PATRICIA tries : limiting distribution of depth - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1993

Compact suffix trees resemble PATRICIA tries : limiting distribution of depth

B. Rais
  • Fonction : Auteur
Wojciec Szpankowski
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1995.pdf (330.65 Ko) Télécharger le fichier

Dates et versions

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

Identifiants

  • HAL Id : inria-00074677 , version 1

Citer

Philippe Jacquet, B. Rais, Wojciec Szpankowski. Compact suffix trees resemble PATRICIA tries : limiting distribution of depth. [Research Report] RR-1995, INRIA. 1993. ⟨inria-00074677⟩
93 Consultations
41 Téléchargements

Partager

Gmail Facebook X LinkedIn More