Oblivious string embeddings and edit distance approximations
Oblivious string embeddings and edit distance approximations
复制标题
DOI：
10.5555/1109557.1109644
复制
发表时间：
2006-01
期刊：
影响因子：
--
通讯作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
中科院分区：
文献类型：
--
作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
我们引入了一个明显的嵌入，将编辑距离的长度n映射到在任何给定r的任何值r下最多的n/r的字符串。对于某些μ= O（1），我们证明是（几乎）最佳的嵌入。有效的算法更具体地在两个字符串之间近似于编辑距离，对于任何1>ε≥0，我们描述了一种算法，以计算两个字符串s和r长度n之间的编辑距离d（s，r）（n1+ε ），近似于min {n1-ε/3+o（1），（d（s，r/nε）1/2+o（1）}。对于ε= 0，我们得到了一个（n） - 时间算法，该算法近似于编辑距离min {n1/3+o（1），d（s，r）1/2+o（1）}，改善了Bar-Yossef等人的最新结果。
We introduce an oblivious embedding that maps strings of length n under edit distance to strings of length at most n/r under edit distance for any value of parameter r. For any given r, our embedding provides a distortion of Õ(r1+μ) for some μ = o(1), which we prove to be (almost) optimal. The embedding can be computed in Õ(21/μn) time.We also show how to use the main ideas behind the construction of our embedding to obtain an efficient algorithm for approximating the edit distance between two strings. More specifically, for any 1 > ε ≥ 0, we describe an algorithm to compute the edit distance D(S, R) between two strings S and R of length n in time Õ(n1+ε), within an approximation factor of min{n1-ε/3+o(1), (D(S, R/nε)1/2+o(1)}. For the case of ε = 0, we get a Õ(n)-time algorithm that approximates the edit distance within a factor of min{n1/3+o(1), D(S, R)1/2+o(1)}, improving the recent result of Bar-Yossef et al. [2].