LZ77-based self-indexing with faster pattern matching

DOI10.1007/978-3-642-54423-1_63MaRDI QIDQ5405087zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(26)

• Random access in persistent strings and segment selection
• Finger search in grammar-compressed strings
• Grammar compressed sequences with rank/select support
• Comparison of LZ77-type parsings
• Flexible indexing of repetitive collections
• Lempel-Ziv factorization powered by space efficient suffix trees
• Self-indexing based on LZ77
• 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
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Universal compressed text indexing
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Rpair: rescaling RePair with Rsync
• 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
• 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)