论文标题
一种简单的sublrinear算法，用于差距编辑距离
A Simple Sublinear Algorithm for Gap Edit Distance
论文作者
论文摘要
我们研究了估计两个$ n $ character字符串之间的编辑距离的问题。尽管最坏情况下的精确计算被认为需要接近二次的时间，但先前的工作表明，在某些制度中，可以在子线上时间解决以下{\ em Gap Edit距离}问题：区分距离$ \ le K $ $ \ le K $和$> k^2 $的输入。我们的主要结果是该基准的一种非常简单的算法，该算法是及时运行的$ \ tilde o（n/\ sqrt {k}）$，尤其是解决了在相关$ k $的整个范围内获得真正倾斜时间的开放问题。 Building on the same framework, we also obtain a $k$-vs-$k^2$ algorithm for the one-sided preprocessing model with $\tilde O(n)$ preprocessing time and $\tilde O(n/k)$ query time (improving over a recent $\tilde O(n/k+k^2)$-query time algorithm for the same problem [GRS'20].
We study the problem of estimating the edit distance between two $n$-character strings. While exact computation in the worst case is believed to require near-quadratic time, previous work showed that in certain regimes it is possible to solve the following {\em gap edit distance} problem in sub-linear time: distinguish between inputs of distance $\le k$ and $>k^2$. Our main result is a very simple algorithm for this benchmark that runs in time $\tilde O(n/\sqrt{k})$, and in particular settles the open problem of obtaining a truly sublinear time for the entire range of relevant $k$. Building on the same framework, we also obtain a $k$-vs-$k^2$ algorithm for the one-sided preprocessing model with $\tilde O(n)$ preprocessing time and $\tilde O(n/k)$ query time (improving over a recent $\tilde O(n/k+k^2)$-query time algorithm for the same problem [GRS'20].
