Edit Distance in Python

by

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(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

And a couple of more implementations are here.

More Related Contents:

  1. What happens when start value < end value with range() cmd in Python?
  2. Check if all elements in a list are identical
  3. Permutations between two lists of unequal length
  4. Pythonic way to check if a list is sorted or not
  5. Detecting consecutive integers in a list [duplicate]
  6. Evenly distributing n points on a sphere
  7. Efficient way to apply multiple filters to pandas DataFrame or Series
  8. What is the best way to get all the divisors of a number?
  9. Sorting text file by using Python
  10. Maximum sum sublist?
  11. How to implement a binary tree?
  12. In Python, what is the fastest algorithm for removing duplicates from a list so that all elements are unique *while preserving order*? [duplicate]
  13. Best way to determine if a sequence is in another sequence?
  14. Mapping a range of values to another
  15. How to test if one string is a subsequence of another? [duplicate]
  16. Find elements of array one nearest to elements of array two
  17. Complexity of list.index(x) in Python
  18. Fast prime factorization module
  19. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  20. Python: find closest string (from a list) to another string
  21. Split a list of numbers into n chunks such that the chunks have (close to) equal sums and keep the original order
  22. In Python, how do you find the index of the first value greater than a threshold in a sorted list?
  23. String similarity metrics in Python [duplicate]
  24. What is the time complexity of heapq.nlargest?
  25. creating a spiral array in python?
  26. Understanding change-making algorithm
  27. How can I fit a Bézier curve to a set of data?
  28. Mergesort with Python
  29. Find non-common elements in lists
  30. Algorithm for solving Sudoku

Leave a Comment