Faster 3x approximate edit distance algorithms for strings with arbitrary costs
Factor Three Approximation for Edit Distance
Data Structures and Algorithms
Summary
Edit distance measures how many changes are needed to turn one string into another, which is useful in spell checking and DNA analysis. The authors developed randomized algorithms that find an approximate answer three times as close as the best exact methods, but much faster for long strings. They also prove that for some types of cost measures, no fast approximations are possible. Additionally, they provide faster algorithms when costs meet certain conditions like symmetry or metric properties.
What this means in practice
- •For text processing engineers: Speed up approximate string similarity calculations in spell checkers and search engines using faster 3-approximation algorithms.
- •For bioinformatics teams: Improve time efficiency of approximate sequence alignment when edit costs satisfy metric or symmetry conditions.
Authors
Egor Gorbachev
Abstract
We give randomized algorithms for $3$-approximate edit distance in $\widetilde{\mathcal{O}}(N^{11/6})$ time for unweighted edit distance and in $\widetilde{\mathcal{O}}(N^{40/21})$ time for arbitrary metric edit weights, where $N$ is the total input length. For non-metric costs, we prove an unconditional $Ω(N^2)$ oracle-query lower bound for every approximation factor depending only on $N$, even for symmetric weights or weights satisfying the triangle inequality (but not both). Under the Orthogonal Vectors Hypothesis, we show a similar result for constant-size alphabets. This holds even for symmetric weights over a size-$3$ alphabet or triangle-inequality weights over a size-$2$ alphabet. In contrast, for symmetric weights over a binary alphabet we show an $\widetilde{\mathcal{O}}(N^{40/21})$-time $3$-approximation algorithm.