source: simhash.py @ 0:2f43cb89e87c

Revision 0:2f43cb89e87c, 2.1 KB checked in by andre.hagenbruch@rub.de, 7 years ago (diff)

Initial commit for version 0.2

Line 
1#!/usr/bin/python
2
3# Implementation of Charikar simhashes in Python
4# See: http://dsrg.mff.cuni.cz/~holub/sw/shash/#a1
5
6class Simhash():
7    def __init__(self, tokens='', hashbits=128):
8        self.hashbits = hashbits
9        self.hash = self.simhash(tokens)
10
11    def __str__(self):
12        return str(self.hash)
13   
14    def __long__(self):
15        return long(self.hash)
16
17    def __float__(self):
18        return float(self.hash)
19   
20    def simhash(self, tokens):
21        # Returns a Charikar simhash with appropriate bitlength
22        v = [0]*self.hashbits
23   
24        for t in [self._string_hash(x) for x in tokens]:
25            bitmask = 0
26            for i in xrange(self.hashbits):
27                bitmask = 1 << i
28                if t & bitmask:
29                    v[i] += 1
30                else:
31                    v[i] -= 1
32   
33        fingerprint = 0
34        for i in xrange(self.hashbits):
35            if v[i] >= 0:
36                fingerprint += 1 << i
37       
38        return fingerprint
39
40    def _string_hash(self, v):
41        # A variable-length version of Python's builtin hash
42        if v == "":
43            return 0
44        else:
45            x = ord(v[0])<<7
46            m = 1000003
47            mask = 2**self.hashbits-1
48            for c in v:
49                x = ((x*m)^ord(c)) & mask
50            x ^= len(v)
51            if x == -1: 
52                x = -2
53            return x
54
55    def hamming_distance(self, other_hash):
56        x = (self.hash ^ other_hash.hash) & ((1 << self.hashbits) - 1)
57        tot = 0
58        while x:
59            tot += 1
60            x &= x-1
61        return tot
62
63    def similarity(self, other_hash):
64        a = float(self.hash)
65        b = float(other_hash)
66        if a>b: return b/a
67        return a/b
68
69if __name__ == '__main__':
70    s = 'This is a test string for testing'
71    hash1 = Simhash(s.split())
72    print "%s\t[simhash = 0x%x]" % (s, hash1)
73
74    s = 'This is a test string for testing also!'
75    hash2 = Simhash(s.split())
76    print "%s\t[simhash = 0x%x]" % (s, hash2)
77
78    print hash1.similarity(hash2), "percent similar"
79    print hash1.hamming_distance(hash2), "bits differ out of", hash1.hashbits
Note: See TracBrowser for help on using the repository browser.