On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation

DOI10.1007/978-3-319-67428-5_5zbMath1454.68043arXiv1705.09538OpenAlexW2619414470MaRDI QIDQ5150918

Golnaz Badkobeh, Tomasz Kociumaka, Simon J. Puglisi, Shunsuke Inenaga, Dmitry Kosolobov, Travis Gagie

Publication date: 16 February 2021

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

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

zbMATH Keywords

compressionsmallest grammarLZ78LZDLZMW

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Related Items (1)

Dynamic Path-decomposed Tries

Cites Work

• On compressing and indexing repetitive sequences
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• The smallest grammar problem revisited
• A Faster Grammar-Based Self-index
• LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
• Self-Indexed Grammar-Based Compression
• Access, Rank, and Select in Grammar-compressed Strings
• The Smallest Grammar Problem
• Efficient randomized pattern-matching algorithms
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Efficient Lyndon Factorization of Grammar Compressed Text
• LZ-End Parsing in Linear Time
• Fast incremental planarity testing
• Random Access to Grammar-Compressed Strings and Trees

This page was built for publication: On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation