Statistical Properties of Factor Oracles

Jérémie Bourdon 1, 2 Irena Rusu 2
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Factor and suffix oracles provide an economic and efficient solution for storing all the factors and suffixes respectively of a given text. Whereas good estimations exist for the size of the factor/suffix oracle in the worst case, no average-case analysis has been done until now. In this paper, we give an estimation of the average size for the factor/suffix oracle of an $n$-length text when the alphabet size is 2 and under a Bernoulli distribution model with parameter 1/2. To reach this goal, a new oracle is defined, which shares many of the properties of a factor/suffix oracle but is easier to study and provides an upper bound of the average size we are interested in. Our study introduces tools that could be further used in other average-case analysis on factor/suffix oracles, for instance when the alphabet size is arbitrary.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2010, LNCS, 9 (2011), pp.59-66. 〈10.1007/978-3-642-02441-2〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00415952
Contributeur : <>
Soumis le : samedi 11 septembre 2010 - 07:00:05
Dernière modification le : samedi 14 janvier 2017 - 01:04:13
Document(s) archivé(s) le : dimanche 12 décembre 2010 - 02:21:15

Fichier

BourdonRusu.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jérémie Bourdon, Irena Rusu. Statistical Properties of Factor Oracles. Journal of Discrete Algorithms, Elsevier, 2010, LNCS, 9 (2011), pp.59-66. 〈10.1007/978-3-642-02441-2〉. 〈hal-00415952〉

Partager

Métriques

Consultations de la notice

419

Téléchargements de fichiers

105