#! /usr/bin/python
import sys
import cgi
def normalise( str ):
return str.replace( " ", "" ).lower()
def cost( i, j ):
return a[i] != b[j]
memo = {}
def distance( i, j ):
if ((i < 0) or (j < 0)):
return 0
if (memo.has_key( (i, j) )):
return memo[(i, j)]
up = distance( (i - 1), j ) + 1
left = distance( i, (j - 1) ) + 1
diag = distance( (i - 1), (j - 1) ) + cost( i, j )
d = min( (up, left, diag) )
memo[(i, j)] = d
return d
def totalDistance():
return distance( (len( a ) - 1), (len( b ) - 1) )
form = cgi.FieldStorage()
a = form.getvalue( "a" )
b = form.getvalue( "b" )
n = int( form.getvalue( "n", "0" ) )
if (n):
a = normalise( a )
b = normalise( b )
ed = totalDistance()
s = 1.0 - (float( ed ) / float( max( (len( a ), len( b )) ) ))
out = sys.stdout
out.write( "Content-type: text/html\n" )
out.write( "\n" )
out.write( """
Edit Distance
Edit Distance
""" )
out.write( ("String A: " + str( a ) + "
\n") )
out.write( ("String B: " + str( b ) + "
\n") )
out.write( ("Edit Distance: " + str( ed ) + "
\n") )
out.write( ("Similarity: " + str( s ) + "
\n") )
out.write( """
""" )
out.flush()