Python implementation of the Levenshtein distance finding algo

100words.txt

unpieced
superobedient
nonsacrificing
spikedace
outdare
superirritability
trainman
prevocalically
phonetician
paradrop
cicatrix
fossorial
nonrecalcitrancy
tzarist
pyromantic
redoubtably
lurker
unextinguished
autopolyploid
nut
textbook
fallowness
phrensy
tartary
trapunto
catheterize
apostille
contiguously
phosphorylase
kinetography
unpublishable
carpetbag
tattiness
gaminess
outpracticed
prud
patchouly
metamathematical
unreportable
photosynthetically
parnellism
birdlimed
submanager
subedit
inlit
sitting
extemporaneity
semiangle
chuffily
hemeralopia
nonretardative
curler
connivant
mannerism
nutation
scrooge
bitters
selenic
washiness
polycarpy
erectile
unsmashed
tautomerizing
somatotonic
guest
jansenism
preputial
mani
interparenthetic
yohoing
seraph
acuminated
kitkat
citizenship
lenis
mujtahid
casino
dendriform
molluscous
foreword
kittens
pottage
yeysk
galatians
holophytic
dollish
kitties
lehi
subzero
undilated
tristfully
portlier
menacingly
outhammer
ashlaring
unfriended
skittles
alvera
bailey
kitten

search.py

import time
import sys

def lev( s, t ):
	len_s, len_t = len( s ), len( t )

	if s == t: return 0;
	if len_s == 0: return len_t
	if len_t == 0: return len_s

	v0, v1 = [], []

	for i in range( len_t + 1 ):
		v0.append( 0 )
		v1.append( 0 )

	for i in range( len_s ):
		v1[0] = i + 1

		for j in range( len_t ):
			cost = 0 if s[i] == t[j] else 1
			v1[j+1] = min( v1[j] + 1, v0[j + 1] + 1, v0[j] + cost )

		for j in range( len( v0 ) ):
			v0[j] = v1[j]

	return v1[len_t]

def search( searchterm ):
	print "Searching for term \"" + searchterm + "\" in a list of " + str( len( dictionary ) ) + " words."
	results = []
	for word in dictionary:
		results.append( [ lev( searchterm, word ), word ] )
	return sorted( results )

def prettyresults( results ):
	for result in results[0:11]:
		print result[1] + ": " + str( result[0] )

dictionary = []

with open('100words.txt') as f:
    for line in f:
        dictionary.append( line.rstrip('\n') )

start_time = time.clock()

searchterm = "kitten"

if len(sys.argv) > 1:
	searchterm = sys.argv[1]

prettyresults( search( searchterm ) )

print "Search completed in", time.clock() - start_time, "seconds"