Articolo in rivista, 2010, ENG, 10.1145/1868237.1868248
Ferragina P.; Venturini R.
Department of Computer Science, Univ. Pisa, Pisa, Italy; CNR-ISTI, Pisa, Italy
The Permuterm index [Garfield 1976] is a time-efficient and elegant solution to the string dictionary problem in which pattern queries may possibly include one wild-card symbol (called Tolerant Retrieval problem). Unfortunately the Permuterm index is space inefficient because it quadruples the dictionary size. In this article we propose the Compressed Permuterm Index which solves the Tolerant Retrieval problem in time proportional to the length of the searched pattern, and space close to the kth order empirical entropy of the indexed dictionary. We also design a dynamic version of this index that allows to efficiently manage insertion in, and deletion from, the dictionary of individual strings. The result is based on a simple variant of the Burrows-Wheeler Transform, defined on a dictionary of strings of variable length, that allows to efficiently solve the Tolerant Retrieval problem via known (dynamic) compressed indexes [Navarro and Mäkinen 2007]. We will complement our theoretical study with a significant set of experiments that show that the Compressed Permuterm Index supports fast queries within a space occupancy that is close to the one achievable by compressing the string dictionary via gzip or bzip. This improves known approaches based on Front-Coding [Witten et al. 1999] by more than 50% in absolute space occupancy, still guaranteeing comparable query time.
ACM transactions on algorithms 7 (1), pp. 10–21
Text Indexing, Data Compression
ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"
ID: 44413
Year: 2010
Type: Articolo in rivista
Creation: 2011-09-14 00:00:00.000
Last update: 2018-02-12 14:29:04.000
CNR authors
External IDs
CNR OAI-PMH: oai:it.cnr:prodotti:44413
DOI: 10.1145/1868237.1868248