Please use this identifier to cite or link to this item:
Type: Artigo
Title: Burrows-wheeler Transform And Lcp Array Construction In Constant Space
Author: Louza
Felipe A.; Gagie
Travis; Telles
Guilherme P.
Abstract: In this article we extend the elegant in-place Burrows-Wheeler transform (BWT) algorithm proposed by Crochemore et al. [12]. Our extension is twofold: we first show how to compute simultaneously the longest common prefix (LCP) array as well as the BWT, using constant additional space; we then show how to build the LCP array directly in compressed representation using Elias coding, still using constant additional space and with no asymptotic slowdown. Furthermore, we provide a time/space tradeoff for our algorithm when additional memory is allowed. Our algorithm runs in quadratic time, as does Crochemore et al.'s, and is supported by interesting properties of the BWT and of the LCP array, contributing to our understanding of the time/space tradeoff curve for building indexing structures. (c) 2016 Elsevier B.V. All rights reserved.
Subject: Burrows-wheeler Transform
Lcp Array
In-place Algorithms
Compressed Lcp Array
Elias Coding
Editor: Elsevier Science BV
Rights: fechado
Identifier DOI: 10.1016/j.jda.2016.11.003
Date Issue: 2017
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000394809100003.pdf360.54 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.