我正在尋找一個生產質量布隆過濾器實現在Python中處理相當大數量的項目（比如說100M到1B的項目與0.01％的誤報率）。Python中的現代高性能布隆過濾器？
Pybloom是一個選項，但它似乎顯示了它的年齡，因爲它定期拋出Python 2.5上的DeprecationWarning錯誤。喬格雷戈里奧也有an implementation。
要求是快速查找性能和穩定性。我也願意爲特別優秀的c/C++實現創建Python接口，如果有良好的Java實現，甚至可以創建Jython。
缺乏這一點，任何有關位/陣列/位矢量表示的建議，可以處理〜16E9位？
最後我終於找到pybloomfiltermap。我沒有用過它，但看起來它符合法案。
看看array模塊。
class Bit(object):
def __init__(self, size):
self.bits= array.array('B',[0 for i in range((size+7)//8)])
def set(self, bit):
b= self.bits[bit//8]
self.bits[bit//8] = b | 1 << (bit % 8)
def get(self, bit):
b= self.bits[bit//8]
return (b >> (bit % 8)) & 1
FWIW，所有//8和% 8操作都可以用>>3和&0x07所取代。這可能導致略微更好的速度在一些模糊的風險。
此外，將'B'和8更改爲'L'和32在大多數硬件上應該更快。 [更改爲'H'和16可能在某些硬件上速度更快，但值得懷疑。]
太可愛了！ +1 – 2008-11-22 16:52:33
我最近也走了這條路;儘管聽起來我的申請有些不同。我對在大量字符串上近似設置操作感興趣。
您確實需要一個快速位向量。根據你想放在布隆過濾器中的內容，你可能還需要考慮一下哈希算法的使用速度。你可能會發現這個library有用。您也可能想要使用下面使用的隨機數技術，一次只掃描您的密鑰。
在非Java位陣列實現的方面：
我使用BitVector建立我的布隆過濾器。我花了一些時間分析和優化庫，並將補丁提供給Avi。轉到BitVector鏈接並向下滾動到v1.5中的確認以查看詳細信息。最後，我意識到性能不是這個項目的目標，並決定不使用它。
下面是我躺在身邊的一些代碼。我可能會把它放在python-bloom的google代碼上。建議歡迎。
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
此外，在我的情況下，我發現有一個更快的BitVector的count_bits函數是有用的。將此代碼放入BitVector 1中。5，它應該給你一個更高性能位的計數方法：
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]
謝謝瑞安，非常翔實。關於BitVector的性能，您是否找到了更快的選擇？ 另外，我注意到你只用了4個哈希，這看起來有點低。對此有何想法？一種常見的做法似乎是使用諸如SHA1之類的東西，並將這些位分割成多個哈希值。 – Parand 2008-11-23 02:06:05
Hashcount取決於：＃元素和可接受的假陽性率。我有一個改進版本的上面，我將簽入。沒有找到更快的東西（儘管我認爲這將是一個本地實現）。 – 2008-11-27 19:04:26
我非常感興趣的是布盧姆過濾器的變體，他們的表現和理解他們的用例。 關於布盧姆過濾器變體（包括SIGCOMM，SIGMETRICS等頂級會議上發佈的那些變體）的研究工作如此之多，但我不認爲他們在主流語言庫中的存在性很強。你爲什麼認爲這種情況？
雖然我的興趣是語言不可知的，但我想分享一篇關於Bloom過濾器變體和Bloom過濾器應用程序的文章。
http://appolo85.wordpress.com/2010/08/03/bloom-filter/
我很想了解更多關於布隆過濾器變種其使用情況，以及它們的設計/實施，和庫在其他語言。
您認爲Bloom上的大部分出版物和（代碼？）過濾器變體僅用於增加博士畢業生的發表論文數量？
或者是大多數人不想搗亂生產就緒的標準布隆過濾器實施，「工作得很好」：D
對Parand的反應，說「通常的做法似乎是使用像SHA1並分裂形成多個散列「，雖然這是常見的做法（PyBloom也使用它），但這並不意味着它是正確的做法; - ）
For Bloom過濾器是散列函數的唯一要求，它的輸出空間必須在給定期望輸入的情況下均勻分佈。雖然密碼哈希值肯定滿足了這個要求，但它有點像使用火箭筒拍攝蒼蠅。
而是嘗試它使用只有一個XOR和每個輸入字節，我估計比SHA1 :)
的FNV哈希不加密安全快幾百倍一個乘法FNV Hash，但你不知道需要它。它略有imperfect avalanche behaviour，但是您並未將其用於完整性檢查。
關於統一性，請注意第二個鏈接僅對32位FNV哈希進行了卡方檢驗。最好使用更多的位和FNV-1變體，它們交換XOR和MUL步驟以獲得更好的位擴散。對於布隆過濾器，還有幾個捕獲點，比如將輸出均勻映射到位陣列的索引範圍。如果可能的話，我會說比特陣列的大小是2的最接近的冪，並相應地調整k。這樣你可以獲得更好的準確性，並且可以使用簡單的XOR摺疊來繪製範圍。
此外，這裏有一個參考解釋爲什麼你不需要SHA1（或任何加密哈希），當你需要a general purpose hash。
你可以用it.unimi.dsi.util.BloomFilter的The DSI Utilities來嘗試。
我已經提出了一個蟒蛇布隆過濾器實現在http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/
它是純Python，具有良好的散列函數，良好的自動化測試，選擇後端的（磁盤，陣列，MMAP，更多），更直觀參數爲__init__方法，因此您可以指定理想數量的元素和所需的最大錯誤率，而不是特定的數據結構特定的可調參數。
出於興趣，你能解釋一下現有的實現（特別是PyBloom）有什麼問題嗎？它可能是「牙齒長」，但如果它有效並且不需要修復，那聽起來像是一個加號。 – Oddthinking 2008-11-22 15:01:15
奇怪的想法，更新了一些解釋。 – Parand 2008-11-22 15:13:10