Gần đây tôi cũng đã đi xuống con đường này; mặc dù có vẻ như ứng dụng của tôi hơi khác một chút. Tôi đã quan tâm đến việc xấp xỉ các hoạt động thiết lập trên một số lượng lớn các chuỗi.
Bạn thực hiện quan sát chính rằng cần có tốc độ bit nhanh bit. Tùy thuộc vào những gì bạn muốn đưa vào bộ lọc nở của bạn, bạn cũng có thể cần phải suy nghĩ về tốc độ của thuật toán băm được sử dụng. Bạn có thể tìm thấy điều này library hữu ích. Bạn cũng có thể muốn tinker với kỹ thuật số ngẫu nhiên được sử dụng dưới đây mà chỉ băm khóa của bạn một lần duy nhất.
Về-Java không triển khai mảng bit:
tôi đã xây dựng bộ lọc nở của tôi sử dụng BitVector. Tôi đã dành một chút thời gian để lập hồ sơ và tối ưu hóa thư viện và đóng góp các bản vá của mình cho Avi. Đi đến liên kết BitVector đó và cuộn xuống để xác nhận trong v1.5 để xem chi tiết. Cuối cùng, tôi nhận ra rằng hiệu suất không phải là mục tiêu của dự án này và quyết định không sử dụng nó.
Đây là một số mã tôi đã nói dối. Tôi có thể đặt điều này lên trên mã google tại python nở. Đề nghị chào đón.
from BitVector import BitVector
from random import Random
# get hashes from http://www.partow.net/programming/hashfunctions/index.html
from hashes import RSHash, JSHash, PJWHash, ELFHash, DJBHash
#
# [email protected]/www.asciiarmor.com
#
# copyright (c) 2008, ryan cox
# all rights reserved
# BSD license: http://www.opensource.org/licenses/bsd-license.php
#
class BloomFilter(object):
def __init__(self, n=None, m=None, k=None, p=None, bits=None):
self.m = m
if k > 4 or k < 1:
raise Exception('Must specify value of k between 1 and 4')
self.k = k
if bits:
self.bits = bits
else:
self.bits = BitVector(size=m)
self.rand = Random()
self.hashes = []
self.hashes.append(RSHash)
self.hashes.append(JSHash)
self.hashes.append(PJWHash)
self.hashes.append(DJBHash)
# switch between hashing techniques
self._indexes = self._rand_indexes
#self._indexes = self._hash_indexes
def __contains__(self, key):
for i in self._indexes(key):
if not self.bits[i]:
return False
return True
def add(self, key):
dupe = True
bits = []
for i in self._indexes(key):
if dupe and not self.bits[i]:
dupe = False
self.bits[i] = 1
bits.append(i)
return dupe
def __and__(self, filter):
if (self.k != filter.k) or (self.m != filter.m):
raise Exception('Must use bloom filters created with equal k/m paramters for bitwise AND')
return BloomFilter(m=self.m,k=self.k,bits=(self.bits & filter.bits))
def __or__(self, filter):
if (self.k != filter.k) or (self.m != filter.m):
raise Exception('Must use bloom filters created with equal k/m paramters for bitwise OR')
return BloomFilter(m=self.m,k=self.k,bits=(self.bits | filter.bits))
def _hash_indexes(self,key):
ret = []
for i in range(self.k):
ret.append(self.hashes[i](key) % self.m)
return ret
def _rand_indexes(self,key):
self.rand.seed(hash(key))
ret = []
for i in range(self.k):
ret.append(self.rand.randint(0,self.m-1))
return ret
if __name__ == '__main__':
e = BloomFilter(m=100, k=4)
e.add('one')
e.add('two')
e.add('three')
e.add('four')
e.add('five')
f = BloomFilter(m=100, k=4)
f.add('three')
f.add('four')
f.add('five')
f.add('six')
f.add('seven')
f.add('eight')
f.add('nine')
f.add("ten")
# test check for dupe on add
assert not f.add('eleven')
assert f.add('eleven')
# test membership operations
assert 'ten' in f
assert 'one' in e
assert 'ten' not in e
assert 'one' not in f
# test set based operations
union = f | e
intersection = f & e
assert 'ten' in union
assert 'one' in union
assert 'three' in intersection
assert 'ten' not in intersection
assert 'one' not in intersection
Ngoài ra, trong trường hợp của tôi, tôi thấy hữu ích khi có hàm count_bits nhanh hơn cho BitVector. Thả mã này vào BitVector 1.5 và nó sẽ cung cấp cho bạn phương pháp đếm bit hiệu quả hơn:
def fast_count_bits(self, v):
bits = (
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8)
return bits[v & 0xff] + bits[(v >> 8) & 0xff] + bits[(v >> 16) & 0xff] + bits[v >> 24]
Không quan tâm, bạn có thể giải thích điều gì sai với các triển khai hiện có (đặc biệt là PyBloom) không? Nó có thể là "dài trong răng", nhưng nếu nó hoạt động và không cần sửa chữa, mà âm thanh như một cộng. – Oddthinking
Oddthinking, cập nhật với một số lời giải thích. – Parand