Linear-time text compression by longest-first substitution

DOI10.3390/A2041429zbMATH Open1445.68365OpenAlexW2085254467MaRDI QIDQ1662518FDOQ1662518

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)

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

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

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)

Cites Work

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

Cited In (6)

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