LZ77-based self-indexing with faster pattern matching

DOI10.1007/978-3-642-54423-1_63zbMATH Open1405.68104OpenAlexW226134553MaRDI QIDQ5405087FDOQ5405087

Authors: Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, Simon J. Puglisi 

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-54423-1_63

Recommendations

• A faster grammar-based self-index
• Self-indexing based on LZ77
• Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
• Indexed multi-pattern matching
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (26)

• Finger search in grammar-compressed strings
• Grammar compressed sequences with rank/select support
• Comparison of LZ77-type parsings
• Flexible indexing of repetitive collections
• Self-indexing based on LZ77
• Lempel-Ziv factorization powered by space efficient suffix trees
• Document listing on repetitive collections with guaranteed performance
• String Indexing with Compressed Patterns
• A faster grammar-based self-index
• Composite repetition-aware data structures
• Relations between greedy and bit-optimal LZ77 encodings
• Grammar-compressed indexes with logarithmic search time
• On the approximation ratio of LZ-end to LZ77
• Top tree compression of tries
• Arithmetics on suffix arrays of Fibonacci words
• Title not available (Why is that?)
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Universal compressed text indexing
• Rpair: rescaling RePair with Rsync
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• LZ-End Parsing in Linear Time
• siEDM: an efficient string index and search algorithm for edit distance with moves
• A self-index on block trees
• Sublinear time Lempel-Ziv (LZ77) factorization
• Random access in persistent strings and segment selection
• Dynamic index and LZ factorization in compressed space

This page was built for publication: LZ77-based self-indexing with faster pattern matching

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