
# coding:utf-8

# http://blog.csdn.net/sdj222555/article/details/7970466


class SimHash:

    def __init__(self, tokens='', bits=128):
        self.bits = bits
        self.hash = self.simhash(tokens)

    def __str__(self):
        return str(self.hash)

    def simhash(self, tokens):
        v = [0] * self.bits
        for t in [self.string_hash(x) for x in tokens]:
            for i in range(self.bits):
                bitmask = 1 << i
                if t & bitmask:
                    v[i] += 1
                else:
                    v[i] -= 1
        fingerprint = 0
        for i in range(self.bits):
            if v[i] >= 0:
                fingerprint += 1 << i
        return fingerprint

    def hamming_distance(self, other):
        x = (self.hash ^ other.hash) & ((1 << self.bits) - 1)
        cnt = 0
        while x:
            cnt += 1
            x &= x - 1
        return cnt

    def similarity(self, other):
        a = float(self.hash)
        b = float(other.hash)
        if a > b:
            return b / a
        else:
            return a / b

    def string_hash(self, source):
        if source == '':
            return 0
        else:
            x = ord(source[0]) << 7
            m = 1000003
            mask = 2 ** self.bits - 1
            for c in source:
                x = ((x * m) ^ ord(c)) & mask
            x ^= len(source)
            if x == -1:
                x = -2
            return x


if __name__ == '__main__':
    pass
