파이썬의 현대적이고 고성능 블룸 필터?
https://stackoverflow.com/questions/311202
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 Python에서 생산 품질 블룸 필터 구현을 찾고 있으며 상당히 많은 수의 품목 (예 : 0.01% 오 탐지 속도의 100m ~ 1B 항목)을 처리합니다.
파이 블룸 하나의 옵션이지만 Python 2.5에서 정기적으로 감가 상각 오류를 던지기 때문에 나이가 표시되는 것 같습니다. Joe Gregorio도 있습니다 구현.
요구 사항은 빠른 조회 성능 및 안정성입니다. 또한 우수한 C/C ++ 구현 또는 Jython에 좋은 Java 구현이있는 경우 Python 인터페이스를 만들 수 있습니다.
그로 인해 ~ 16e9 비트를 처리 할 수있는 비트 어레이 / 비트 벡터 표현에 대한 권장 사항이 없습니까?
해결책 3
결국 나는 찾았다 pybloomfiltermap. 나는 그것을 사용하지 않았지만 법안에 맞는 것처럼 보입니다.
다른 팁
나는 최근 에이 길을 내려 갔다. 내 응용 프로그램이 약간 다른 것처럼 들리지만. 많은 문자열에서 세트 작업을 근사화하는 데 관심이있었습니다.
당신은 a 빠른 비트 벡터가 필요합니다. 블룸 필터에 넣고 싶은 것에 따라 사용 된 해싱 알고리즘의 속도에 대해 생각해야 할 수도 있습니다. 당신은 이것을 찾을 수 있습니다 도서관 유용한. 아래에 사용 된 임의의 숫자 기술을 한 번만 해시하는 것만으로도 땜질을 원할 수도 있습니다.
비 자바 비트 어레이 구현 측면에서 :
- 부스트가 있습니다 dynamic_bitset
- Java에는 내장되어 있습니다 비츠 세트
블룸 필터를 사용하여 만들었습니다 비트 벡터. 나는 도서관을 프로파일 링하고 최적화하고 AVI에 패치를 다시 기고하는 데 시간을 보냈습니다. 해당 비트 벡터 링크로 이동하여 아래로 스크롤하여 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
#
# ryan.a.cox@gmail.com / 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]
Parand에 대한 반응으로 "일반적인 관행은 Sha1과 같은 것을 사용하고 여러 해시를 형성하기 위해 비트를 나누는 것 같습니다"라고 말하면서, 그것은 일반적인 관행 (Pybloom도 사용)이라는 의미에서 사실 일 수 있습니다. t 그것은 옳은 일이라는 것을 의미합니다 ;-)
블룸 필터의 경우 해시 함수에 유일한 요구 사항은 출력 공간이 예상 입력을 고려하여 균일하게 분배해야한다는 것입니다. 암호화 해시는 확실히이 요구 사항을 충족하지만 바주카로 파리를 촬영하는 것도 거의 없습니다.
대신 시도하십시오 FNV 해시 입력 바이트 당 하나의 XOR과 하나의 곱셈을 사용하는데, 이는 SHA1보다 수백 배 더 빠른 것으로 추정됩니다 :)
FNV 해시는 암호화 적으로 안전하지 않지만 필요하지 않습니다. 약간 있습니다 불완전한 눈사태 행동, 그러나 당신은 무결성 검사를 위해 그것을 사용하지 않습니다.
균일성에 대해, 두 번째 링크는 32 비트 FNV 해시에 대한 카이-제곱 테스트 만 수행했습니다. 더 많은 비트와 FNV-1 변형을 사용하는 것이 좋습니다. 블룸 필터의 경우 출력을 비트 어레이의 인덱스 범위에 균일하게 매핑하는 것과 같은 몇 가지 어획량이 더 있습니다. 가능하면 비트 어레이의 크기를 가장 가까운 2의 전력으로 반올림하고 조정합니다. 케이 따라서. 이렇게하면 정확도가 향상되고 간단한 xor 폴딩을 사용하여 범위를 매핑 할 수 있습니다.
또한 다음은 필요한 경우 SHA1 (또는 암호화 해시)을 원하지 않는 이유를 설명하는 참조입니다. 범용 해시.
를보세요 정렬 기준 치수.
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. 이것 5월 약간의 모호함에 따라 약간 더 빠른 속도로 이어집니다.
또한 변화 'B' 그리고 8 에게 'L' 그리고 32 대부분의 하드웨어에서 더 빠르야합니다. [변경 'H' 그리고 일부 하드웨어에서는 16 명이 더 빠를 수 있지만 의심 스럽습니다.
파이썬 블룸 필터 구현을했습니다 http://stromberg.dnsalias.org/~strombrg/drs-cloom-filter/
순수한 파이썬, 좋은 해시 함수, 좋은 자동 테스트, 백엔드 선택 (디스크, 배열, MMAP 등) 및보다 직관적 인 논증이 있습니다. __init__ 방법으로, 다소 미묘한 데이터 특정 튜블에 대신 이상적인 요소와 원하는 최대 오류율을 지정할 수 있습니다.
블룸 필터 변형, 성능에 관심이 있으며 사용 사례를 이해합니다. Bloom 필터 변형에 대한 잘 인용 된 연구가 너무 많지만 (SIGCOMM, SIGMETRICS와 같은 최고 수준의 컨퍼런스에 출판 된 연구), 나는 주류 언어 라이브러리에서 그들의 존재가 강력하다고 생각하지 않습니다. 왜 그게 사실이라고 생각합니까?
내 관심은 언어에 대한 정보이지만 Bloom 필터 변형에 대해 작성한 기사와 Bloom 필터의 응용 프로그램을 공유하고 싶었습니다.
http://appolo85.wordpress.com/2010/08/03/bloom-filter/
블룸 필터 변형의 사용 사례, 디자인/구현 및 다른 언어로 라이브러리에 대해 더 많이 배우고 싶습니다.
Bloom 필터 변형에 대한 대부분의 간행물과 (코드?)가 박사 학위 졸업생의 게시 된 용지 수를 증가시키는 역할을한다고 생각하십니까?
아니면 대부분의 사람들이 "잘 작동하는"생산 준비 표준 블룸 필터 구현을 엉망으로 만들고 싶지 않습니까? : D
