Weighted edit distance approximated faster with constant factor
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
Data Structures and Algorithms
Summary
Measuring how different two strings are is useful in many areas from spelling correction to DNA analysis. When the cost to change one character into another varies a lot, calculations get much slower. The authors design an algorithm that quickly estimates these differences within about three times the true cost. Their method works even when strings have different lengths and edit costs come from any kind of metric.
What this means in practice
- •For bioinformatics teams: Estimate DNA or protein sequence similarity faster when mutation costs vary irregularly across letters.
- •For text processing engineers: Quickly approximate weighted spelling or transcription differences using diverse cost measures without needing long computations.
Authors
Ethan Mader, Borna Tavasoli, Jihan Wang
Abstract
We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^δ)$-approximation with $\widetilde{O}(n^{2-δ})$ running time for every fixed $0 < δ< 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.