add python bloom filter

vk · vk · commit 3857dc76a1ae · 2015-02-21T11:51:34.000+05:30
diff --git a/Bloom_Filter/Python/argvk/.gitignore b/Bloom_Filter/Python/argvk/.gitignore
@@ -0,0 +1 @@
+env/
diff --git a/Bloom_Filter/Python/argvk/BloomFilter.py b/Bloom_Filter/Python/argvk/BloomFilter.py
@@ -0,0 +1,30 @@
+"""
+Bloomfilters are a memory efficient way of checking if an element is part of a set or not
+
+here is a pretty decent tutorial http://billmill.org/bloomfilter-tutorial/
+"""
+
+from bitarray import bitarray
+import mmh3
+
+class BloomFilter:
+
+    def __init__(self):
+        self.HASH_SIZE = 1000
+
+        self.bits = bitarray(self.HASH_SIZE)
+        self.bits.setall(0)
+
+    def add(self, word):
+        for seed in range(self.HASH_SIZE):
+            bit_value = mmh3.hash(word, seed) % self.HASH_SIZE
+            self.bits[bit_value] = 1
+
+    def check(self, word):
+        for seed in range(self.HASH_SIZE):
+            bit_value = mmh3.hash(word, seed) % self.HASH_SIZE
+            if self.bits[bit_value] == 0:
+                return False 
+        return True
+
+
diff --git a/Bloom_Filter/Python/argvk/BloomFilter_test.py b/Bloom_Filter/Python/argvk/BloomFilter_test.py
@@ -0,0 +1,12 @@
+from BloomFilter import BloomFilter
+
+bf = BloomFilter()
+
+bf.add("python")
+bf.add("vk")
+
+test_ok = 0
+
+assert(bf.check("python") == True)
+assert(bf.check("vk") == True)
+assert(bf.check("kaboom") == False)
diff --git a/Bloom_Filter/Python/argvk/requirements.txt b/Bloom_Filter/Python/argvk/requirements.txt
@@ -0,0 +1,2 @@
+bitarray==0.8.1
+mmh3==2.3
