levenstein.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def lev(s1, s2, l1 = None, l2 = None):
  if l1 == None:
    l1 = len(s1)

  if l2 == None:
    l2 = len(s2)

  if l1 == 0:
    return l2
  elif l2 == 0:
    return l1

  if (s1[l1 - 1] == s2[l2 - 1]):
    cost = 0
  else:
    cost = 1

  return min([
    lev(s1, s2, l1 - 1, l2) + 1, 
    lev(s1, s2, l1, l2 - 1) + 1,
    lev(s1, s2, l1 - 1, l2 - 1) + cost
  ])

print("lev(winter, linter) = %d" % lev('winter', 'linter'))
print("lev(winter, splinter) = %d" % lev('winter', 'splinter'))
print("lev(winter, python) = %d" % lev('winter', 'python'))

dictionary = { 'winter': 'zima', 'spring': 'wiosna', 'summer': 'lato', 'autumn': 'jesień', 'Poland': 'Polska' }
search_for = 'wintr'
similars = { k: dictionary[k] for k in filter(lambda x: lev(x, search_for) <= 3, dictionary.keys()) }

print("words similar to `{0}`: {1}".format(search_for, similars))