Other
When indexing equals compression: Experiments with compressing suffix arrays and applications
(2004)
Abstract
We report on a new and improved version of high-order entropy-compressed suffix arrays, which has theoretical performance guarantees similar to those in our earlier work [16], yet represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20 % of the original text size—without requiring a separate instance of the text—and support fast and powerful searches. To our knowledge, this is the best known method in terms of space for fast searching. 1
Disciplines
Publication Date
2004
Citation Information
Roberto Grossi, Ankur Gupta and Jeffrey S. Vitter. "When indexing equals compression: Experiments with compressing suffix arrays and applications" (2004) Available at: http://works.bepress.com/ankur_gupta/6/