Efficient algorithms for Lempel-Ziv encoding

DOI10.1007/3-540-61422-2_148zbMath1502.68379OpenAlexW2067672042MaRDI QIDQ5054830

Wojciech Plandowski, Marek Karpinski, Leszek Gąsieniec, Wojciech Rytter

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61422-2_148

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items (25)

On the complexity of pattern matching for highly compressed two-dimensional texts. ⋮ Collage system: A unifying framework for compressed pattern matching. ⋮ Equality Testing of Compressed Strings ⋮ Pattern-matching problems for 2-dimensional images described by finite automata ⋮ On stricter reachable repetitiveness measures ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ The fully compressed subgroup membership problem ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Efficient retrieval of approximate palindromes in a run-length encoded string ⋮ A \textit{really} simple approximation of smallest grammar ⋮ An efficient algorithm to test square-freeness of strings compressed by straight-line programs ⋮ Polynomial braid combing ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Approximation of grammar-based compression via recompression ⋮ The complexity of compressed membership problems for finite automata ⋮ Leaf languages and string compression ⋮ Computing Longest Common Substring and All Palindromes from Compressed Strings ⋮ Recognizing string graphs in NP ⋮ Efficient algorithms to compute compressed longest common substrings and compressed palindromes ⋮ Tracing compressed curves in triangulated surfaces ⋮ Compressed automata for dictionary matching ⋮ Tree compression with top trees ⋮ The complexity of compressing subsegments of images described by finite automata ⋮ Longest substring palindrome after edit

Cites Work

• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Optimal two-dimensional compressed matching
• Optimal parallel algorithms for periods, palindromes and squares
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient algorithms for Lempel-Ziv encoding