LZ-End Parsing in Linear Time

DOI10.4230/LIPICS.ESA.2017.53zbMATH Open1442.68050OpenAlexW2758331792MaRDI QIDQ5111742FDOQ5111742

Authors Dominik Kempa, Dmitry Kosolobov

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7847/pdf/LIPIcs-ESA-2017-53.pdf/

zbMATH Keywords

linear timeconstruction algorithmLZ77LZ-End

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 5764825 (Why is no real title available?)
• A data structure for dynamic trees
• A faster grammar-based self-index
• A universal algorithm for sequential data compression
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Compressed representations of sequences and full-text indexes
• Design and implementation of an efficient priority queue
• Dynamic weighted ancestors
• Faster approximate pattern matching in compressed repetitive texts
• Faster lightweight Lempel-Ziv parsing
• Hybrid indexes for repetitive datasets
• Indexing text using the Ziv--Lempel trie
• Introduction to algorithms.
• Jewels of Stringology
• LZ-End Parsing in Linear Time
• LZ77-based self-indexing with faster pattern matching
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• On compressing and indexing repetitive sequences
• Optimal bounds for the predecessor problem
• Range predecessor and Lempel-Ziv parsing
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Self-indexing based on LZ77
• Space-efficient construction of compressed indexes in deterministic linear time
• Surpassing the information theoretic bound with fusion trees
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Time-space trade-offs for predecessor search
• Weighted ancestors in suffix trees

Cited in

(11)

• A space-optimal grammar compression
• scientific article; zbMATH DE number 1452981 (Why is no real title available?)
• New advances in rightmost Lempel-Ziv
• On the number of factors in the LZ-End factorization
• On the approximation ratio of LZ-end to LZ77
• Lempel-Ziv-like parsing in small space
• Comparison of LZ77-type parsings
• Linear-time suffix parsing for deterministic languages
• Bidirectional Text Compression in External Memory
• LZ-End Parsing in Linear Time
• On two LZ78-style grammars: compression bounds and compressed-space computation

Describes a project that uses

Uses Software

• LZ77

This page was built for publication: LZ-End Parsing in Linear Time

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