### Compressed text indexes: From theory to practiceCompressed text indexes: From theory to practice

Access Restriction
Subscribed

 Author Ferragina, Paolo ♦ Gonzlez, Rodrigo ♦ Navarro, Gonzalo ♦ Venturini, Rossano Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Text indexing ♦ Bioinformatics databases ♦ Coding and information theory ♦ Data storage representation ♦ Data structures ♦ Indexing methods ♦ Text compression ♦ Textual databases Abstract A compressed full-text self-index represents a text in a compressed form and still answers queries efficiently. This represents a significant advancement over the (full-)text indexing techniques of the previous decade, whose indexes required several times the size of the text. Although it is relatively new, this algorithmic 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 article 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 $\textit{Pizza&Chili}$ site, which offers tuned implementations and a standardized API for the most successful compressed full-text self-indexes, together with effective test-beds 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 algorithmic technology. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 13 Page Count 20 Starting Page 1.12 Ending Page 1.31

#### Open content in new tab

Source: ACM Digital Library