<s> import unicodedata <EOL> from collections import defaultdict <EOL> from . compat import _range , _zip_longest , _no_bytes_err <EOL> from . porter import Stemmer <EOL> def _normalize ( s ) : <EOL> return unicodedata . normalize ( '<STR_LIT>' , s ) <EOL> def levenshtein_distance ( s1 , s2 ) : <EOL> if isinstance ( s1 , bytes ) or isinstance ( s2 , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> if s1 == s2 : <EOL> return <NUM_LIT:0> <EOL> rows = len ( s1 ) + <NUM_LIT:1> <EOL> cols = len ( s2 ) + <NUM_LIT:1> <EOL> if not s1 : <EOL> return cols - <NUM_LIT:1> <EOL> if not s2 : <EOL> return rows - <NUM_LIT:1> <EOL> prev = None <EOL> cur = range ( cols ) <EOL> for r in _range ( <NUM_LIT:1> , rows ) : <EOL> prev , cur = cur , [ r ] + [ <NUM_LIT:0> ] * ( cols - <NUM_LIT:1> ) <EOL> for c in _range ( <NUM_LIT:1> , cols ) : <EOL> deletion = prev [ c ] + <NUM_LIT:1> <EOL> insertion = cur [ c - <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> edit = prev [ c - <NUM_LIT:1> ] + ( <NUM_LIT:0> if s1 [ r - <NUM_LIT:1> ] == s2 [ c - <NUM_LIT:1> ] else <NUM_LIT:1> ) <EOL> cur [ c ] = min ( edit , deletion , insertion ) <EOL> return cur [ - <NUM_LIT:1> ] <EOL> def _jaro_winkler ( ying , yang , long_tolerance , winklerize ) : <EOL> if isinstance ( ying , bytes ) or isinstance ( yang , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> ying_len = len ( ying ) <EOL> yang_len = len ( yang ) <EOL> if not ying_len or not yang_len : <EOL> return <NUM_LIT:0> <EOL> min_len = max ( ying_len , yang_len ) <EOL> search_range = ( min_len // <NUM_LIT:2> ) - <NUM_LIT:1> <EOL> if search_range < <NUM_LIT:0> : <EOL> search_range = <NUM_LIT:0> <EOL> ying_flags = [ False ] * ying_len <EOL> yang_flags = [ False ] * yang_len <EOL> common_chars = <NUM_LIT:0> <EOL> for i , ying_ch in enumerate ( ying ) : <EOL> low = i - search_range if i > search_range else <NUM_LIT:0> <EOL> hi = i + search_range if i + search_range < yang_len else yang_len - <NUM_LIT:1> <EOL> for j in _range ( low , hi + <NUM_LIT:1> ) : <EOL> if not yang_flags [ j ] and yang [ j ] == ying_ch : <EOL> ying_flags [ i ] = yang_flags [ j ] = True <EOL> common_chars += <NUM_LIT:1> <EOL> break <EOL> if not common_chars : <EOL> return <NUM_LIT:0> <EOL> k = trans_count = <NUM_LIT:0> <EOL> for i , ying_f in enumerate ( ying_flags ) : <EOL> if ying_f : <EOL> for j in _range ( k , yang_len ) : <EOL> if yang_flags [ j ] : <EOL> k = j + <NUM_LIT:1> <EOL> break <EOL> if ying [ i ] != yang [ j ] : <EOL> trans_count += <NUM_LIT:1> <EOL> trans_count /= <NUM_LIT:2> <EOL> common_chars = float ( common_chars ) <EOL> weight = ( ( common_chars / ying_len + common_chars / yang_len + <EOL> ( common_chars - trans_count ) / common_chars ) ) / <NUM_LIT:3> <EOL> if winklerize and weight > <NUM_LIT> and ying_len > <NUM_LIT:3> and yang_len > <NUM_LIT:3> : <EOL> j = min ( min_len , <NUM_LIT:4> ) <EOL> i = <NUM_LIT:0> <EOL> while i < j and ying [ i ] == yang [ i ] and ying [ i ] : <EOL> i += <NUM_LIT:1> <EOL> if i : <EOL> weight += i * <NUM_LIT:0.1> * ( <NUM_LIT:1.0> - weight ) <EOL> if ( long_tolerance and min_len > <NUM_LIT:4> and common_chars > i + <NUM_LIT:1> and <EOL> <NUM_LIT:2> * common_chars >= min_len + i ) : <EOL> weight += ( ( <NUM_LIT:1.0> - weight ) * ( float ( common_chars - i - <NUM_LIT:1> ) / float ( ying_len + yang_len - i * <NUM_LIT:2> + <NUM_LIT:2> ) ) ) <EOL> return weight <EOL> def damerau_levenshtein_distance ( s1 , s2 ) : <EOL> if isinstance ( s1 , bytes ) or isinstance ( s2 , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> len1 = len ( s1 ) <EOL> len2 = len ( s2 ) <EOL> infinite = len1 + len2 <EOL> da = defaultdict ( int ) <EOL> score = [ [ <NUM_LIT:0> ] * ( len2 + <NUM_LIT:2> ) for x in _range ( len1 + <NUM_LIT:2> ) ] <EOL> score [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] = infinite <EOL> for i in _range ( <NUM_LIT:0> , len1 + <NUM_LIT:1> ) : <EOL> score [ i + <NUM_LIT:1> ] [ <NUM_LIT:0> ] = infinite <EOL> score [ i + <NUM_LIT:1> ] [ <NUM_LIT:1> ] = i <EOL> for i in _range ( <NUM_LIT:0> , len2 + <NUM_LIT:1> ) : <EOL> score [ <NUM_LIT:0> ] [ i + <NUM_LIT:1> ] = infinite <EOL> score [ <NUM_LIT:1> ] [ i + <NUM_LIT:1> ] = i <EOL> for i in _range ( <NUM_LIT:1> , len1 + <NUM_LIT:1> ) : <EOL> db = <NUM_LIT:0> <EOL> for j in _range ( <NUM_LIT:1> , len2 + <NUM_LIT:1> ) : <EOL> i1 = da [ s2 [ j - <NUM_LIT:1> ] ] <EOL> j1 = db <EOL> cost = <NUM_LIT:1> <EOL> if s1 [ i - <NUM_LIT:1> ] == s2 [ j - <NUM_LIT:1> ] : <EOL> cost = <NUM_LIT:0> <EOL> db = j <EOL> score [ i + <NUM_LIT:1> ] [ j + <NUM_LIT:1> ] = min ( score [ i ] [ j ] + cost , <EOL> score [ i + <NUM_LIT:1> ] [ j ] + <NUM_LIT:1> , <EOL> score [ i ] [ j + <NUM_LIT:1> ] + <NUM_LIT:1> , <EOL> score [ i1 ] [ j1 ] + ( i - i1 - <NUM_LIT:1> ) + <NUM_LIT:1> + ( j - j1 - <NUM_LIT:1> ) ) <EOL> da [ s1 [ i - <NUM_LIT:1> ] ] = i <EOL> return score [ len1 + <NUM_LIT:1> ] [ len2 + <NUM_LIT:1> ] <EOL> def jaro_distance ( s1 , s2 ) : <EOL> return _jaro_winkler ( s1 , s2 , False , False ) <EOL> def jaro_winkler ( s1 , s2 , long_tolerance = False ) : <EOL> return _jaro_winkler ( s1 , s2 , long_tolerance , True ) <EOL> def soundex ( s ) : <EOL> if not s : <EOL> return s <EOL> if isinstance ( s , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> s = _normalize ( s ) <EOL> replacements = ( ( '<STR_LIT>' , '<STR_LIT:1>' ) , <EOL> ( '<STR_LIT>' , '<STR_LIT:2>' ) , <EOL> ( '<STR_LIT>' , '<STR_LIT:3>' ) , <EOL> ( '<STR_LIT:l>' , '<STR_LIT:4>' ) , <EOL> ( '<STR_LIT>' , '<STR_LIT:5>' ) , <EOL> ( '<STR_LIT:r>' , '<STR_LIT>' ) ) <EOL> result = [ s [ <NUM_LIT:0> ] ] <EOL> count = <NUM_LIT:1> <EOL> for lset , sub in replacements : <EOL> if s [ <NUM_LIT:0> ] . lower ( ) in lset : <EOL> last = sub <EOL> break <EOL> else : <EOL> last = None <EOL> for letter in s [ <NUM_LIT:1> : ] : <EOL> for lset , sub in replacements : <EOL> if letter . lower ( ) in lset : <EOL> if sub != last : <EOL> result . append ( sub ) <EOL> count += <NUM_LIT:1> <EOL> last = sub <EOL> break <EOL> else : <EOL> last = None <EOL> if count == <NUM_LIT:4> : <EOL> break <EOL> result += '<STR_LIT:0>' * ( <NUM_LIT:4> - count ) <EOL> return '<STR_LIT>' . join ( result ) <EOL> def hamming_distance ( s1 , s2 ) : <EOL> if isinstance ( s1 , bytes ) or isinstance ( s2 , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> if len ( s2 ) > len ( s1 ) : <EOL> s1 , s2 = s2 , s1 <EOL> distance = len ( s1 ) - len ( s2 ) <EOL> for i , c in enumerate ( s2 ) : <EOL> if c != s1 [ i ] : <EOL> distance += <NUM_LIT:1> <EOL> return distance <EOL> def nysiis ( s ) : <EOL> if isinstance ( s , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> if not s : <EOL> return '<STR_LIT>' <EOL> s = s . upper ( ) <EOL> key = [ ] <EOL> if s . startswith ( '<STR_LIT>' ) : <EOL> s = '<STR_LIT>' + s [ <NUM_LIT:3> : ] <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> s = s [ <NUM_LIT:1> : ] <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> s = '<STR_LIT:C>' + s [ <NUM_LIT:1> : ] <EOL> elif s . startswith ( ( '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> s = '<STR_LIT>' + s [ <NUM_LIT:2> : ] <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> s = '<STR_LIT>' + s [ <NUM_LIT:3> : ] <EOL> if s . endswith ( ( '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> s = s [ : - <NUM_LIT:2> ] + '<STR_LIT:Y>' <EOL> elif s . endswith ( ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> s = s [ : - <NUM_LIT:2> ] + '<STR_LIT:D>' <EOL> key . append ( s [ <NUM_LIT:0> ] ) <EOL> i = <NUM_LIT:1> <EOL> len_s = len ( s ) <EOL> while i < len_s : <EOL> ch = s [ i ] <EOL> if ch == '<STR_LIT:E>' and i + <NUM_LIT:1> < len_s and s [ i + <NUM_LIT:1> ] == '<STR_LIT>' : <EOL> ch = '<STR_LIT>' <EOL> i += <NUM_LIT:1> <EOL> elif ch in '<STR_LIT>' : <EOL> ch = '<STR_LIT:A>' <EOL> elif ch == '<STR_LIT>' : <EOL> ch = '<STR_LIT>' <EOL> elif ch == '<STR_LIT>' : <EOL> ch = '<STR_LIT:S>' <EOL> elif ch == '<STR_LIT:M>' : <EOL> ch = '<STR_LIT:N>' <EOL> elif ch == '<STR_LIT>' : <EOL> if i + <NUM_LIT:1> < len ( s ) and s [ i + <NUM_LIT:1> ] == '<STR_LIT:N>' : <EOL> ch = '<STR_LIT:N>' <EOL> else : <EOL> ch = '<STR_LIT:C>' <EOL> elif ch == '<STR_LIT:S>' and s [ i + <NUM_LIT:1> : i + <NUM_LIT:3> ] == '<STR_LIT>' : <EOL> ch = '<STR_LIT>' <EOL> i += <NUM_LIT:2> <EOL> elif ch == '<STR_LIT:P>' and i + <NUM_LIT:1> < len ( s ) and s [ i + <NUM_LIT:1> ] == '<STR_LIT:H>' : <EOL> ch = '<STR_LIT:F>' <EOL> i += <NUM_LIT:1> <EOL> elif ch == '<STR_LIT:H>' and ( s [ i - <NUM_LIT:1> ] not in '<STR_LIT>' or ( i + <NUM_LIT:1> < len ( s ) and s [ i + <NUM_LIT:1> ] not in '<STR_LIT>' ) ) : <EOL> if s [ i - <NUM_LIT:1> ] in '<STR_LIT>' : <EOL> ch = '<STR_LIT:A>' <EOL> else : <EOL> ch = s [ i - <NUM_LIT:1> ] <EOL> elif ch == '<STR_LIT>' and s [ i - <NUM_LIT:1> ] in '<STR_LIT>' : <EOL> ch = s [ i - <NUM_LIT:1> ] <EOL> if ch [ - <NUM_LIT:1> ] != key [ - <NUM_LIT:1> ] [ - <NUM_LIT:1> ] : <EOL> key . append ( ch ) <EOL> i += <NUM_LIT:1> <EOL> key = '<STR_LIT>' . join ( key ) <EOL> if key . endswith ( '<STR_LIT:S>' ) and key != '<STR_LIT:S>' : <EOL> key = key [ : - <NUM_LIT:1> ] <EOL> if key . endswith ( '<STR_LIT>' ) : <EOL> key = key [ : - <NUM_LIT:2> ] + '<STR_LIT:Y>' <EOL> if key . endswith ( '<STR_LIT:A>' ) and key != '<STR_LIT:A>' : <EOL> key = key [ : - <NUM_LIT:1> ] <EOL> return key <EOL> def match_rating_codex ( s ) : <EOL> if isinstance ( s , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> s = s . upper ( ) <EOL> codex = [ ] <EOL> prev = None <EOL> for i , c in enumerate ( s ) : <EOL> if ( c != '<STR_LIT:U+0020>' and ( i == <NUM_LIT:0> and c in '<STR_LIT>' ) or ( c not in '<STR_LIT>' and c != prev ) ) : <EOL> codex . append ( c ) <EOL> prev = c <EOL> if len ( codex ) > <NUM_LIT:6> : <EOL> return '<STR_LIT>' . join ( codex [ : <NUM_LIT:3> ] + codex [ - <NUM_LIT:3> : ] ) <EOL> else : <EOL> return '<STR_LIT>' . join ( codex ) <EOL> def match_rating_comparison ( s1 , s2 ) : <EOL> codex1 = match_rating_codex ( s1 ) <EOL> codex2 = match_rating_codex ( s2 ) <EOL> len1 = len ( codex1 ) <EOL> len2 = len ( codex2 ) <EOL> res1 = [ ] <EOL> res2 = [ ] <EOL> if abs ( len1 - len2 ) >= <NUM_LIT:3> : <EOL> return None <EOL> lensum = len1 + len2 <EOL> if lensum <= <NUM_LIT:4> : <EOL> min_rating = <NUM_LIT:5> <EOL> elif lensum <= <NUM_LIT:7> : <EOL> min_rating = <NUM_LIT:4> <EOL> elif lensum <= <NUM_LIT:11> : <EOL> min_rating = <NUM_LIT:3> <EOL> else : <EOL> min_rating = <NUM_LIT:2> <EOL> for c1 , c2 in _zip_longest ( codex1 , codex2 ) : <EOL> if c1 != c2 : <EOL> if c1 : <EOL> res1 . append ( c1 ) <EOL> if c2 : <EOL> res2 . append ( c2 ) <EOL> unmatched_count1 = unmatched_count2 = <NUM_LIT:0> <EOL> for c1 , c2 in _zip_longest ( reversed ( res1 ) , reversed ( res2 ) ) : <EOL> if c1 != c2 : <EOL> if c1 : <EOL> unmatched_count1 += <NUM_LIT:1> <EOL> if c2 : <EOL> unmatched_count2 += <NUM_LIT:1> <EOL> return ( <NUM_LIT:6> - max ( unmatched_count1 , unmatched_count2 ) ) >= min_rating <EOL> def metaphone ( s ) : <EOL> if isinstance ( s , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> result = [ ] <EOL> s = _normalize ( s . lower ( ) ) <EOL> if s . startswith ( ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> s = s [ <NUM_LIT:1> : ] <EOL> i = <NUM_LIT:0> <EOL> while i < len ( s ) : <EOL> c = s [ i ] <EOL> next = s [ i + <NUM_LIT:1> ] if i < len ( s ) - <NUM_LIT:1> else '<STR_LIT>' <EOL> nextnext = s [ i + <NUM_LIT:2> ] if i < len ( s ) - <NUM_LIT:2> else '<STR_LIT>' <EOL> if c == next and c != '<STR_LIT:c>' : <EOL> i += <NUM_LIT:1> <EOL> continue <EOL> if c in '<STR_LIT>' : <EOL> if i == <NUM_LIT:0> or s [ i - <NUM_LIT:1> ] == '<STR_LIT:U+0020>' : <EOL> result . append ( c ) <EOL> elif c == '<STR_LIT:b>' : <EOL> if ( not ( i != <NUM_LIT:0> and s [ i - <NUM_LIT:1> ] == '<STR_LIT:m>' ) ) or next : <EOL> result . append ( '<STR_LIT:b>' ) <EOL> elif c == '<STR_LIT:c>' : <EOL> if next == '<STR_LIT:i>' and nextnext == '<STR_LIT:a>' or next == '<STR_LIT:h>' : <EOL> result . append ( '<STR_LIT:x>' ) <EOL> i += <NUM_LIT:1> <EOL> elif next in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:s>' ) <EOL> i += <NUM_LIT:1> <EOL> else : <EOL> result . append ( '<STR_LIT:k>' ) <EOL> elif c == '<STR_LIT:d>' : <EOL> if next == '<STR_LIT:g>' and nextnext in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT>' ) <EOL> i += <NUM_LIT:2> <EOL> else : <EOL> result . append ( '<STR_LIT:t>' ) <EOL> elif c in '<STR_LIT>' : <EOL> result . append ( c ) <EOL> elif c == '<STR_LIT:g>' : <EOL> if next in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT>' ) <EOL> elif next not in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:k>' ) <EOL> elif next == '<STR_LIT:h>' and nextnext and nextnext not in '<STR_LIT>' : <EOL> i += <NUM_LIT:1> <EOL> elif c == '<STR_LIT:h>' : <EOL> if i == <NUM_LIT:0> or next in '<STR_LIT>' or s [ i - <NUM_LIT:1> ] not in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:h>' ) <EOL> elif c == '<STR_LIT:k>' : <EOL> if i == <NUM_LIT:0> or s [ i - <NUM_LIT:1> ] != '<STR_LIT:c>' : <EOL> result . append ( '<STR_LIT:k>' ) <EOL> elif c == '<STR_LIT:p>' : <EOL> if next == '<STR_LIT:h>' : <EOL> result . append ( '<STR_LIT:f>' ) <EOL> i += <NUM_LIT:1> <EOL> else : <EOL> result . append ( '<STR_LIT:p>' ) <EOL> elif c == '<STR_LIT:q>' : <EOL> result . append ( '<STR_LIT:k>' ) <EOL> elif c == '<STR_LIT:s>' : <EOL> if next == '<STR_LIT:h>' : <EOL> result . append ( '<STR_LIT:x>' ) <EOL> i += <NUM_LIT:1> <EOL> elif next == '<STR_LIT:i>' and nextnext in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:x>' ) <EOL> i += <NUM_LIT:2> <EOL> else : <EOL> result . append ( '<STR_LIT:s>' ) <EOL> elif c == '<STR_LIT:t>' : <EOL> if next == '<STR_LIT:i>' and nextnext in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:x>' ) <EOL> elif next == '<STR_LIT:h>' : <EOL> result . append ( '<STR_LIT:0>' ) <EOL> i += <NUM_LIT:1> <EOL> elif next != '<STR_LIT:c>' or nextnext != '<STR_LIT:h>' : <EOL> result . append ( '<STR_LIT:t>' ) <EOL> elif c == '<STR_LIT:v>' : <EOL> result . append ( '<STR_LIT:f>' ) <EOL> elif c == '<STR_LIT:w>' : <EOL> if i == <NUM_LIT:0> and next == '<STR_LIT:h>' : <EOL> i += <NUM_LIT:1> <EOL> next = s [ i + <NUM_LIT:1> ] <EOL> if next in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:w>' ) <EOL> elif c == '<STR_LIT:x>' : <EOL> if i == <NUM_LIT:0> : <EOL> if next == '<STR_LIT:h>' or ( next == '<STR_LIT:i>' and nextnext in '<STR_LIT>' ) : <EOL> result . append ( '<STR_LIT:x>' ) <EOL> else : <EOL> result . append ( '<STR_LIT:s>' ) <EOL> else : <EOL> result . append ( '<STR_LIT:k>' ) <EOL> result . append ( '<STR_LIT:s>' ) <EOL> elif c == '<STR_LIT:y>' : <EOL> if next in '<STR_LIT>' : <EOL> result . append ( '<STR_LIT:y>' ) <EOL> elif c == '<STR_LIT:z>' : <EOL> result . append ( '<STR_LIT:s>' ) <EOL> elif c == '<STR_LIT:U+0020>' : <EOL> if len ( result ) > <NUM_LIT:0> and result [ - <NUM_LIT:1> ] != '<STR_LIT:U+0020>' : <EOL> result . append ( '<STR_LIT:U+0020>' ) <EOL> i += <NUM_LIT:1> <EOL> return '<STR_LIT>' . join ( result ) . upper ( ) <EOL> def porter_stem ( s ) : <EOL> if isinstance ( s , bytes ) : <EOL> raise TypeError ( _no_bytes_err ) <EOL> return Stemmer ( s ) . stem ( ) </s>
