Compact suffix trees resemble PATRICIA tries : limiting distribution of depth

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.
Type de document :
Rapport
[Research Report] RR-1995, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074677
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:04:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 18:16:56

Fichiers

Identifiants

  • HAL Id : inria-00074677, version 1

Collections

Citation

Philippe Jacquet, B. Rais, Wojciec Szpankowski. Compact suffix trees resemble PATRICIA tries : limiting distribution of depth. [Research Report] RR-1995, INRIA. 1993. 〈inria-00074677〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

48