Lyndon array construction during Burrows–Wheeler inversion

Felipe A. Louza, W. F. Smyth, Giovanni Manzini, Guilherme P. Telles

Research output: Contribution to journalArticlepeer-review

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(nlog⁡n/log⁡log⁡n) time using asymptotically the same space as T.

Original languageEnglish
Pages (from-to)2-9
Number of pages8
JournalJournal of Discrete Algorithms
Volume50
DOIs
Publication statusPublished - May 2018
Externally publishedYes

Keywords

  • Balanced parentheses
  • Burrows–Wheeler inversion
  • Compressed representation
  • Linear time
  • Lyndon array

Fingerprint

Dive into the research topics of 'Lyndon array construction during Burrows–Wheeler inversion'. Together they form a unique fingerprint.

Cite this