Algorithms For Dummies

  Ten Algorithmic Problems Yet to Solve 

     403

Reducing Edit Distance Calculation Time

The  edit distance between two strings is the number of operations required to 

transform one string into the other string. The distance calculation revolves 

around the Levenshtein distance operations, which are the removal, insertion, or 

substitution of a character in the string. This particular technique sees use in 

natural language interfaces, DNA sequence quantification, and all sorts of other 

places where you can have two similar strings that require some sort of compari-

son or modification.

A number of solutions for this problem currently exist, all of them quite slow. In 

fact, most of them take exponential time, so the time required to perform a trans-

formation quickly adds up to the point where humans can see pauses in the pro-

cessing of input. The pause isn’t quite so bad when using a word processor that 

performs automatic word checks and changes a misspelled word into the correct 

one. However, when using voice interfaces, the pause can become quite noticeable 

and cause the human operator to make mistakes. The current goal is to allow edit 

distance calculation in subquadratic time: O(n

2−ϵ

).