How Compression and Approximation Affect Efficiency in String Distance Measures
How Compression and Approximation Affect Efficiency in String Distance Measures
复制标题
压缩和近似如何影响弦距离测量的效率
DOI：
10.1137/1.9781611977073.112
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
and Saha, Barna
中科院分区：
文献类型：
--
作者：
Ganesh, Arun;Kociumaka, Tomasz;Loncoln, Andrea;and Saha, Barna
真实世界的数据通常以压缩形式出现。直接分析压缩的数据（不首先解压缩）可以节省数量级的空间和时间。在这项工作中，我们专注于基本序列比较问题，并试图量化底层数据高度可压缩时的时间复杂度增益。我们考虑语法压缩，它结合了许多实际相关的压缩方案，如Lempel-Ziv家族、字典方法等。对于总长度为nand总压缩大小的两个字符串，已知编辑距离和最长公共子序列（LCS）可以在timeÕ（nN）中精确计算，而对于未压缩设置则为toO（N2）。许多现实世界的应用需要同时对齐多个序列，已知最快的中位数编辑距离和LCS的精确算法运行inO（Nk）时间，而中心编辑距离的时间复杂度为o （N2k）。这自然提出了一个问题，如果压缩可以帮助显著减少运行时间，分叉≥3，可能是太（Nk/2nk/2），或者更乐观地说，太（Nnk-1）。1不幸的是，我们展示了新的下界，排除了任何改进beyondΩ（Nk-1n）时间对于任何这些问题，假设强指数时间假设（SETH），其中againnand分别代表总长度和总压缩大小。这回答了Abboud、Backurs、Bringmann和k<e:1> nnemann （FOCS'17）提出的一个开放性问题。存在这样的负面结果，我们问是否允许近似可以帮助，我们表明近似和压缩一起可以对多个字符串和两个字符串都非常有效。我们为序列的中位数编辑距离开发了anÕ（Nk/2nk/2）时间FPTAS，从而使高度可压缩序列的维数节省了近一半。相比之下，noO(Nk -Ω (1)) time PTAS在未压缩设置下存在中值编辑距离问题。对中心编辑距离问题进行了改进。对于两个字符串，我们得到编辑距离和LCS的时间FPTAS；请注意，当≪N1/4时，此运行时间为iso(N)。相比之下，对于未压缩的字符串，甚至没有一个LCS的次二次算法在近似因子中具有小于多项式的间隙。基于我们的近似算法的洞察力，我们还获得了许多基本距离度量的一些新的和改进的结果，包括编辑距离，汉明距离和移位距离。
Real-world data often comes in compressed form. Analyzing compressed data directly (without first decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes such as the Lempel–Ziv family, dictionary methods, and others. For two strings of total lengthNand total compressed sizen, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in timeÕ(nN), as opposed toO(N2) for the uncompressed setting. Many real-world applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS ofkstrings run inO(Nk) time, whereas the one for center edit distance has a time complexity ofO(N2k). This naturally raises the question if compression can help to reduce the running time significantly fork≥ 3, perhaps toO(Nk/2nk/2) or, more optimistically, toO(Nnk–1).1Unfortunately, we show new lower bounds that rule out any improvement beyondΩ(Nk–1n) time for any of these problems assuming the Strong Exponential Time Hypothesis (SETH), where againNandnrepresent the total length and the total compressed size, respectively. This answers an open question of Abboud, Backurs, Bringmann, and Künnemann (FOCS'17).In presence of such negative results, we ask if allowing approximation can help, and we show that approximation and compression together can be surprisingly effective for both multiple and two strings.We develop anÕ(Nk/2nk/2)-time FPTAS for the median edit distance ofksequences, leading to a saving of nearly half the dimensions for highly-compressible sequences. In comparison, noO(Nk–Ω(1))-time PTAS is known for the median edit distance problem in the uncompressed setting. We obtain an improvement from for the center edit distance problem. For two strings, we get an -time FPTAS for both edit distance and LCS; note that this running time iso(N) whenevern≪N1/4. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain several new and improved results for many fundamental distance measures including the edit, Hamming, and shift distances.