How to implement Minimum Edit Distance in Python

This Python tutorial helps you to understand what is minimum edit distance and how Python implements this algorithm. First, we will learn what is the minimum edit distance.

Definition :

Minimum Edit Distance gives you to the minimum number of operations required to change one string into another string. The operations involved are:-

• Insert
• Update
• Delete

All the operations involve the same cost.

Example:-

Let’s say,

Input:

String 1 = ‘Cat’

String 2 = ‘Car’

Output: 1

The minimum number of operations required to change string 1 to string 2 is only one. That means to change the string ‘Cat’ into string ‘Car’ is to only update the letter ‘t’ to ‘r’.

  Implementation of Minimum Edit Distance in Python

Source Code :

def edit_distance(str1, str2, a, b):
    string_matrix = [[0 for i in range(b+1)] for i in range(a+1)]

    for i in range(a+1):
        for j in range(b+1):

            if i == 0:
                string_matrix[i][j] = j   # If first string is empty, insert all characters of second string into first.

            elif j == 0:
                string_matrix[i][j] = i   # If second string is empty, remove all characters of first string.

            elif str1[i-1] == str2[j-1]:
                string_matrix[i][j] = string_matrix[i-1][j-1]  # If last characters of two strings are same, nothing much to do. Ignore the last two characters and get the count of remaining strings.

            else:
                string_matrix[i][j] = 1 + min(string_matrix[i][j-1],      # insert operation
                                       string_matrix[i-1][j],      # remove operation
                                       string_matrix[i-1][j-1])    # replace operation

    return string_matrix[a][b]


if __name__ == '__main__':
    str1 = 'Cats'
    str2 = 'Rats'

    print('No. of Operations required :',edit_distance(str1, str2, len(str1), len(str2)))
    

    str3 = 'Saturday'
    str4 = 'Sunday'
    print('No. of Operations required :',edit_distance(str3, str4, len(str3), len(str4)))

Output :

Case-1 :-

Input:

str1 = 'Cats'

str2 = 'Rats'

No. of Operations required : 1

Case-2 :-

Input:

str1 = 'Saturday'

str2 = 'Sunday'

No. of Operations required : 3

In Case-1, str1 =’Cats’ and str2 = ‘Rats’.  To change ‘Cats’ into ‘Rats’, only one update operation is required. That means letter ‘C’ is replaced by letter ‘R’.

In Case-2 , str3 =’Saturday’ and str4=’Sunday’. To change ‘Saturday’ to ‘Sunday’, three operations are required. That means letters ‘a’ and ‘t’ are deleted and ‘n’ is inserted.

 

You can also read,

• Depth First Search algorithm in Python
• Breadth First Search algorithm in Python