5
$\begingroup$

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all substrings of the longer string of length $m$?

Can it in fact be done in $O(nm)$ time?

$\endgroup$
  • $\begingroup$ What do you want as the output? Do you want $n-m+1$ numbers, namely the value of $D(S,T[i\ldots i+m+1])$ for each $i=0,\dots,n-m$ (where $S$ is the shorter string and $T$ is the longer string, and $D(\cdot,\cdot)$ is the edit-distance function)? Or, do you want a single number, which is the smallest of those numbers? $\endgroup$ – D.W. Jul 1 '13 at 4:52
  • $\begingroup$ @D.W. I would like all $n-m+1$ numbers as you say. $\endgroup$ – felix Jul 1 '13 at 6:16
1
$\begingroup$

If you want the minimum number of single-character changes (insert, delete, substitute) that transforms the shorter string $S$ into some length-$m$ substring of $T$, then this can be done in $O(nm)$ time.

The standard algorithm for computing the edit distance between two strings runs in $O(nm)$ time. It uses dynamic programming to build up a matrix $d[\cdot,\cdot]$ where $d[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to $T[0 \ldots j]$.

You can use a simple variation of this algorithm to build up a matrix $d'[\cdot,\cdot]$ where $d'[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to some suffix of $T[0 \ldots j]$ (i.e., to some string $T[k \ldots j]$ for some $k\le j$). The running time remains $O(nm)$. This is sometimes known under the name fuzzy string search.

This gives you a single distance, which represents the smallest number of single-character changes needed to transform $S$ into a length-$m$ substring of $T$. (If you wanted to get all $n-m+1$ edit distances from $S$ to each length-$m$ substring of $T$, I don't know whether that can be done in $O(nm)$ time.)

$\endgroup$
  • $\begingroup$ Thank you. I am unfortunately looking for all $n-m+1$ edit distances from $S$ to each length-$m$ substring of $T$. $\endgroup$ – felix Jul 1 '13 at 6:17
  • $\begingroup$ This is also called local alignment, solved by the Smith–Waterman algorithm (which works as described here). $\endgroup$ – Raphael Sep 2 '13 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.