Papers for

text processing engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Weighted edit distance approximated faster with constant factor

A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics

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.

Mon 14 SeptData Structures and Algorithms

The gist

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.

Open → 2609.14873v1