The compressed permuterm index

DOI10.1145/1868237.1868248MaRDI QIDQ3188992zbMATHOpenAlexFDO

Authors Paolo Ferragina, Rossano Venturini

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Burrows-Wheeler transformcompressed indexstring dictionaryindexing data structurepermuterm

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Searching and sorting (68P10) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Faster compressed dictionary matching
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Indexing compressed text
• Compressed indexes for dynamic text collections
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

Cited in

(14)

• On optimally partitioning a text to improve its compression
• Compressed string dictionary search with edit distance one
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Engineering a textbook approach to index massive string dictionaries
• Indexing permutations for binary strings
• Compressed string dictionaries via data-aware subtrie compaction
• Wheeler graphs: a framework for BWT-based data structures
• Lempel-Ziv-78 compressed string dictionaries
• Efficient techniques for approximate record matching modulo permutations
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Lightweight merging of compressed indices based on BWT variants
• Space-efficient substring occurrence estimation
• On the complexity of recognizing Wheeler graphs
• A new class of string transformations for compressed text indexing

This page was built for publication: The compressed permuterm index

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