Italiano (Italian) English (Inglese)
Friday, 9 June 2023


Pubblication Details
Authors:Giovanni Manzini
Scientific Area:Text Compression and Indexing
Title:Two space saving tricks for linear time LCP computation
Published on:TR-INF-2004-02-03-UNIPMN
Publisher:Computer Science Department, UPO
Tipo Pubblicazione:Technical Report
Abstract:In this paper we consider the linear time algorithm of Kasai et al. for the computation of the LCP array given the text and the suffix array. We show that this algorithm can be implemented without any auxiliary array in addition to the ones required for the input (the text and the suffix array) and the output (the LCP array). Thus, for a text of length n, we reduce the space occupancy of this algorithm from 13n bytes to 9n bytes. We also consider the problem of computing the LCP array ``overwriting' the suffix array. For this problem we propose an algorithm whose space occupancy depends on the regularity of the text. Experiments show that for linguistic texts our algorithm uses roughly 7n bytes. Our algorithm makes use of the Burrows-Wheeler Transform even if it does not represent any data in compressed form. To our knowledge this is the first application of the Burrows-Wheeler Transform outside the domain of data compression.