Compressed text indexes, from theory to practice

DOI10.1145/1412228.1455268MaRDI QIDQ5406182zbMATH OpenOpenAlexFDO

Authors Paolo Ferragina, Rossano Venturini, Rodrigo González, Gonzalo Navarro

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1412228.1455268

zbMATH Keywords

bioinformatics databasescoding and information theorydata storage representationdata structuresindexing methodstext compressiontext indexingtextual databases

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms (68W40)

Recommendations

• Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
• Approximate string matching with compressed indexes
• Compressed Text Indexes with Fast Locate
• A compressed text index on secondary memory
• Space-efficient construction of Lempel-Ziv compressed text indexes

Cited in

(26)

• Faster entropy-bounded compressed suffix trees
• Approximate string matching with compressed indexes
• Wheeler graphs: a framework for BWT-based data structures
• Practical compressed suffix trees
• Fixed block compression boosting in FM-indexes: theory and practice
• Distribution-aware compressed full-text indexes
• Grammar index by induced suffix sorting
• Comparison between text compression algorithms in biological sequences
• Improved and extended locating functionality on compressed suffix arrays
• Stronger Lempel-Ziv based compressed text indexing
• Compressed text indexing with wildcards
• Space-efficient substring occurrence estimation
• Approximate search of short patterns with high error rates using the 01^ 0 lossless seeds
• Compressed string dictionary search with edit distance one
• Locally compressed suffix arrays
• Lossless seeds for searching short patterns with high error rates
• Compressed Text Indexes with Fast Locate
• String matching with alphabet sampling
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Space-efficient construction of Lempel-Ziv compressed text indexes
• scientific article; zbMATH DE number 6469201 (Why is no real title available?)
• Comparative genomics with succinct colored de Bruijn graphs
• Algorithms for Galois words: detection, factorization, and rotation
• LZ78 substring compression in compressed space
• A simple representation of tree covering utilizing balanced parentheses and efficient implementation of average-case optimal RMQs
• Grammar index by induced suffix sorting

This page was built for publication: Compressed text indexes, from theory to practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5406182)