On the approximation ratio of LZ-end to LZ77

DOI10.1007/978-3-030-86692-1_10MaRDI QIDQ2146133zbMATH OpenOpenAlexFDO

Authors Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Masayuki Takeda

Publication date 15 June 2022

Full work available at URL https://arxiv.org/abs/2106.01173

zbMATH Keywords

Lempel-Ziv 77 factorizationLZ-end factorizationperiod-doubling sequence

Mathematics Subject Classification ID

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

Cites work

• A faster grammar-based self-index
• A separation between RLSLPs and LZ77
• A universal algorithm for sequential data compression
• An optimal algorithm for computing the repetitions in a word
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• At the roots of dictionary compression: string attractors
• Automatic Sequences
• Compression of individual sequences via variable-rate coding
• Crochemore Factorization of Sturmian and Other Infinite Words
• Data compression via textual substitution
• Dynamic index and LZ factorization in compressed space
• Fast relative Lempel-Ziv self-index for similar sequences
• Free differential calculus. IV: The quotient groups of the lower central series
• scientific article; zbMATH DE number 6862137 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• Lempel-Ziv-like parsing in small space
• LZ-End Parsing in Linear Time
• LZ77-based self-indexing with faster pattern matching
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• On compressing and indexing repetitive sequences
• On the Approximation Ratio of Ordered Parsings
• On the size of overlapping Lempel-Ziv and Lyndon factorizations
• Optimal-Time Dictionary-Compressed Indexes
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• The Smallest Grammar Problem
• Towards a definitive measure of repetitiveness

Cited in

(6)

• A separation between RLSLPs and LZ77
• Converting SLP to LZ78 in almost Linear Time
• On the number of factors in the LZ-End factorization
• Hardness and approximability of bounded access Lempel Ziv coding
• On the complexity and approximability of bounded access Lempel Ziv coding
• LZ77 computation based on the run-length encoded BWT

Describes a project that uses

Uses Software

• LZ77

This page was built for publication: On the approximation ratio of LZ-end to LZ77

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