文章基本信息

标题：A Space-Optimal Grammar Compression
本地全文：下载
作者：Yoshimasa Takabatake ; Tomohiro I ; Hiroshi Sakamoto 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：67:1-67:15
DOI：10.4230/LIPIcs.ESA.2017.67
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 sigma, the smallest CFG is O(log N)-approximable in the offline setting and O(log N log^* 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 log (n!/n^sigma) + n + o(n) bits. Although there is an online grammar compression algorithm that directly computes the succinct encoding of its output CFG with O(log N log^* 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 log log n) compression time. In addition we propose several techniques to boost grammar compression and show their efficiency by computational experiments.
关键词：Grammar compression; fully-online algorithm; succinct data structure