An online algorithm for lightweight grammar-based compression

DOI10.3390/A5020214MaRDI QIDQ1736509zbMATH OpenOpenAlexFDO

Authors Shirou Maruyama, Hiroshi Sakamoto, Masayuki Takeda

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a5020214

zbMATH Keywords

approximation algorithmonline algorithmgrammar-based compressionlossless compression

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Recommendations

• String Processing and Information Retrieval
• A space-optimal grammar compression
• Approximation of grammar-based compression via recompression
• A fully linear-time approximation algorithm for grammar-based compression
• Approximation of Grammar-Based Compression via Recompression

Cited in

(9)

• Grammar Compression by Induced Suffix Sorting
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• General document retrieval in compact space
• A space-optimal grammar compression
• Grammar-Based Compression in a Streaming Model
• LZ-ABT: a practical algorithm for \(\alpha \)-balanced grammar compression
• Linear-time off-line text compression by longest-first substitution.
• Rpair: rescaling RePair with Rsync
• siEDM: an efficient string index and search algorithm for edit distance with moves

This page was built for publication: An online algorithm for lightweight grammar-based compression

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