Lyndon array construction during Burrows-Wheeler inversion

Autor(es)

Louza, Felipe A. ^[1] ; Smyth, W. F. ^{[2, 3]} ; Manzinic, Giovanni ^{[4, 5]} ; Telles, Guilherme P. ^[6]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Comp & Math, Sao Paulo - Brazil

^[2] McMaster Univ, Dept Comp & Software, Hamilton, ON - Canada

^[3] Murdoch Univ, Sch Engn & Informat Technol, Murdoch, WA - Australia

^[4] Univ Piemonte Orientale, Comp Sci Inst, Vercelli - Italy

^[5] CNR, Inst Informat & Telemat, Pisa - Italy

^[6] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF DISCRETE ALGORITHMS; v. 50, p. 2-9, MAY 2018.
• Citações Web of Science: 0

Resumo

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. (C) 2018 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 17/09105-0 - Ordenação de sufixos e medidas de similaridade entre cadeias
• Beneficiário: Felipe Alves da Louza
• Linha de fomento: Bolsas no Brasil - Pós-Doutorado