Source-linked AI summary
Compressed Text Indexes:From Theory to Practice!
Paolo Ferragina, Rodrigo Gonzalez, Gonzalo Navarro, Rossano Venturini
TL;DR
Compressed full-text indexing promised efficient queries in compressed space, but its practical adoption was hindered by implementation complexity and the lack of reusable, standardized software. This paper reviews and engineers compressed indexes, introduces the Pizza&Chili site and two FM-index variants, and evaluates them experimentally. The experiments identify different leading indexes by task and text type, while showing substantial space savings alongside slower searches than plain suffix arrays.
Problem
Existing compressed indexes required substantial programming and engineering expertise, while isolated implementations lacked a common API for reuse and deployment.
Method
The paper reviews implemented compressed indexes, introduces two FM-index variants and the Pizza&Chili platform, and evaluates the implementations with testbeds and experiments.
Results
For counting, SSA and AF-index are best; SSA favors small alphabets for locating and extracting, while CSA leads on other high-order-compressible texts and LZ-index is competitive when extra space is allowed.
Takeaways & Limitations
Compressed indexes can provide significant search and extraction throughput while using up to 18 times less space than plain suffix arrays.
Takeaways & Limitations
Construction can require 5–9 times the text size in memory even when the final compressed index is small, and searches can be one to three orders of magnitude slower than plain suffix arrays.
Abstract
from arXiv · showhide
A compressed full-text self-index represents a text in a compressed form and still answers queries efficiently. This technology represents a breakthrough over the text indexing techniques of the previous decade, whose indexes required several times the size of the text. Although it is relatively new, this technology has matured up to a point where theoretical research is giving way to practical developments. Nonetheless this requires significant programming skills, a deep engineering effort, and a strong algorithmic background to dig into the research results. To date only isolated implementations and focused comparisons of compressed indexes have been reported, and they missed a common API, which prevented their re-use or deployment within other applications. The goal of this paper is to fill this gap. First, we present the existing implementations of compressed indexes from a practitioner's point of view. Second, we introduce the Pizza&Chili site, which offers tuned implementations and a standardized API for the most successful compressed full-text self-indexes, together with effective testbeds and scripts for their automatic validation and test. Third, we show the results of our extensive experiments on these codes with the aim of demonstrating the practical relevance of this novel and exciting technology.
1 Introduction
Full-text indexes became necessary for substring search, but traditional structures consumed excessive space. Compressed self-indexes address this trade-off, and this paper makes them more usable through engineering, standardized software, and experiments.
- Motivation: Full-text indexing supports substring searches needed in applications where word-boundary-based indexes are insufficient.The paper cites bio-informatics, computational linguistics, multimedia databases, search engines for agglutinating languages, and Far East languages as examples.
- Motivation: Traditional suffix trees and suffix arrays required at least four times the text size for reasonable efficiency.This space demand was problematic because disk access can be up to one million times slower than main memory, making internal-memory residence important.
- Compressed indexes: Compressed full-text indexes exploit text regularities to reduce space to the compressed-text scale without impairing query efficiency.They can also reproduce text portions without accessing the original text.
- Contributions: The paper reviews successful compressed indexes from a software-development perspective, including implementation choices and limitations.This engineering focus complements earlier theoretical surveys and aims to stimulate improvements in algorithmic tools.
- Contributions: The authors introduce two new compressed-index implementations, both variants of the FM-index family.One re-engineers an early self-index implementation, while the other implements the strongest current theoretical space/time guarantees and remains practically relevant.
- Technology transfer: Pizza&Chili provides tuned implementations, a common API, texts, and tools for experimenting with and validating compressed indexes.The site is intended to let programmers plug indexes into software and compare implementations experimentally.
2 Basic Concepts
This section defines text-search queries and classical full-text indexing, then introduces compressed-index primitives such as backward search, rank, wavelet trees, empirical entropy, and the Burrows-Wheeler Transform.
- Text-search queries: Text-search indexing supports counting and locating pattern occurrences, while self-indexes additionally extract text substrings without storing the original text separately.The basic queries are count, locate, and, for self-indexes, extract.
- Classical full-text indexes: Suffix trees answer counting in O(m) and locating in O(occ), but require 10 to 20 times the text size in practice; suffix arrays require about 4 times.Suffix arrays compact the suffix-tree representation while retaining Θ(n log n)-bit asymptotic space.
- Classical full-text indexes: Suffix-array searching identifies the lexicographic interval of suffixes prefixed by the pattern, then counts with occ = ep−sp+1 and locates occurrences from that interval.Binary search takes O(m log n), with auxiliary structures reducing the search time.
- Backward search: Backward search processes the pattern from right to left, updating suffix-array intervals until it finds no match or an interval containing all occurrences.The initial interval is obtained from a symbol table; each inductive step extends the matched pattern prefix leftward.
- Rank queries: Rank queries count a symbol's occurrences in a sequence prefix; binary rank uses block sampling, while wavelet trees reduce general-alphabet rank to binary rank operations.Wavelet trees can also replace the sequence for access, and Huffman-shaped variants use at most n(H0(S) + 1) + o(n log σ) bits with average rank/access time O(H0(S)).
- Compression measures and BWT: Empirical entropy measures compressibility for individual strings, with Hk capturing dependence on contexts of length k; the Burrows-Wheeler Transform groups symbols sharing contexts to improve compression.For k ≥ 0, nHk(T) lower-bounds context-based compression output, and BWT-based indexes exploit the resulting regularity.
3 Compressed Indexes
Compressed self-indexes support full-text searching and text access while occupying space tied to text compressibility. This section reviews FM-index, CSA, and LZ-index designs, including their query procedures, implementation trade-offs, and two new FM-index variants.
- Compressed-index overview: Theoretical compressed indexes achieve nHk(T) + o(n log σ) bits while supporting counting, locating, and substring extraction.The cited bounds give O(m log σ) counting time, O(log^(1+ε) n) time per located occurrence, and O(ℓ log σ + log^(1+ε) n) extraction time.
- FM-index family: FM-indexes compress the BWT and use generalized rank queries with backward search to identify pattern occurrences.Different variants trade space against counting, locating, and extraction performance.
- FM-index family: FM-index locating follows LF-mapping steps from each pattern-matching row to a marked suffix-array row, then reconstructs its text position.Sampling rate sA trades space for query time and guarantees at most sA LF-steps under the bitmap-based scheme.
- FM-index family: FM-index extraction starts from a sampled text position and applies LF-steps backwards, requiring at most sA + r − l + 1 applications.The sampling mechanism used for locating also supports substring extraction.
- Other compressed indexes: The SSA uses a Huffman-shaped wavelet tree for zero-order compression, while the LZ-index is competitive for locating and extracting but not counting alone.SSA rank and access average O(H0(T) + 1) time; LZ-index counting and locating are performed simultaneously.
4 The Pizza&Chili Site
The Pizza&Chili site packages compressed-index implementations, test collections, and validation tools behind a common API. Its indexed texts span multiple application types and support systematic evaluation of compression and performance.
- Site and API: Pizza&Chili provides publicly available, tuned compressed-index implementations intended to transfer the technology into software systems.The site combines software, testbeds, and a common API for researchers and developers.
- Site and API: The site includes compressed indexes supporting classical full-text searches, text access operations, representative text collections, and automatic validation scripts.The collections are designed to stress the effects of compression on memory usage and CPU performance.
- Implementations: The available implementations include plain Suffix Array, SSA, AF-index, RLFM, FMI-2, CSA, and LZ-index variants with different compression and query trade-offs.SSA emphasizes simplicity and zero-order compression; AF-index and RLFM provide high-order compression, while CSA is robust for large alphabets.
- Implementations: All implementations support byte-based alphabets of up to 255 symbols, reserving one symbol as the terminator “$”.CSA and LZ-index are exceptions to the common deep-shallow suffix-array construction used by the other indexes.
- Texts and experiments: Real compressors can achieve ratios superior to H4 because they use explicitly or implicitly longer contexts.The comparison includes gzip, bzip2, and PPMDi, while the tables report empirical entropy through fourth order.
5 Experimental Results
The experiments compare representative compressed indexes across construction, counting, locating, and extraction, exposing practical space/time tradeoffs and current limitations. Compressed indexes substantially reduce space, but the fastest or most suitable index depends on the operation and dataset.
- Experimental setup: The experiments evaluate SSA, AF-index, CSA, and LZ-index as representatives of three compressed-index classes.The study uses these implementations to provide a concise performance picture of compressed indexes.
- 5.2 Counting: The AF-index and CSA usually provide the best or similar space usage, while SSA is usually fastest for counting.The plain suffix array is 2–6 times faster than any compressed index but can occupy up to 18 times more space.
- 5.3 Locate: The experiments include sampling space for both locating and extracting, although that space could be reduced when only locating is required.The reported space/time tradeoffs therefore do not isolate the locate operation alone.
- 5.3 Locate: Compressed indexes are currently very efficient for selective locating queries, whereas traditional indexes become more effective when locating many occurrences.This difference follows from the occurrence layout and motivates further research on performance in hierarchical memories.
- 5.4 Extract: For extraction, CSA is better on sources and xml, SSA is better on dna and proteins, and LZ-index is much faster on several datasets with additional space.Using space equal to, and sometimes half of, the text, compressed indexes can extract around 1 MB/sec from arbitrary positions.
6 Conclusion and Future Work
The experiments show that compressed indexes offer substantial space savings with useful search and extraction throughput, but no single index dominates across all text collections and tasks.
- For counting, SSA and AF-index are the best indexes, while CSA usually loses because its counting complexity is O(m log n).
- For locating and extracting, SSA is strongest on small-alphabet data, CSA leads on other high-order compressible texts, and LZ-index is competitive when extra space is allowed.
- The paper concludes that there is no clear winner for all text collections, while its experiments demonstrate the practical relevance of compressed text indexing.
- Compressed indexes can store text in 30%–50% of its original size for counting while searching 20,000–50,000 patterns of 20 chars within a second.
- Compressed indexes can store text in 40%–80% of its original size while locating about 100,000 pattern occurrences per second.
- Compressed indexes use up to 18 times less space than a plain suffix array, but are one to three orders of magnitude slower for counting and locating.