LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding

DOI10.1007/978-3-319-19929-0_19MaRDI QIDQ2942259zbMATH OpenOpenAlexFDO

Authors Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19929-0_19

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Faster compact on-line Lempel-Ziv factorization
• Efficient LZ78 factorization of grammar compressed text
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Computing Lempel-Ziv factorization online
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small

Cites work

• scientific article; zbMATH DE number 1629861 (Why is no real title available?)
• An online algorithm for lightweight grammar-based compression
• Compression of individual sequences via variable-rate coding
• Efficient LZ78 factorization of grammar compressed text
• Fast incremental planarity testing
• Improved dynamic dictionary matching
• On-line construction of suffix trees
• Self-indexed grammar-based compression
• Speeding up q-gram mining on grammar-based compressed texts
• Unified compression-based acceleration of edit-distance computation

Cited in

(10)

• Finger search in grammar-compressed strings
• Computing NP-hard repetitiveness measures via MAX-SAT
• Dynamic Path-decomposed Tries
• Lyndon factorization of grammar compressed texts revisited
• LZ78 substring compression in compressed space
• On the approximation ratio of LZ-end to LZ77
• A space-optimal grammar compression
• On two LZ78-style grammars: compression bounds and compressed-space computation
• LZ-ABT: a practical algorithm for \(\alpha \)-balanced grammar compression
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

This page was built for publication: LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding

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