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

period-doubling sequenceLempel-Ziv 77 factorizationLZ-end factorization

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 6862137 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• 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
• 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
• Lempel-Ziv-like parsing in small space
• 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

(4)

• Converting SLP to LZ78 in almost Linear Time
• LZ77 computation based on the run-length encoded BWT
• A separation between RLSLPs and LZ77
• On the number of factors in the LZ-End factorization

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)