论文标题
在接近线性的时间内编辑距离：这是一个恒定的因素
Edit Distance in Near-Linear Time: it's a Constant Factor
论文作者
论文摘要
我们提出了一种算法，用于将两个长度的$ n $ in Time $ n^{1+ \ varepsilon} $之间的编辑距离近似于恒定因素，对于任何$ \ varepsilon> 0 $。我们的结果完成了最近的突破性论文[Chakraborty-Das-goldenberg-koucky-saks，focs'18]中提出的研究方向，该纸张显示了第一个恒定因子近似算法，具有（强）亚次级运行时间。 [Koucky-Saks，Stoc'20]和[Brakensiek-Rubinstein，stoc'20]的最新结果显示了接近线性的时间算法，这些算法在$ n $中获得添加剂近似值（等效地，恒定的因子近似值，当编辑距离值接近$ n $）。相反，对于任何输入字符串，我们的算法在接近线性的时间内获得了恒定的因子近似值。 与以前的算法相反，这些算法主要是在较小的子字上递归的算法，我们的算法逐渐使局部对编辑距离的贡献逐渐消除了逐渐较大的基因。为此，我们迭代地构建了一个距离甲骨文数据结构，以在输入字符串的所有子字符串上进行编辑距离的度量，长度为$ n^{i \ varepsilon} $，for $ i = 0,1，\ ldots，1/\ varepsilon $。距离Oracle以一定的平均意义近似于这些子字符串的编辑距离，足以估算整个编辑距离。
We present an algorithm for approximating the edit distance between two strings of length $n$ in time $n^{1+\varepsilon}$ up to a constant factor, for any $\varepsilon>0$. Our result completes a research direction set forth in the recent breakthrough paper [Chakraborty-Das-Goldenberg-Koucky-Saks, FOCS'18], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results of [Koucky-Saks, STOC'20] and [Brakensiek-Rubinstein, STOC'20] have shown near-linear time algorithms that obtain an additive approximation, near-linear in $n$ (equivalently, constant-factor approximation when the edit distance value is close to $n$). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input strings. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings, of length $n^{i\varepsilon}$ for $i=0,1,\ldots,1/\varepsilon$. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance.
