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

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

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

(29)

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

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)