Linear-time text compression by longest-first substitution

DOI10.3390/A2041429MaRDI QIDQ1662518zbMATH OpenOpenAlexFDO

Authors Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Publication date 20 August 2018

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/a2041429

zbMATH Keywords

linear-time algorithmssuffix treesgrammar-based text compression

Mathematics Subject Classification ID

Data structures (68P05) 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)

Recommendations

• Linear-time off-line text compression by longest-first substitution.
• scientific article; zbMATH DE number 1187116
• Longest common extensions with recompression
• Efficient LZ78 factorization of grammar compressed text
• String Processing and Information Retrieval

Cites work

• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• scientific article; zbMATH DE number 2086666 (Why is no real title available?)
• scientific article; zbMATH DE number 1445329 (Why is no real title available?)
• A fully linear-time approximation algorithm for grammar-based compression
• A unified algorithm for accelerating edit-distance computation via text-compression
• A universal algorithm for sequential data compression
• An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximate matching of run-length compressed strings
• Collage system: A unifying framework for compressed pattern matching.
• Compression of individual sequences via variable-rate coding
• Data structures and algorithms for the string statistics problem
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Grammar-based codes: a new class of universal lossless source codes
• Linear-time off-line text compression by longest-first substitution.
• On-line construction of suffix trees
• Processing Compressed Texts: A Tractability Border
• Textual data compression in computational biology: algorithmic techniques
• Universal lossless compression via multilevel pattern matching

Cited in

(6)

• Searching for smallest grammars on large sequences and application to DNA
• Linear-time off-line text compression by longest-first substitution.
• Converting SLP to LZ78 in almost Linear Time
• Bidirectional Text Compression in External Memory
• The smallest grammar problem as constituents choice and minimal grammar parsing
• Using static suffix array in dynamic application: case of text compression by longest first substitution

This page was built for publication: Linear-time text compression by longest-first substitution

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