Implement the Levenshtein-distance algorithm.

levenshtein.py

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

'''Implement the Levenshtein-distance Algorithm'''

def levenshtein(source, dest):
    '''Return the levenshteiin distance between source and dest'''
	row_len = len(source) + 1
	col_len = len(dest) + 1

	if row_len==1 or col_len==1:
		return max(row_len, col_len)

	matrix = [[col+row for col in range(col_len)] for row in range(row_len)]

	for row in xrange(1, row_len):
		for col in xrange(1, col_len):
			cost = 0 if source[row - 1] == dest[col - 1] else 1

			deletion = matrix[row-1][col] + 1
			insertion = matrix[row][col-1] + 1
			substitution = matrix[row-1][col-1] + cost

			matrix[row][col] = min(deletion, insertion, substitution)

	return matrix[row_len-1][col_len-1]

if __name__ == '__main__':

	token = ['add', 'bisect', 'branch', 'checkout', 'clone', 'commit', 
		'diff', 'fetch', 'grep', 'init', 'log', 'merge', 'mv', 'pull', 
		'push', 'rebase', 'reset', 'rm', 'show', 'status', 'tag']

	key = 'show'
	result = [levenshtein(key, des) for des in token]
	print min(*result)

	for des in token:
		r = levenshtein(key, des)
		if r < 3:
			print des, r