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.
FERRAGINA, PAOLO (Corresponding)
|Autori:||Ferragina, Paolo; J., Siren; Venturini, Rossano|
|Titolo:||Distribution-aware compressed full-text indexes|
|Anno del prodotto:||2013|
|Digital Object Identifier (DOI):||10.1007/s00453-013-9782-3|
|Appare nelle tipologie:||1.1 Articolo in rivista|