블 룸 필터 (Bloom Filter) 의 원리 와 구현

어떤 상황 에서 부 릉 필터 가 필요 합 니까?
먼저 비교적 흔히 볼 수 있 는 몇 가지 예 를 살 펴 보 자.

글자 처리 소프트웨어 에서 영어 단어 가 맞 춤 법 이 맞 는 지 확인 해 야 한다

FBI 에서 한 용의자 의 이름 이 이미 용의자 명단 에 있 는 지

인터넷 파충류 에서 한 사이트 가 방문 되 었 는 지 여부

야후, gmail 등 메 일 스 팸 메 일 여과 기능

이 몇 가지 예 는 공 통 된 특징 이 있다. 어떻게 원소 가 집합 에 존재 하 는 지 판단 합 니까?
일반적인 사고 방식.

배열

링크

나무, 밸 런 스 이 진 트 리, 트 리

지도 (붉 은 검 은 나무)

해시 표

위 에서 설명 한 이 몇 가지 데이터 구 조 는 흔히 볼 수 있 는 정렬 과 결합 되 고 2 분 검색 은 대부분 요소 가 집합 중의 수요 가 있 는 지 를 신속하게 처리 할 수 있다.그러나 집합 안의 원소 수량 이 충분 할 때 500 만 개의 기록, 심지어 1 억 개의 기록 이 있다 면?이때 일반적인 데이터 구조의 문제 가 두 드 러 졌 다.배열, 링크, 트 리 등 데이터 구 조 는 요소 의 내용 을 저장 하고 데이터 의 양 이 너무 많 으 면 소모 하 는 메모리 도 선형 으로 증가 하여 최종 적 으로 병목 에 이 를 것 이다.어떤 학우 들 은 해시 표 가 효율 이 높 지 않 느 냐 고 물 을 수도 있다.조회 효율 은 O (1) 에 도달 할 수 있다.그러나 해시 표 가 소모 해 야 할 메모 리 는 여전히 높다.해시 표를 사용 하여 1 억 개의 쓰레기 이메일 주 소 를 저장 하 는 데 소모 되 는 것 은?해시 표 의 방법: 우선, 해시 함 수 는 이메일 주 소 를 8 바이트 정보 지문 으로 표시 합 니 다.해시 표 의 저장 효율 이 보통 50% 이하 인 것 을 감안 하면 (해시 충돌);따라서 소 모 된 메모리: 8 * 2 * 1 억 바이트 = 1.6G 메모리, 일반 컴퓨터 는 이렇게 큰 메모 리 를 제공 할 수 없습니다.이때 부 릉 필터 (Bloom Filter) 가 생 겨 났 다.부 릉 필터 의 원 리 를 계속 소개 할 때 하 쉬 함수 에 대한 예비 지식 을 먼저 설명 한다.
해시 함수
해시 함수 의 개념 은 임의의 크기 의 데 이 터 를 특정 크기 의 데이터 로 변환 하 는 함수 이 며, 변 환 된 데 이 터 를 해시 값 이나 해시 인 코딩 이 라 고 합 니 다.다음은 설명도 입 니 다.
원시 데 이 터 는 해시 함수 의 매 핑 을 거 친 후에 하나의 해시 인 코딩 이 라 고 부 르 고 데 이 터 는 압축 된 것 을 뚜렷하게 볼 수 있다.해시 함 수 는 해시 표 와 부 릉 필 터 를 실현 하 는 기초 입 니 다.
부 릉 필터 소개

바 톤 부 론 은 1970 년 에 제기 했다

긴 이 진 벡터 (자릿수 그룹)

일련의 랜 덤 함수 (해시)

공간 효율 과 조회 효율 이 높다

어느 정도 오심 율 (해시 표 는 정확 한 일치)

부 릉 필터 원리
블 룸 필터 (Bloom Filter) 의 핵심 실현 은 엄 청 난 자릿수 그룹 과 몇 개의 해시 함수 입 니 다.비트 배열 의 길이 가 m 이 고 해시 함수 의 개 수 는 k 라 고 가정 합 니 다.
상기 그림 을 예 로 들 면 구체 적 인 조작 절차: 집합 안에 3 개의 원소 {x, y, z} 가 있다 고 가정 하면 해시 함수 의 개 수 는 3 이다.우선 비트 배열 을 초기 화하 고 안에 있 는 모든 비트 를 0 으로 설정 합 니 다.집합 안의 모든 요소 에 대해 원 소 를 3 개의 해시 함 수 를 통 해 차례대로 매 핑 합 니 다. 매 핑 할 때마다 해시 값 이 생 깁 니 다. 이 값 은 비트 배열 위의 한 점 에 대응 한 다음 에 비트 배열 에 대응 하 는 위 치 를 1 로 표시 합 니 다.W 요소 가 집합 에 있 는 지 확인 할 때 같은 방법 으로 W 를 해시 를 통 해 자릿수 그룹의 3 개 점 에 투사 합 니 다.만약 세 개의 점 중 하나 가 1 이 아니라면 이 요 소 는 반드시 집합 에 존재 하지 않 는 다 고 판단 할 수 있다.반대로 세 개의 점 이 모두 1 이면 이 요 소 는 집합 에 존재 할 수 있다.주의: 이 요소 가 반드시 집합 에 존재 하 는 지 판단 할 수 없고 어느 정도 오심 율 이 있 을 수 있 습 니 다.그림 에서 볼 수 있 듯 이 특정한 요소 가 맵 을 통 해 아래 에 4, 5, 6 이라는 세 가지 점 으로 표시 된다 고 가정 할 수 있다.이 세 가지 점 은 모두 1 이지 만 이 세 가지 점 은 서로 다른 요소 가 하 쉬 를 거 쳐 얻 은 위치 임 이 분명 하 다. 따라서 이런 상황 은 요소 가 집합 에 있 지 않 지만 대응 하 는 것 이 모두 1 일 수도 있다 는 것 을 설명 한다. 이것 은 오심 율 이 존재 하 는 원인 이다.
부 릉 필터 추가 요소

추가 할 요 소 를 k 개의 해시 함수

에 게 줍 니 다.

비트 배열 에 대응 하 는 k 개 위치

를 얻 었 다.

이 k 위 치 를 1

로 설정 합 니 다.
부 릉 필터 조회 요소

조회 할 요 소 를 k 개의 해시 함수

에 게 줍 니 다.

비트 배열 에 대응 하 는 k 개 위치

를 얻 었 다.

k 개의 위치 가 0 이면 집합 에 없 을 것 이다

k 개의 위치 가 모두 1 이면 집합 중

부 릉 필터 구현
다음은 python 의 실현 을 보 여 줍 니 다. murmurhash 알고리즘 을 사용 하 십시오.

import mmh3from bitarray import bitarray# zhihu_crawler.bloom_filter# Implement a simple bloom filter with murmurhash algorithm.# Bloom filter is used to check wether an element exists in a collection, and it has a good performance in big data situation.# It may has positive rate depend on hash functions and elements count.BIT_SIZE = 5000000class BloomFilter:
    
    def __init__(self):
        # Initialize bloom filter, set size and all bits to 0
        bit_array = bitarray(BIT_SIZE)
        bit_array.setall(0)        self.bit_array = bit_array        
    def add(self, url):
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.)
        # Here use 7 hash functions.
        point_list = self.get_postions(url)        for b in point_list:            self.bit_array[b] = 1

    def contains(self, url):
        # Check if a url is in a collection
        point_list = self.get_postions(url)

        result = True
        for b in point_list:
            result = result and self.bit_array[b]    
        return result    def get_postions(self, url):
        # Get points positions in bit vector.
        point1 = mmh3.hash(url, 41) % BIT_SIZE
        point2 = mmh3.hash(url, 42) % BIT_SIZE
        point3 = mmh3.hash(url, 43) % BIT_SIZE
        point4 = mmh3.hash(url, 44) % BIT_SIZE
        point5 = mmh3.hash(url, 45) % BIT_SIZE
        point6 = mmh3.hash(url, 46) % BIT_SIZE
        point7 = mmh3.hash(url, 47) % BIT_SIZE        return [point1, point2, point3, point4, point5, point6, point7]