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

grammar-based text compressionlinear-time algorithmssuffix trees

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)

Review text

Summary: We consider grammar-based text compression with \textit{longest first substitution} (LFS), where non-overlapping occurrences of a longest repeating factor of the input text are replaced by a new non-terminal symbol. We present the first linear-time algorithm for LFS. Our algorithm employs a new data structure called \textit{sparse lazy suffix trees}. We also deal with a more sophisticated version of LFS, called LFS2, that allows better compression. The first linear-time algorithm for LFS2 is also presented.

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

• 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
• 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?)
• 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)

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