Algorithms For Dummies

  Relying on Dynamic Programming 

     317

Approximating string search

Determining when one word is similar to another isn’t always simple. Words may 

differ slightly because of misspelling or different ways of writing the word itself, 

thus rendering any exact match impossible. This isn’t just a problem that raises 

interesting issues during a spell check, though. For example, putting similar text 

strings together (such as names, addresses, or code identifiers) that refer to the 

same person may help create a one-customer view of a firm’s customer base or 

help a national security agency locate a dangerous criminal.

Approximating string searches has many applications in machine translation, 

speech recognition, spell checking and text processing, computational biology, 

and information retrieval. Thinking about the manner in which sources input data 

into databases, you know there are many mismatches between data fields that a 

smart algorithm must solve. Matching a similar, but not precisely equal, series of 

letters is an ability that finds uses in fields such as genetics when comparing DNA 

sequences (expressed by letters representing nucleotides G,A,T, and C ) to deter-

mine whether two sequences are similar and how they resemble each other.

Vladimir Levenshtein, a Russian scientist expert in information theory (see 

http://ethw.org/Vladimir_I._Levenshtein

 for details), devised a simple mea-

sure (named after him) in 1965 that computes the grade of similarity between two 

strings by counting how many transformations it takes to change the first string 

into the second. The Levenshtein distance (also known as edit distance) counts 

how many changes are necessary in a word: