<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> __version__ = '<STR_LIT>' <EOL> from collections import defaultdict <EOL> from scipy import array <EOL> from numpy . random import permutation <EOL> def arrayPermutation ( permutation ) : <EOL> """<STR_LIT>""" <EOL> assert permutation . ndim == <NUM_LIT:1> , "<STR_LIT>" <EOL> def permute ( arr ) : <EOL> assert arr . ndim == <NUM_LIT:1> , "<STR_LIT>" <EOL> assert arr . shape == permutation . shape , "<STR_LIT>" <EOL> return array ( [ arr [ i ] for i in permutation ] ) <EOL> return permute <EOL> def jacardCoefficient ( a , b ) : <EOL> """<STR_LIT>""" <EOL> if a . shape != b . shape : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> length = a . shape [ <NUM_LIT:0> ] <EOL> a = a . astype ( bool ) <EOL> b = b . astype ( bool ) <EOL> return float ( ( a == b ) . sum ( ) ) / length <EOL> class MinHash ( object ) : <EOL> """<STR_LIT>""" <EOL> def __setPermutations ( self , permutations ) : <EOL> self . _permutations = permutations <EOL> self . _permFuncs = [ arrayPermutation ( i ) for i in permutations ] <EOL> def __getPermutations ( self ) : <EOL> return self . _permutations <EOL> permutations = property ( __getPermutations , <EOL> __setPermutations ) <EOL> def __init__ ( self , dim , nPermutations ) : <EOL> """<STR_LIT>""" <EOL> self . dim = dim <EOL> self . permutations = array ( [ permutation ( dim ) <EOL> for _ in range ( nPermutations ) ] ) <EOL> self . buckets = defaultdict ( lambda : [ ] ) <EOL> def _firstOne ( self , arr ) : <EOL> """<STR_LIT>""" <EOL> for i , elem in enumerate ( arr ) : <EOL> if elem == <NUM_LIT:1> : <EOL> return i <EOL> return i + <NUM_LIT:1> <EOL> def _checkItem ( self , item ) : <EOL> if item . ndim != <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if item . shape != ( self . dim , ) : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> def _hash ( self , item ) : <EOL> """<STR_LIT>""" <EOL> self . _checkItem ( item ) <EOL> result = [ ] <EOL> for perm in self . _permFuncs : <EOL> permuted = perm ( item ) <EOL> result . append ( self . _firstOne ( permuted ) ) <EOL> return tuple ( result ) <EOL> def put ( self , item , satellite ) : <EOL> """<STR_LIT>""" <EOL> self . _checkItem ( item ) <EOL> item = item . astype ( bool ) <EOL> bucket = self . _hash ( item ) <EOL> self . buckets [ bucket ] . append ( ( item , satellite ) ) <EOL> def knn ( self , item , k ) : <EOL> """<STR_LIT>""" <EOL> self . _checkItem ( item ) <EOL> candidates = self . buckets [ self . _hash ( item ) ] <EOL> candidates . sort ( key = lambda x : jacardCoefficient ( x [ <NUM_LIT:0> ] , item ) , <EOL> reverse = True ) <EOL> return candidates [ : k ] </s>
