Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
复制标题
动态相对压缩、动态部分和和子串串联
DOI：
10.1007/s00453-017-0380-7
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Søren Vind
中科院分区：
文献类型：
--
作者：
Philip Bille;Patrick Hagge Cording;Inge Li Gørtz;Frederik Rye Skjoldjensen;Hjalte Wedel Vildhøj;Søren Vind
给定一个静态参考字符串R和源字符串S，S相对于R的相对压缩是S的编码。作为对R的一系列引用。相对压缩方案是一个经典的压缩模型成功地压缩了高度重复的大规模数据集，例如基因组和Web-DATA。我们在动态设置中启动相对压缩的研究，其中压缩源字符串s受到编辑操作的约束。目标是紧凑地维护压缩表示形式，同时支持编辑并允许有效地随机访问（未压缩）源字符串。我们提出了新的数据结构，可在最佳相对压缩的大小中使用空间线性，以实现最佳的更新和查询时间，几乎所有参数组合。我们还提出了用于限制和扩展更新集的解决方案。为了实现这些结果，我们重新审视动态部分总和问题和基因串联问题。我们为这些问题提供了新的最佳或接近最佳范围。插入我们的新结果，我们还立即获得了针对具有通配符问题的模式以及动态文本和静态模式匹配问题的字符串索引的新界限。
Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string S is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem.
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
R. Grossi;Ankur Gupta;J. Vitter
通讯作者：
R. Grossi;Ankur Gupta;J. Vitter
影响因子：
1.3
作者：
Navarro, Gonzalo;Sadakane, Kunihiko
通讯作者：
Sadakane, Kunihiko