<s> '''<STR_LIT>''' <EOL> from string import digits , lowercase <EOL> from sys import maxint <EOL> DIGITS = set ( digits ) <EOL> LOWERCASE = set ( lowercase ) <EOL> TSURUOKA_2004_INS_CHEAP = set ( ( '<STR_LIT:U+0020>' , '<STR_LIT:->' , ) ) <EOL> TSURUOKA_2004_DEL_CHEAP = TSURUOKA_2004_INS_CHEAP <EOL> TSURUOKA_2004_REPL_CHEAP = set ( [ ( a , b ) for a in DIGITS for b in DIGITS ] + <EOL> [ ( a , a . upper ( ) ) for a in LOWERCASE ] + <EOL> [ ( a . upper ( ) , a ) for a in LOWERCASE ] + <EOL> [ ( '<STR_LIT:U+0020>' , '<STR_LIT:->' ) , ( '<STR_LIT:->' , '<STR_LIT:_>' ) ] ) <EOL> NONNUM_T2004_REPL_CHEAP = set ( [ ( a , a . upper ( ) ) for a in LOWERCASE ] + <EOL> [ ( a . upper ( ) , a ) for a in LOWERCASE ] + <EOL> [ ( '<STR_LIT:U+0020>' , '<STR_LIT:->' ) , ( '<STR_LIT:->' , '<STR_LIT:_>' ) ] ) <EOL> TSURUOKA_INS = dict ( [ ( c , <NUM_LIT:10> ) for c in TSURUOKA_2004_INS_CHEAP ] ) <EOL> TSURUOKA_DEL = dict ( [ ( c , <NUM_LIT:10> ) for c in TSURUOKA_2004_DEL_CHEAP ] ) <EOL> TSURUOKA_REPL = dict ( [ ( c , <NUM_LIT:10> ) for c in NONNUM_T2004_REPL_CHEAP ] ) <EOL> def tsuruoka ( a , b ) : <EOL> if len ( a ) == <NUM_LIT:0> or len ( b ) == <NUM_LIT:0> : <EOL> return <NUM_LIT:100> * max ( len ( a ) , len ( b ) ) <EOL> prev_min_col = [ <NUM_LIT:0> ] <EOL> for b_c in b : <EOL> prev_min_col . append ( prev_min_col [ - <NUM_LIT:1> ] + TSURUOKA_INS . get ( b_c , <NUM_LIT:100> ) ) <EOL> curr_min_col = prev_min_col <EOL> for a_c in a : <EOL> curr_min_col = [ prev_min_col [ <NUM_LIT:0> ] + TSURUOKA_DEL . get ( a_c , <NUM_LIT:100> ) ] <EOL> for b_i , b_c in enumerate ( b ) : <EOL> if b_c == a_c : <EOL> curr_min_col . append ( prev_min_col [ b_i ] ) <EOL> else : <EOL> curr_min_col . append ( min ( <EOL> prev_min_col [ b_i + <NUM_LIT:1> ] + TSURUOKA_DEL . get ( a_c , <NUM_LIT:100> ) , <EOL> curr_min_col [ - <NUM_LIT:1> ] + TSURUOKA_INS . get ( b_c , <NUM_LIT:100> ) , <EOL> prev_min_col [ b_i ] + TSURUOKA_REPL . get ( ( a_c , b_c ) , <NUM_LIT:50> ) <EOL> ) ) <EOL> prev_min_col = curr_min_col <EOL> return curr_min_col [ - <NUM_LIT:1> ] <EOL> def tsuruoka_local ( a , b , edge_insert_cost = <NUM_LIT:1> , max_cost = maxint ) : <EOL> if len ( a ) == <NUM_LIT:0> : <EOL> return len ( b ) * edge_insert_cost <EOL> if len ( b ) == <NUM_LIT:0> : <EOL> return <NUM_LIT:100> * len ( b ) <EOL> if a in b : <EOL> cost = ( len ( b ) - len ( a ) ) * edge_insert_cost <EOL> return cost if cost < max_cost else max_cost <EOL> prev_min_col = [ <NUM_LIT:0> ] <EOL> for b_c in b : <EOL> prev_min_col . append ( prev_min_col [ - <NUM_LIT:1> ] + edge_insert_cost ) <EOL> curr_min_col = prev_min_col <EOL> for a_c in a : <EOL> curr_min_col = [ prev_min_col [ <NUM_LIT:0> ] + TSURUOKA_DEL . get ( a_c , <NUM_LIT:100> ) ] <EOL> for b_i , b_c in enumerate ( b ) : <EOL> if b_c == a_c : <EOL> curr_min_col . append ( prev_min_col [ b_i ] ) <EOL> else : <EOL> curr_min_col . append ( min ( <EOL> prev_min_col [ b_i + <NUM_LIT:1> ] + TSURUOKA_DEL . get ( a_c , <NUM_LIT:100> ) , <EOL> curr_min_col [ - <NUM_LIT:1> ] + TSURUOKA_INS . get ( b_c , <NUM_LIT:100> ) , <EOL> prev_min_col [ b_i ] + TSURUOKA_REPL . get ( ( a_c , b_c ) , <NUM_LIT:50> ) <EOL> ) ) <EOL> if min ( curr_min_col ) >= max_cost : <EOL> return max_cost <EOL> prev_min_col = curr_min_col <EOL> min_cost = curr_min_col [ - <NUM_LIT:1> ] <EOL> for i in range ( len ( curr_min_col ) ) : <EOL> cost = curr_min_col [ i ] + edge_insert_cost * ( len ( curr_min_col ) - i - <NUM_LIT:1> ) <EOL> min_cost = min ( min_cost , cost ) <EOL> if min_cost < max_cost : <EOL> return min_cost <EOL> else : <EOL> return max_cost <EOL> def tsuruoka_norm ( a , b ) : <EOL> return <NUM_LIT:1> - ( tsuruoka ( a , b ) / ( max ( len ( a ) , len ( b ) ) * <NUM_LIT> ) ) <EOL> def levenshtein ( a , b ) : <EOL> if len ( a ) == <NUM_LIT:0> or len ( b ) == <NUM_LIT:0> : <EOL> return max ( len ( a ) , len ( b ) ) <EOL> prev_min_col = [ <NUM_LIT:0> ] <EOL> for b_c in b : <EOL> prev_min_col . append ( prev_min_col [ - <NUM_LIT:1> ] + <NUM_LIT:1> ) <EOL> curr_min_col = prev_min_col <EOL> for a_c in a : <EOL> curr_min_col = [ prev_min_col [ <NUM_LIT:0> ] + <NUM_LIT:1> ] <EOL> for b_i , b_c in enumerate ( b ) : <EOL> if b_c == a_c : <EOL> curr_min_col . append ( prev_min_col [ b_i ] ) <EOL> else : <EOL> curr_min_col . append ( min ( <EOL> prev_min_col [ b_i + <NUM_LIT:1> ] + <NUM_LIT:1> , <EOL> curr_min_col [ - <NUM_LIT:1> ] + <NUM_LIT:1> , <EOL> prev_min_col [ b_i ] + <NUM_LIT:1> <EOL> ) ) <EOL> prev_min_col = curr_min_col <EOL> return curr_min_col [ - <NUM_LIT:1> ] <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> for a , b in ( ( '<STR_LIT>' , '<STR_LIT>' ) , ( '<STR_LIT>' , '<STR_LIT>' ) , ( '<STR_LIT>' , '<STR_LIT>' ) , ( '<STR_LIT>' , '<STR_LIT:bar>' ) , ( '<STR_LIT>' , '<STR_LIT>' ) , ( '<STR_LIT>' , '<STR_LIT>' ) , ( '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> print '<STR_LIT>' , a , b , levenshtein ( a , b ) <EOL> print '<STR_LIT>' , a , b , tsuruoka ( a , b ) <EOL> print '<STR_LIT>' , a , b , tsuruoka_local ( a , b ) <EOL> print '<STR_LIT>' , a , b , tsuruoka_norm ( a , b ) </s>
