Real-time traversal in grammar-based compressed files
Real-time traversal in grammar-based compressed files
复制标题
基于语法的压缩文件中的实时遍历
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
P. Sant
中科院分区：
文献类型：
--
作者：
L. Gąsieniec;R. Kolpakov;I. Potapov;P. Sant
仅提供摘要表格。在文本压缩应用程序中，能够在不需要(完整)解压缩的情况下处理压缩数据非常重要。在这种情况下，研究允许时间/空间高效地访问压缩文件的任何片段而不被强制执行完全解压缩的压缩方法是至关重要的。在这里，我们研究在基于语法的压缩的背景下，从压缩文件中实时恢复连续符号。在这种设置中，压缩文本被表示为一个小的(几个KB)词典D(包含一组码字)和一个基于从词典D中提取的符号的非常长的(几个Mb)字符串。这种压缩的空间效率与基于Lempel-Ziv方法的标准压缩方法相当。我们证明，人们可以访问原始文本的连续符号，在恒定的时间和额外的O(|D|)空间内从一个符号移动到另一个符号。该算法是对(L.Gasieniec等，Proc.)中提出的在线线性(摊销)时间算法的改进。第13国际交响乐。关于基金。的比较。Theo.，LNCS，第2138卷，第138-152页，2001)。
Summary form only given. In text compression applications, it is important to be able to process compressed data without requiring (complete) decompression. In this context it is crucial to study compression methods that allow time/space efficient access to any fragment of a compressed file without being forced to perform complete decompression. We study here the real-time recovery of consecutive symbols from compressed files, in the context of grammar-based compression. In this setting, a compressed text is represented as a small (a few Kb) dictionary D (containing a set of code words), and a very long (a few Mb) string based on symbols drawn from the dictionary D. The space efficiency of this kind of compression is comparable with standard compression methods based on the Lempel-Ziv approach. We show, that one can visit consecutive symbols of the original text, moving from one symbol to another in constant time and extra O(|D|) space. This algorithm is an improvement of the on-line linear (amortised) time algorithm presented in (L. Gasieniec et al, Proc. 13th Int. Symp. on Fund. of Comp. Theo., LNCS, vol.2138, p.138-152, 2001).