Home > Algorithms, Computer Programming, Computer Science > Difference between two strings – Levenshtein Algorithm

Difference between two strings – Levenshtein Algorithm

So now after a long time, I am going to write about an algorithm which I recently read, and found it very useful.

This algorithm is about, how different two strings are, and how many minimum operations are required to convert smaller string in length to larger (if their lengths are different). If the two string are of equal length then the number of charcaters that differ in two strings is the difference of strings. For example, in ‘computer’ and ‘computes’ the difference is 1 and in ‘test’ and ‘goat’ the difference is 3. Such distance is called as Hamming distance or edit distance simply put.

However if the strings are different in length then we use Levenshtein Algorithm or edit distance. Which works as follows.

For the two strings s1(cat) and s2(cots) of lengths m(3) and n(4), make an array of n*m and fill the each cell in 0th row with it’s corresponding column number and each cell in 0th column with it’s corresponding row number so our array ‘D’ will look like,

0 1 2 3

1

2

3

4

After this we compute a value in ‘temp’ which is 0 if s1[i] = s1[j] and 1 otherwise. And then find the minimum of D[i-1][j] + 1, D[i][j-1] +1 and D[i-1][j-1] + cost and assign it to D[i][j], where ‘i’ and ‘j’ are indeces while we compute. When we fill this array the last value in D[n][m] will give you the minimum number of moves required to convert str1(smaller) into str2(larger).

Here D[i-1][j] + 1, tell us if it is selected that we have to insert value in str1, if we select D[i][j-1] + 1 then we have to delete from str2 and if D[i-1][j-1] + cost is selected then we have to substitue in str1.

This is an interesting algorithm to try and then code, and is useful to find closest matches for a string and then can be used in many applications.

Advertisements
  1. dong
    February 23, 2007 at 2:32 pm

    most basic (101) dynamic programming algorithm ever

  2. Idetrorce
    December 15, 2007 at 12:08 pm

    very interesting, but I don’t agree with you
    Idetrorce

  3. May 20, 2009 at 2:29 pm

    U’ve got good pics, the site could use a tiny bit of work (no offense) its still awesome

  1. January 19, 2007 at 3:57 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: