Near-optimal sublinear time algorithms for Ulam distance
Near-optimal sublinear time algorithms for Ulam distance
复制标题
Ulam 距离的近最优亚线性时间算法
DOI：
10.1137/1.9781611973075.8
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;Huy L. Nguyen
我们给出了接近距离的边界，用于估计两个不变的词（ULAM距离）之间的编辑距离，并在两个长度d和编辑距离r的情况下以恒定的近似为单位，我们的算法在时间上运行（ d/r +√d）并向R输出常数近似。我们还证明了匹配的下限（最多到对数项）。 [Andoni-Indyk-Krauthgamer，Soda'09]和[Batu-ergun-Kilian-Magen-Raskhodnikhodnikova-rubinfeld-sami，stoc'03]。
We give near-tight bounds for estimating the edit distance between two non-repetitive strings (Ulam distance) with constant approximation, in sub-linear time. For two strings of length d and at edit distance R, our algorithm runs in time Õ(d/R + √d) and outputs a constant approximation to R. We also prove a matching lower bound (up to logarithmic terms). Both upper and lower bounds are improvements over previous results from, respectively, [Andoni-Indyk-Krauthgamer, SODA'09] and [Batu-Ergun-Kilian-Magen-Raskhodnikova-Rubinfeld-Sami, STOC'03].