<s> def levenshtein_distance ( first , second ) : <EOL> """<STR_LIT>""" <EOL> if len ( first ) > len ( second ) : <EOL> first , second = second , first <EOL> if len ( second ) == <NUM_LIT:0> : <EOL> return len ( first ) <EOL> first_length = len ( first ) + <NUM_LIT:1> <EOL> second_length = len ( second ) + <NUM_LIT:1> <EOL> distance_matrix = [ [ <NUM_LIT:0> ] * second_length for x in range ( first_length ) ] <EOL> for i in range ( first_length ) : <EOL> distance_matrix [ i ] [ <NUM_LIT:0> ] = i <EOL> for j in range ( second_length ) : <EOL> distance_matrix [ <NUM_LIT:0> ] [ j ] = j <EOL> for i in xrange ( <NUM_LIT:1> , first_length ) : <EOL> for j in range ( <NUM_LIT:1> , second_length ) : <EOL> deletion = distance_matrix [ i - <NUM_LIT:1> ] [ j ] + <NUM_LIT:1> <EOL> insertion = distance_matrix [ i ] [ j - <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> substitution = distance_matrix [ i - <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] <EOL> if first [ i - <NUM_LIT:1> ] != second [ j - <NUM_LIT:1> ] : <EOL> substitution += <NUM_LIT:1> <EOL> distance_matrix [ i ] [ j ] = min ( insertion , deletion , substitution ) <EOL> return distance_matrix [ first_length - <NUM_LIT:1> ] [ second_length - <NUM_LIT:1> ] <EOL> def percent_diff ( a , b ) : <EOL> try : <EOL> return <NUM_LIT:100> * levenshtein_distance ( a , b ) / float ( max ( len ( a ) , len ( b ) ) ) <EOL> except ZeroDivisionError : <EOL> if len ( a ) == len ( b ) : return <NUM_LIT:0> <EOL> else : return <NUM_LIT:100> </s>
