간단 하고 효율 적 인 데이터 구조 - Bloom Filter (부 릉 필터)

배경: 오 군 박사의 《 수학의 미 》 를 뒤 적 였 을 때 부 릉 필 터 를 보 았 기 때문에 이에 대한 자신의 인식 을 정리 합 니 다.
1. 부 릉 필 터 는 무엇 에 사용 합 니까?
        부 릉 필 터 는 하나의 요소 가 하나의 집합 에 속 하 는 지 여 부 를 판단 하 는 데 사용 할 수 있다. 더욱 엄밀 하 게 말 하면 하나의 요소 가 특정한 집합 에 속 하지 않 는 지 100% 확인 할 수 있 지만 하나의 요소 가 특정한 집합 에 속 하 는 지 100% 확인 할 수 없다.        그 사용 장면 에 대해 가장 먼저 생각 한 것 은 '높 은 조작 을 해 야 하 는 지' 를 판단 하 는 것 이다. 예 를 들 어 네트워크 나 디스크 에 있 는 일부 자원 을 방문 하 는 것 이다.예 를 들 어 Google 의 BitTable 과 Apach HBase 는 브 론 필 터 를 사용 하여 조회 한 데이터 가 저장 되 어 있 는 지 여 부 를 판단 하여 디스크 를 계속 읽 어야 하 는 지 여 부 를 확인 합 니 다.예 를 들 어 파충류 로 웹 페이지 를 캡 처 할 때 일부 웹 페이지 는 서로 연결 되 거나 여러 웹 페이지 에 같은 웹 링크 가 포함 되 어 있 기 때문에 부 릉 필 터 를 사용 하여 url 이 기어 올 랐 는 지 여 부 를 판단 하여 이 url 의 방문 을 계속 할 지 여 부 를 확인한다.
2. 부 릉 필 터 는 어떻게 실현 하고 사용 합 니까?
        부 릉 필 터 는 두 부분 으로 구성 되 어 있 습 니 다. 하나의 비트 배열 과 하나의 해시 함수 입 니 다.부 릉 필 터 를 초기 화하 기 위해 서, 우 리 는 비트 그룹의 모든 위 치 를 0 으로 설정 합 니 다.그래서 만약 에 우리 가 열 개의 배열 이 있다 면:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        집합 에 원 소 를 추가 할 때, 우 리 는 원 소 를 입력 으로 산열 함수 에 제공 합 니 다.해시 함수 마다 배열 색인 을 출력 합 니 다.만약 에 문자열 'hello' 를 두 개의 해시 함수 f1, f2 에 전달한다 고 가정 하면 이 두 개의 해시 함 수 는 색인 0 과 4 를 제공 합 니 다. 우 리 는 비트 배열 의 해당 위 치 를 1 로 설정 합 니 다.

[1, 0, 0, 0, 1, 0, 0, 0, 0, 0]

        하나의 요 소 를 조회 할 때 우 리 는 요 소 를 두 개의 해시 함수 에 전달 하고 두 개의 색인 을 얻 은 후에 배열 의 해당 비트 의 값 을 검사 합 니 다.

두 값 중 0 이 있 으 면 가능 한 색인 값 조합 (0, 0), (0, 1), (1, 0) 이 있 으 면 이 요소 가 집합 에 없 음 을 판단 할 수 있다.따라서 모든 함수 가 위치 로 돌아 가 는 값 을 검사 할 필요 가 없습니다. 최소한 하나의 값 이 0 인 것 을 발견 하면 이 요소 가 집합 에 없 음 을 판단 할 수 있 습 니 다.예 를 들 어 우 리 는 '워드' 가 집합 에 속 하 는 지, 두 함수 가 돌아 오 는 색인 이 1 과 5 라 고 가정 해 야 한다.두 색인 비트 값 이 모두 0 이기 때문에 그 중 한 자 리 를 검사 하면 '워드 는 집합 에 속 하지 않 는 다' 는 결론 을 얻 을 수 있다.

두 값 이 모두 1 이면 "이 요 소 는 집합 중 일 수 있 습 니 다" 라 고 판정 할 수 있 습 니 다. 해시 함수 가 충돌 할 수 있 기 때 문 입 니 다. 예 를 들 어 우 리 는 두 함수 로 "Bloom" 의 색인 을 1 과 9 로 가 져 올 수 있 습 니 다. "filter" 의 색인 을 가 져 오 면 5 와 7 이 될 수 있 습 니 다. 이 때 "word" 를 조회 하면 1 과 9 가 "bloom" 과 "filter" 로 가 져 올 수 있 습 니 다.1 로 설정 되 어 충돌 이 발생 했 습 니 다. 따라서 검색 요소 가 집합 에 있 는 지 100% 확인 할 수 없습니다.

        하나의 요소 집합 을 제거 할 때 '해시 함수 가 충돌 할 수 있 습 니 다' 는 문제 로 인해 요소 의 해당 위 치 를 초기 화 하려 면 같은 색인 위 치 를 가 진 다른 요 소 를 잘못 삭제 할 수 있 기 때문에 비트 배열 을 처리 할 필요 가 없습니다.
3. 왜 부 릉 필터 의 효율 이 비교적 높 습 니까?
시간 복잡 도

요 소 를 추가 할 때 교체 배열 이 필요 하지 않 고 색인 비트 의 값 을 간단하게 설정 하기 때문에 작업 에 걸 리 는 시간 은 해시 함수 의 개수 에 달 려 있 기 때문에 k 개의 해시 함수 에 대한 부 릉 필터 에 요 소 를 추가 하 는 시간 복잡 도 는 O (k) 입 니 다.

요 소 를 조회 할 때 k 개 해시 함수 의 부 릉 필터 에 대해 비트 배열 에서 검사 하 는 색인 수량 이 변 하지 않 는 상계 만 있 기 때문에 요 소 를 조회 하 는 시간 복잡 도 는 O (k) 입 니 다.

공간 복잡 도
        요 소 를 저장 할 필요 가 없 기 때문에 일정한 길이 의 자릿수 그룹 에 의존 하여 존재 여 부 를 판단 하고 배열 의 길이 의 크기 도 집합 에서 요소 의 많 고 적 음 에 달 려 있 지 않 으 며 오심 율 이 커지 거나 효율 이 낮 아 지 는 대가 로 저장 (자릿수 그룹) 을 줄 일 수 있다.
4. 부 릉 필 터 는 어떤 단점 이 있 습 니까?
        주요 단점 은 어느 정도 오심 율 과 삭제 가 어렵 기 때문에 집합 에 저 장 된 요소 가 증가 함 에 따라 오심 율 도 증가한다. 오심 율 의 크기 는 세 가지 기준 과 관련 이 있다. 즉, 자릿수 그룹 길이 m, 집합 길이 n, 해시 함수 개수 k 이다. 그 관 계 는 문헌 을 참고 할 수 있다. 이 문헌 은 주어진 m, n, k = ln (2) 에 대해 증명 했다.* m / n 시 오 판 률 이 가장 낮다.