Variable-Length Codes for Space-Efficient Grammar-Based Compression
Variable-Length Codes for Space-Efficient Grammar-Based Compression
复制标题
用于节省空间的基于语法的压缩的可变长度代码
DOI：
10.1007/978-3-642-34109-0_42
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Yoshimasa Takabatake
中科院分区：
文献类型：
--
作者：
毛利貴之;杉町勇和;東藤大樹;岩崎敦;横尾真;Yoshimasa Takabatake
字典是实现基于语法的压缩算法的关键数据结构。这样的字典应该在(1)秒内访问所有代码，以实现有效的压缩。一个由固定长度代码组成的标准字典消耗了大量的2logbit的内存。我们提出了一种新颖的字典，包括离线和在线基于语法的压缩算法的变长代码。在离线情况下，我们给出了一个字典，它的空间长度最多为{nlogn+ 2n+o(n), 3nlogσ(1 +o(1))}位，其中。在一个在线的设置中，我们提供了一个字典，最多有一个固定的字母表和未知的空间。实验表明，我们的字典所使用的内存比最先进的字典要小得多。
Dictionary is a crucial data structure to implement grammar-based compression algorithms. Such a dictionary should access any codes inO(1) time for an efficient compression. A standard dictionary consisting of fixed-length codes consumes a large amount of memory of 2nlognbits fornvariables. We present novel dictionaries consisting of variable-length codes for offline and online grammar-based compression algorithms. In an offline setting, we present a dictionary of at most min {nlogn+ 2n+o(n), 3nlogσ(1 +o(1))} bits of space where. In an online setting, we present a dictionary of at mostbits of space for a constant alphabet and unknownn. Experiments revealed that memory usage in our dictionary was much smaller than that of state-of-the-art dictionaries.