<s> """<STR_LIT>""" <EOL> from whoosh . compat import xrange <EOL> def levenshtein ( seq1 , seq2 , limit = None ) : <EOL> """<STR_LIT>""" <EOL> oneago = None <EOL> thisrow = range ( <NUM_LIT:1> , len ( seq2 ) + <NUM_LIT:1> ) + [ <NUM_LIT:0> ] <EOL> for x in xrange ( len ( seq1 ) ) : <EOL> oneago , thisrow = thisrow , [ <NUM_LIT:0> ] * len ( seq2 ) + [ x + <NUM_LIT:1> ] <EOL> for y in xrange ( len ( seq2 ) ) : <EOL> delcost = oneago [ y ] + <NUM_LIT:1> <EOL> addcost = thisrow [ y - <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> subcost = oneago [ y - <NUM_LIT:1> ] + ( seq1 [ x ] != seq2 [ y ] ) <EOL> thisrow [ y ] = min ( delcost , addcost , subcost ) <EOL> if limit and x > limit and min ( thisrow ) > limit : <EOL> return limit + <NUM_LIT:1> <EOL> return thisrow [ len ( seq2 ) - <NUM_LIT:1> ] <EOL> def damerau_levenshtein ( seq1 , seq2 , limit = None ) : <EOL> """<STR_LIT>""" <EOL> oneago = None <EOL> thisrow = list ( range ( <NUM_LIT:1> , len ( seq2 ) + <NUM_LIT:1> ) ) + [ <NUM_LIT:0> ] <EOL> for x in xrange ( len ( seq1 ) ) : <EOL> twoago , oneago , thisrow = oneago , thisrow , [ <NUM_LIT:0> ] * len ( seq2 ) + [ x + <NUM_LIT:1> ] <EOL> for y in xrange ( len ( seq2 ) ) : <EOL> delcost = oneago [ y ] + <NUM_LIT:1> <EOL> addcost = thisrow [ y - <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> subcost = oneago [ y - <NUM_LIT:1> ] + ( seq1 [ x ] != seq2 [ y ] ) <EOL> thisrow [ y ] = min ( delcost , addcost , subcost ) <EOL> if ( x > <NUM_LIT:0> and y > <NUM_LIT:0> and seq1 [ x ] == seq2 [ y - <NUM_LIT:1> ] <EOL> and seq1 [ x - <NUM_LIT:1> ] == seq2 [ y ] and seq1 [ x ] != seq2 [ y ] ) : <EOL> thisrow [ y ] = min ( thisrow [ y ] , twoago [ y - <NUM_LIT:2> ] + <NUM_LIT:1> ) <EOL> if limit and x > limit and min ( thisrow ) > limit : <EOL> return limit + <NUM_LIT:1> <EOL> return thisrow [ len ( seq2 ) - <NUM_LIT:1> ] <EOL> def relative ( a , b ) : <EOL> """<STR_LIT>""" <EOL> d = distance ( a , b ) <EOL> longer = float ( max ( ( len ( a ) , len ( b ) ) ) ) <EOL> shorter = float ( min ( ( len ( a ) , len ( b ) ) ) ) <EOL> r = ( ( longer - d ) / longer ) * ( shorter / longer ) <EOL> return r <EOL> distance = damerau_levenshtein </s>
