Edit Distance in Python


Python Problem Overview

I'm programming a spellcheck program in Python. I have a list of valid words (the dictionary) and I need to output a list of words from this dictionary that have an edit distance of 2 from a given invalid word.

I know I need to start by generating a list with an edit distance of one from the invalid word(and then run that again on all the generated words). I have three methods, inserts(...), deletions(...) and changes(...) that should output a list of words with an edit distance of 1, where inserts outputs all valid words with one more letter than the given word, deletions outputs all valid words with one less letter, and changes outputs all valid words with one different letter.

I've checked a bunch of places but I can't seem to find an algorithm that describes this process. All the ideas I've come up with involve looping through the dictionary list multiple times, which would be extremely time consuming. If anyone could offer some insight, I'd be extremely grateful.

Python Solutions

Solution 1 - Python

The thing you are looking at is called an edit distance and here is a nice explanation on wiki. There are a lot of ways how to define a distance between the two words and the one that you want is called Levenshtein distance and here is a DP (dynamic programming) implementation in python.

def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

And a couple of more implementations are here.

Solution 2 - Python

difflib in the standard library has various utilities for sequence matching, including the get_close_matches method that you could use. It uses an algorithm adapted from Ratcliff and Obershelp.

From the docs

>>> from difflib import get_close_matches
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']

Solution 3 - Python

Here is my version for Levenshtein distance

def edit_distance(s1, s2):

tbl = {}
for i in range(m): tbl[i,0]=i
for j in range(n): tbl[0,j]=j
for i in range(1, m):
	for j in range(1, n):
		cost = 0 if s1[i-1] == s2[j-1] else 1
		tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost)

return tbl[i,j]

print(edit_distance("Helloworld", "HalloWorld"))

Solution 4 - Python

#this calculates edit distance not levenstein edit distance




x =[[0]*(len_2+1) for _ in range(len_1+1)]#the matrix whose last element ->edit distance

for i in range(0,len_1+1): #initialization of base case values
for j in range(0,len_2+1):

for i in range (1,len_1+1):
    for j in range(1,len_2+1):

        if word1[i-1]==word2[j-1]:
            x[i][j] = x[i-1][j-1] 

        else :
            x[i][j]= min(x[i][j-1],x[i-1][j],x[i-1][j-1])+1

print x[i][j]

Solution 5 - Python

I would recommend not creating this kind of code on your own. There are libraries for that.

For instance the Levenshtein library.

In [2]: Levenshtein.distance("foo", "foobar")
Out[2]: 3

In [3]: Levenshtein.distance("barfoo", "foobar")
Out[3]: 6

In [4]: Levenshtein.distance("Buroucrazy", "Bureaucracy")
Out[4]: 3

In [5]: Levenshtein.distance("Misisipi", "Mississippi")
Out[5]: 3

In [6]: Levenshtein.distance("Misisipi", "Misty Mountains")
Out[6]: 11

In [7]: Levenshtein.distance("Buroucrazy", "Born Crazy")
Out[7]: 4

Solution 6 - Python

Using the SequenceMatcher from Python built-in difflib is another way of doing it, but (as correctly pointed out in the comments), the result does not match the definition of an edit distance exactly. Bonus: it supports ignoring "junk" parts (e.g. spaces or punctuation).

from difflib import SequenceMatcher

a = 'kitten'
b = 'sitting'

required_edits = [    code    for code in (        SequenceMatcher(a=a, b=b, autojunk=False)        .get_opcodes()    )    if code[0] != 'equal'
# [#    # (tag, i1, i2, j1, j2)#    ('replace', 0, 1, 0, 1), # replace a[0:1]="k" with b[0:1]="s"
#    ('replace', 4, 5, 4, 5), # replace a[4:5]="e" with b[4:5]="i"
#    ('insert', 6, 6, 6, 7),  # insert b[6:7]="g" after a[6:6]="n"
# ]

# the edit distance:
len(required_edits)  # == 3

Solution 7 - Python

Similar to Santoshi's solution above but I made three changes:

  1. One line initialization instead of five
  2. No need to define cost alone (just use int(boolean) 0 or 1)
  3. Instead of double for loop use product, (this last one is only cosmetic, double loop seems unavoidable)
from itertools import product

def edit_distance(s1,s2):      
   d={ **{(i,0):i for i in range(len(s1)+1)},**{(0,j):j for j in range(len(s2)+1)}}
   for i, j in product(range(1,len(s1)+1), range(1,len(s2)+1)): 
       d[i,j]=min((s1[i-1]!=s2[j-1]) + d[i-1,j-1], d[i-1,j]+1, d[i,j-1]+1)
   return d[i,j]

Solution 8 - Python

Instead of going with Levenshtein distance algo use BK tree or TRIE, as these algorithms have less complexity then edit distance. A good browse over these topic will give a detailed description.

This link will help you more about spell checking.

Solution 9 - Python

You need Minimum Edit Distance for this task.

Following is my version of MED a.k.a Levenshtein Distance.

def MED_character(str1,str2):

    #output the length of other string in case the length of any of the string is zero
    if len1==0:
        return len2
    if len2==0:
        return len1

    accumulator = [[0 for x in range(len2)] for y in range(len1)] #initializing a zero matrix

    # initializing the base cases
    for i in range(0,len1):
        accumulator[i][0] = i;
    for i in range(0,len2):
        accumulator[0][i] = i;

    # we take the accumulator and iterate through it row by row. 
    for i in range(1,len1):
        for j in range(1,len2):
            if char1!=char2:
                cost1=2 #cost for substitution
            accumulator[i][j]=min(accumulator[i-1][j]+1, accumulator[i][j-1]+1, accumulator[i-1][j-1] + cost1 )

    return cost

Solution 10 - Python

Fine tuned codes based on the version from @Santosh and should address the issue brought up by @Artur Krajewski; The biggest difference is replacing an effective 2d matrix

def edit_distance(s1, s2):
# add a blank character for both strings
# launch a matrix
    tbl = [[0] * n for i in range(m)] 
    for i in range(m): tbl[i][0]=i
    for j in range(n): tbl[0][j]=j

    for i in range(1, m):
        for j in range(1, n):
#if strings have same letters, set operation cost as 0 otherwise 1
            cost = 0 if s1[i-1] == s2[j-1] else 1
#find min practice
            tbl[i][j] = min(tbl[i][j-1]+1, tbl[i-1][j]+1, tbl[i-1][j-1]+cost)
    return tbl

edit_distance("birthday", "Birthdayyy")


All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionMelView Question on Stackoverflow
Solution 1 - PythonSalvador DaliView Answer on Stackoverflow
Solution 2 - PythonryanjdillonView Answer on Stackoverflow
Solution 3 - PythonSantoshView Answer on Stackoverflow
Solution 4 - Pythonishaan aroraView Answer on Stackoverflow
Solution 5 - PythonfirelynxView Answer on Stackoverflow
Solution 6 - PythonkrassowskiView Answer on Stackoverflow
Solution 7 - PythonJ.MichaelView Answer on Stackoverflow
Solution 8 - Pythonjt26View Answer on Stackoverflow
Solution 9 - PythonInaam IlahiView Answer on Stackoverflow
Solution 10 - PythonZac S.YView Answer on Stackoverflow