<s> """<STR_LIT>""" <EOL> import collections <EOL> from tornado . options import parse_command_line , options , define <EOL> define ( '<STR_LIT>' , default = <NUM_LIT:0> ) <EOL> define ( '<STR_LIT>' , default = <NUM_LIT:12> ) <EOL> def parse_fp ( fp ) : <EOL> return [ s . decode ( '<STR_LIT>' ) for s in fp . strip ( ) . split ( '<STR_LIT::>' ) ] <EOL> kTagLengths = [ <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:4> ] <EOL> def gen_tags ( fp ) : <EOL> for term in fp : <EOL> term = term . encode ( '<STR_LIT>' ) <EOL> pos = <NUM_LIT:0> <EOL> for l in kTagLengths : <EOL> yield '<STR_LIT>' % ( pos , term [ pos : pos + l ] ) <EOL> pos += l <EOL> assert pos == len ( term ) <EOL> def count_bits ( n ) : <EOL> return bin ( n ) . count ( '<STR_LIT:1>' ) <EOL> def hamming ( t1 , t2 ) : <EOL> assert len ( t1 ) == len ( t2 ) <EOL> total = <NUM_LIT:0> <EOL> for c1 , c2 in zip ( t1 , t2 ) : <EOL> d = ord ( c1 ) ^ ord ( c2 ) <EOL> total += count_bits ( d ) <EOL> return total <EOL> def distance ( fp1 , fp2 ) : <EOL> return min ( hamming ( t1 , t2 ) for t1 in fp1 for t2 in fp2 ) <EOL> class Index ( object ) : <EOL> def __init__ ( self ) : <EOL> self . index = collections . defaultdict ( list ) <EOL> def load ( self , filename ) : <EOL> with open ( filename ) as f : <EOL> for line in f : <EOL> filename , fingerprint = line . split ( '<STR_LIT:\t>' ) <EOL> fingerprint = parse_fp ( fingerprint ) <EOL> for tag in gen_tags ( fingerprint ) : <EOL> self . index [ tag ] . append ( ( filename , fingerprint ) ) <EOL> def find_matches ( self , min_hamming , max_hamming ) : <EOL> assert min_hamming <= max_hamming <EOL> assert max_hamming <= <NUM_LIT:12> , '<STR_LIT>' <EOL> seen = set ( ) <EOL> for tag , lst in self . index . iteritems ( ) : <EOL> for fn1 , fp1 in lst : <EOL> for fn2 , fp2 in lst : <EOL> if fn1 == fn2 : <EOL> continue <EOL> key = tuple ( sorted ( [ fn1 , fn2 ] ) ) <EOL> if key in seen : <EOL> continue <EOL> seen . add ( key ) <EOL> dist = distance ( fp1 , fp2 ) <EOL> if min_hamming <= dist <= max_hamming : <EOL> print '<STR_LIT>' % ( fn1 , fn2 , dist ) <EOL> def main ( ) : <EOL> args = parse_command_line ( ) <EOL> index = Index ( ) <EOL> for arg in args : <EOL> index . load ( arg ) <EOL> index . find_matches ( options . min , options . max ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> main ( ) </s>
