Application of Lempel-Ziv factorization to the approximation of grammar-based compression
Application of Lempel-Ziv factorization to the approximation of grammar-based compression
复制标题
DOI：
10.1016/s0304-3975(02)00777-6
复制
发表时间：
2003-06-13
影响因子：
1.1
通讯作者：
Rytter, W
中科院分区：
文献类型：
--
作者：
Rytter, W
我们引入了一种新的上下文无关文法--A-VL-文法，并证明了它们对基于文法的压缩的适用性。利用这种类型的文法，我们给出了长度为it的给定字符串在字母表Sigma上基于语法的最小压缩的0(nlogSigma\)时间和0(Logn)比近似，以及将大小为k的LZ77编码到大小为0(Klogn)的基于语法的编码的0(Klogn)时间变换。这篇论文的初步版本已独立于Charikar等人在Rytter(计算机科学中的组合模式匹配，第2373卷，Springer，柏林，2000年6月，第20-31页)中提出。(STOEC，2002)，其中基于语法的近似受到了不同结构和更复杂类型的语法的攻击(α小于或等于1-1/2根2的阿尔法平衡语法)。AVL-语法是一种非常自然和简单的基于语法的压缩工具，它是经典的AVL-树的直接扩展。(C)2002 Elsevier Science B.V.保留所有权利。
We introduce new type of context-free grammars, A VL-grammars, and show their applicability to grammar-based compression. Using this type of grammars we present 0(n log \Sigma\) time and 0(log n)-ratio approximation of minimal grammar-based compression of a given string of length it over an alphabet Sigma and 0(k log n) time transformation of LZ77 encoding of size k into a grammar-based encoding of size 0(k log n). A preliminary version of this paper has been presented in Rytter (Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 2373, Springer, Berlin, June 2000, pp. 20-31), independently of Charikar et al. (STOC, 2002), where grammar-based approximation has been attacked with different construction and a more complicated type of grammars (alpha-balanced grammars for alpha less than or equal to 1 - 1/2 root2). The AVL-grammar is a very natural and simple tool for grammar based compression, it is a straightforward extension of the classical AVL-tree. (C) 2002 Elsevier Science B.V. All rights reserved.