Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Lyndon array construction during Burrows-Wheeler inversion

Texto completo
Autor(es):
Louza, Felipe A. [1] ; Smyth, W. F. [2, 3] ; Manzinic, Giovanni [4, 5] ; Telles, Guilherme P. [6]
Número total de Autores: 4
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
Número total de Afiliações: 6
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
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado