ABSTRACT
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].
Index Terms
- Oblivious string embeddings and edit distance approximations
Recommendations
Streaming algorithms for embedding and computing edit distance in the low distance regime
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of ComputingThe Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit ...
The string edit distance matching problem with moves
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithmsThe edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes and changes needed to convert R to S. Given a text string t of length n, and a pattern string p of length m, informally, the string edit ...
The string edit distance matching problem with moves
The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes, and changes needed to convert R to S. Given a text string t of length n, and a pattern string p of length m, informally, the string edit ...
Comments