# Adaptive Computation of the Swap-Insert Correction Distance

arXiv: https://arxiv.org/abs/1504.07298 · HTML: https://mlsanity.com/paper/1504.07298/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2015.

## Built on by (most cited first, 1 of 1)

- [On the k-Hamming and k-Edit Distances](https://mlsanity.com/paper/2306.09144/) (2023)

## Abstract (arXiv)

The Swap-Insert Correction distance from a string S of length n to another string L of length m≥ n on the alphabet [1..d] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size d of the alphabet. We describe an algorithm computing this distance in time within O(d2 nm gd-1), where there are nα occurrences of α in S, mα occurrences of α in L, and where g=maxα∈[1..d] minnα,mα-nα measures the difficulty of the instance. The difficulty g is bounded by above by various terms, such as the length of the shortest string S, and by the maximum number of occurrences of a single character in S. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.