Edit Distance in Near-Linear Time: it's a Constant Factor
Edit Distance in Near-Linear Time: it's a Constant Factor
复制标题
近线性时间编辑距离：它是一个常数因子
DOI：
10.1109/focs46700.2020.00096
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Nosatzki, Negev Shekel
中科院分区：
文献类型：
--
作者：
Andoni, Alexandr;Nosatzki, Negev Shekel
我们提出了一种算法，用于在时间 n1+ε 内近似两个长度为 n 的字符串之间的编辑距离，对于任何 ，直到一个常数因子。我们的结果完成了最近突破性论文 [1] 中提出的研究方向，该论文展示了第一个具有（强）次二次运行时间的常数因子近似算法。最近的结果[2]、[3]仅在编辑距离接近最大的限制下才显示出近线性复杂度（相当于，存在近线性加法近似）。相比之下，我们的算法对于任何输入字符串都能在近线性运行时间内获得常数因子近似值。
We present an algorithm for approximating the edit distance between two strings of length n in time n1+ε, for any , up to a constant factor. Our result completes a research direction set forth in the recent breakthrough paper [1], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results [2], [3] have shown near-linear complexity only under the restriction that the edit distance is close to maximal (equivalently, there is a near-linear additive approximation). In contrast, our algorithm obtains a constant-factor approximation in near-linear running time for any input strings.
登录
查看更多内容
DOI：
10.5555/1109557.1109644
发表时间：
2006-01
期刊：
--
影响因子：
--
作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
通讯作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
Ramsey 分区和邻近数据结构
DOI：
--
发表时间：
2005
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Mendel;A. Naor
通讯作者：
A. Naor
有效地近似伪随机字符串之间的编辑距离
DOI：
--
发表时间：
2018
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
William Kuszmaul
通讯作者：
William Kuszmaul
在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce
影响因子：
2.5
作者：
Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
通讯作者：
Seddighin, Saeed
编辑距离的平滑复杂度
DOI：
10.1145/2344422.2344434
发表时间：
2008
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Alexandr Andoni;Robert Krauthgamer
通讯作者：
Robert Krauthgamer