Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Sėren J., Venturini R. Distribution-aware compressed full-text indexes. In: Algorithmica, vol. 67 (4) pp. 529 - 546. Springer, 2013.
In this paper we address the problem of building a compressed self-index that, given a distribution for the pattern queries and a bound on the space occupancy, minimizes the expected query time within that index space bound. We solve this problem by exploiting a reduction to the problem of finding a minimum weight $K$-link path in a properly designed Directed Acyclic Graph. Interestingly enough, our solution can be used with any compressed index based on the Burrows-Wheeler transform. Our experiments compare this optimal strategy with several other known approaches, showing its effectiveness in practice.
URL: http://link.springer.com/article/10.1007/s00453-013-9782-3
DOI: 10.1007/s00453-013-9782-3
Subject Indexing

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional