In this paper we present an algorithm to compute the Lyndon array of a string T of length n as a byproduct of the inversion of the Burrows–Wheeler transform of T . Our algorithm runs in linear time using only a stack in addition to the data structures used for Burrows–Wheeler inversion. We compare our algorithm with two other linear- time algorithms for Lyndon array construction and show that computing the Burrows– Wheeler transform and then constructing the Lyndon array is competitive compared to the known approaches. We also propose a new balanced parenthesis representation for the Lyndon array that uses 2n + o ( n ) bits of space and supports constant time access. This representation can be built in linear time using O ( n ) words of space, or in O ( n log n / log log n ) time using asymptotically the same space as T .
Lyndon array construction during Burrows–Wheeler inversion
Manzini, Giovanni
;
2018-01-01
Abstract
In this paper we present an algorithm to compute the Lyndon array of a string T of length n as a byproduct of the inversion of the Burrows–Wheeler transform of T . Our algorithm runs in linear time using only a stack in addition to the data structures used for Burrows–Wheeler inversion. We compare our algorithm with two other linear- time algorithms for Lyndon array construction and show that computing the Burrows– Wheeler transform and then constructing the Lyndon array is competitive compared to the known approaches. We also propose a new balanced parenthesis representation for the Lyndon array that uses 2n + o ( n ) bits of space and supports constant time access. This representation can be built in linear time using O ( n ) words of space, or in O ( n log n / log log n ) time using asymptotically the same space as T .File | Dimensione | Formato | |
---|---|---|---|
1710.10105.pdf
file ad accesso aperto
Descrizione: Main paper
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
436.19 kB
Formato
Adobe PDF
|
436.19 kB | Adobe PDF | Visualizza/Apri |
jda2018.pdf
file disponibile solo agli amministratori
Descrizione: main paper
Tipologia:
Versione Editoriale (PDF)
Licenza:
DRM non definito
Dimensione
349.61 kB
Formato
Adobe PDF
|
349.61 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.