Efficient LZ78 factorization of grammar compressed text

DOI10.1007/978-3-642-34109-0_10MaRDI QIDQ4913725zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Publication date 8 April 2013

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.4607

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)

Abstract: We present an efficient algorithm for computing the LZ78 factorization of a text, where the text is represented as a straight line program (SLP), which is a context free grammar in the Chomsky normal form that generates a single string. Given an SLP of size $n$ representing a text $S$ of length $N$, our algorithm computes the LZ78 factorization of $T$ in $O(nsqrtN+mlogN)$ time and $O(nsqrtN+m)$ space, where $m$ is the number of resulting LZ78 factors. We also show how to improve the algorithm so that the $nsqrtN$ term in the time and space complexities becomes either $nL$, where $L$ is the length of the longest LZ78 factor, or $(N-alpha)$ where $alphageq0$ is a quantity which depends on the amount of redundancy that the SLP captures with respect to substrings of $S$ of a certain length. Since $m=O(N/lo{g}_{s}igmaN)$ where $sigma$ is the alphabet size, the latter is asymptotically at least as fast as a linear time algorithm which runs on the uncompressed string when $sigma$ is constant, and can be more efficient when the text is compressible, i.e. when $m$ and $n$ are small.

Recommendations

• Efficient Lyndon factorization of grammar compressed text
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Converting SLP to LZ78 in almost Linear Time
• Lyndon factorization of grammar compressed texts revisited
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small

Cited in

(18)

• Linear-time text compression by longest-first substitution
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• Speeding up q-gram mining on grammar-based compressed texts
• Lempel Ziv computation in small space (LZ-CISS)
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• Self-indexed Text Compression Using Straight-Line Programs
• An Efficient LLL Gram Using Buffered Transformations
• Straight-line programs: a practical test (extended abstract)
• LZ77 factorisation of trees
• Efficient Lyndon factorization of grammar compressed text
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Conversion from RLBWT to LZ77
• Engineering practical Lempel-Ziv tries
• Lyndon factorization of grammar compressed texts revisited
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• Automata, Languages and Programming
• LZ77 computation based on the run-length encoded BWT

This page was built for publication: Efficient LZ78 factorization of grammar compressed text

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