Computing the Burrows–Wheeler transform in place and in small space

Abstract : We introduce the problem of computing the Burrows–Wheeler Transform (BWT) using small additional space. Our in-place algorithm does not need the explicit storage for the suffix sort array and the output array, as typically required in previous work. It relies on the combinatorial properties of the BWT, and runs in O(n 2) time in the comparison model using O(1) extra memory cells, apart from the array of n cells storing the n characters of the input text. We then discuss the time-space trade-off when O(k · σ k) extra ✩ A preliminary version of the results in this paper appeared in [6]. memory cells are allowed with σ k distinct characters, providing an O((n 2 /k + n) log k)-time algorithm to obtain (and invert) the BWT. For example in real systems where the alphabet size is a constant, for any arbitrarily small ǫ > 0, the BWT of a text of n bytes can be computed in O(nǫ −1 log n) time using just ǫn extra bytes.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2015, 32, pp.44 - 52. 〈10.1016/j.jda.2015.01.004〉
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-01616463
Contributeur : Maxime Crochemore <>
Soumis le : vendredi 13 octobre 2017 - 16:41:40
Dernière modification le : lundi 16 octobre 2017 - 10:36:20
Document(s) archivé(s) le : dimanche 14 janvier 2018 - 14:30:51

Fichier

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

Identifiants

Collections

Citation

Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen, Gad M. Landau. Computing the Burrows–Wheeler transform in place and in small space. Journal of Discrete Algorithms, Elsevier, 2015, 32, pp.44 - 52. 〈10.1016/j.jda.2015.01.004〉. 〈hal-01616463〉

Partager

Métriques

Consultations de la notice

15

Téléchargements de fichiers

18