A Space-Optimal Grammar Compression
A Space-Optimal Grammar Compression
复制标题
DOI：
10.4230/lipics.esa.2017.67
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yoshimasa Takabatake;I. Tomohiro;H. Sakamoto
中科院分区：
文献类型：
--
作者：
Yoshimasa Takabatake;I. Tomohiro;H. Sakamoto
语法压缩是一种上下文无关文法(CFG)，它确定性地派生出单个字符串。对于大小为σ的字母表上的长度为N的输入串，最小cfg在脱机设置中是O(LgN)可近似的，在在线设置中是O(lgN LG∗N)可近似的。此外，用n个变量的乔姆斯基范式表示CFG的信息论下界是lg(n！/n)+n+o(N)比特。虽然已经有一种在线语法压缩算法直接计算其输出cfg的简明编码，并具有O(lgN LG∗N)的近似保证，但其工作空间的优化问题仍然是悬而未决的。我们提出了一个完全在线的算法，它需要最少的工作空间，渐近等于O(N，lg，lgN)压缩时间的下界。此外，我们还提出了几种提高语法压缩的技术，并通过计算实验证明了它们的有效性。1998 ACM学科分类E.4编码与信息论
A grammar compression is a context-free grammar (CFG) deriving a single string deterministically. For an input string of length N over an alphabet of size σ, the smallest CFG is O(lgN)approximable in the offline setting and O(lgN lg∗N)-approximable in the online setting. In addition, an information-theoretic lower bound for representing a CFG in Chomsky normal form of n variables is lg(n!/n) + n + o(n) bits. Although there is an online grammar compression algorithm that directly computes the succinct encoding of its output CFG with O(lgN lg∗N) approximation guarantee, the problem of optimizing its working space has remained open. We propose a fully-online algorithm that requires the fewest bits of working space asymptotically equal to the lower bound in O(N lg lgn) compression time. In addition we propose several techniques to boost grammar compression and show their efficiency by computational experiments. 1998 ACM Subject Classification E.4 Coding and Information Theory