Fast approximation algorithm improves weighted edit distance calculations
Metric Weighted Edit Distance: $(3+\varepsilon)$-Approximation in $\widetilde O_\varepsilon(N^{1.6})$ Time
Data Structures and Algorithms
Summary
Measuring how different two strings are is useful in many areas like spell checking or DNA analysis. The authors present a faster way to estimate the weighted edit distance, which accounts for different costs of changes and insertions, under a specific mathematical assumption on these costs. Their method gives a result that is close to the true distance without ever underestimating it and works efficiently even on large strings. They combine previous sampling methods and data structures with new insights about breaking strings into manageable pieces for comparison.
What this means in practice
- •For text processing engineers: Improve the speed of approximate string matching in systems that handle large-scale spell checking with varying edit costs.
- •For bioinformatics pipeline developers: Accelerate approximate sequence alignment tasks when costs of mutations form a metric, enhancing genome analysis workflows.
Authors
Debarati Das, Evangelos Kipouridis, Tomasz Kociumaka
Abstract
For every $0 < \varepsilon \le 1$, we give a randomized $(3+\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\widetilde{O}(N^{8/5}/\varepsilon^{16/5})$, where $\widetilde{O}$ suppresses factors polynomial in $\log(N/\varepsilon)$. The dependence on $N$ matches that of the fastest known $(3+\varepsilon)$-approximation for unit-cost edit distance. The algorithm never underestimates the edit distance and achieves the approximation guarantee with inverse-polynomial failure probability in $N$. The running time bound assumes constant-time exact arithmetic operations and metric queries, and it is independent of the numerical range of the edit costs. We build on three tools: the sampling framework of Chakraborty, Das, Goldenberg, Koucký, and Saks (J. ACM, 2020), with subsequent refinements by Andoni (2020); Kuszmaul's removal of inexpensive characters (ICALP 2019); and Klein's data structure for distances in planar graphs (SODA 2005). Our new ingredients include, among others, a decomposition of one string into pieces of bounded length with highly structured total deletion costs. This decomposition lets us compare all pieces against a small family of substrings of the other string.