Linear-time text compression by longest-first substitution

DOI10.3390/a2041429zbMath1445.68365OpenAlexW2085254467MaRDI QIDQ1662518

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

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

linear-time algorithmssuffix treesgrammar-based text compression

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) Data structures (68P05) Algorithms on strings (68W32)

Related Items (4)

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 ⋮ The smallest grammar problem as constituents choice and minimal grammar parsing ⋮ Bidirectional Text Compression in External Memory

Cites Work

• Textual data compression in computational biology: algorithmic techniques
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• 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.
• On-line construction of suffix trees
• Data structures and algorithms for the string statistics problem
• A fully linear-time approximation algorithm for grammar-based compression
• Processing Compressed Texts: A Tractability Border
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Universal lossless compression via multilevel pattern matching
• Grammar-based codes: a new class of universal lossless source codes
• String Processing and Information Retrieval
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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