Journal article
Lyndon Array construction during Burrows-Wheeler inversion
Journal of Discrete Algorithms, Vol.50, pp.2-9
2018
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 bits of space and supports constant time access. This representation can be built in linear time using words of space, or in time using asymptotically the same space as T.
Details
- Title
- Lyndon Array construction during Burrows-Wheeler inversion
- Authors/Creators
- F.A. Louza (Author/Creator) - Universidade de São PauloW.F. Smyth (Author/Creator) - McMaster UniversityG. Manzini (Author/Creator) - Università degli Studi del Piemonte Orientale “Amedeo Avogadro”G.P. Telles (Author/Creator) - Universidade Estadual de Campinas (UNICAMP)
- Publication Details
- Journal of Discrete Algorithms, Vol.50, pp.2-9
- Publisher
- Elsevier
- Identifiers
- 991005542336907891
- Copyright
- © 2018 Elsevier B.V
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
65 File views/ downloads
83 Record Views