Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
verfasst von : Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen, Gad M. Landau
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We introduce the problem of computing the Burrows– Wheeler Transform (
$\small\mathrm{BWT}$
) using just
O
(1) 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
$\small\mathrm{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 also discuss some time-space trade-offs for the inverse algorithm to obtain the text from the given
$\small\mathrm{BWT}$
.