Adaptive computation of the swap-insert correction distance

Abstract

The Swap-Insert Correction distance from a string S of length n to another string L of length m≥n on the alphabet [1.δ] 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 δ of the alphabet. We describe an algorithm computing this distance in time within O(δ2nmtδ.1), where for each [1.δ] there are occurrences of in S,mϵoccurrences of ¿ in L, and where "t = max [1.δ] min is a new parameter of the analysis, measuring one aspect of the difficulty of the instance. The difficulty "t is bounded by above by various terms, such as the length n of the shortest string S, and by the maximum number of occurrences of a single character in S (max[1.δ]). This result illustrates how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.