Finding the subset of a dictionary that has the minimum edit distance to a given string

Question

I'm looking for the most efficient way of solving an Levenshtein edit distance problem.

We are given as input:

1. A set of strings S of size n <= 8, with average length m <= 50
2. A target string t of length l <= 50

Our task is to 'align' t with S i.e:

Find the subset s* of S, where concat(s*) has the minimum Levenshtein edit distance (among all the subsets) with t

Some thoughts:

1. For 2 strings of length l1 and l2, we could use the standard dynamic programming algorithm which has O(l1*l2) time complexity
2. Brute forcing this would require us to compute editDistance(t, concat(s')) for each subset s'. This would be approximately O(l.m.n!)
3. This could be optimized a bit by memoizing the results i.e if we are computing editDistance(t, S[1, 2, 3, 4]) we could re-use the computation from S[1, 2, 3])
4. The other option I could think of is to construct a Trie or DAWG (Directed Acyclic Word Graph)

But, I'm not an expert on this, so I might be missing a better solution. How would we do this efficiently?

Thanks in advance!

Answer 1

Try all possible permutation and combination of the set $S$. There are exactly $\sum_{r = 1} ^{8} \mathsf{8Pr}$ such possibilities for $n = 8$. This sums to exactly 109600.

For each subset $s^*$ of $S$, find the edit distance to target string $t$ using the standard DP algorithm. This will take time $l_S \times l$ where $l_S$ is the total length of all the strings in $S$ and $l$ is the length of string $t$. Since $l_S$ could be $400$ and $l$ could be $50$, the total running time is ~ $ 2 \times 10^9$.

You can further optimize the algorithm. In the standard DP algorithm, the algorithm stores the minimum edit distance of all the pairs of suffixes of two given strings $a$ and $b$. In the current problem, the string $t$ is fixed; however $concat(s^*)$ varies depending on subset $s^*$. However, note that some suffixes of $concat(s^*)$ overlaps for different $s^*$. You can show that there at most $S_l \cdot (nC0 + nC1 + nC2 + \dotsc + nCn)$ possible different suffixes of the concatenated string $concat(s^*)$ over all possible subsets $s^{*}$ for $n = 8$. This sums to at most $S_l \cdot 2^{8} \leq 102400$. Thus, the algorithm only needs to find edit distance of $102400 \times 50$ possible pairs of suffixes. Thus, the algorithm can be implemented in ~ $5 \times 10^{6}$ computation steps, which is doable in $1$ sec on regular personal computers.