[PYTHON] BloomFilter

 

Bloom Filter는 특정 데이터가 어떤 집합에 포함되어 있는지를 빠르게 확인할 수 있는 방법입니다. 이 구조는 메모리를 효율적으로 사용하면서도, 아주 빠른 검색 속도를 제공합니다.

 

1. 확률적: Bloom Filter는 요소가 존재하지 않으면 확실히 알려주지만, 요소가 존재한다고 할 경우 '거짓 긍정(false positive)'이 발생할 수 있습니다. 즉, 실제로는 존재하지 않는 요소를 존재한다고 잘못 판단할 수 있습니다.
2. 메모리 효율성: Bloom Filter는 해시 함수와 비트 배열을 사용하여 메모리 사용을 최소화합니다. 이는 많은 양의 데이터를 처리할 때 유리합니다.
3. 비용 효율적인 삽입 및 검색: 요소를 추가하거나 검색할 때 O(k) 시간 복잡도를 가지며, 여기서 k는 사용된 해시 함수의 수입니다.

 

Bloom Filter의 구현 코드

 

import hashlib
from bitmap import BitMap

class BloomFilter:
    def __init__(self, m, k):
        self.m = m  # 비트맵의 크기
        self.k = k  # 해시 함수의 수
        self.n = 0  # 현재 추가된 항목 수
        self.bf = BitMap(m)  # 비트맵 초기화

    def getPositions(self, item):
        positions = []
        for i in range(1, self.k + 1):
            h = hashlib.sha256((item + str(i)).encode()).hexdigest()  # 해시 생성
            pos = int(h, 16) % self.m  # 비트맵의 위치 계산
            positions.append(pos)
        return positions

    def add(self, item):
        positions = self.getPositions(item)  # 해시로부터 위치 얻기
        for pos in positions:
            self.bf.set(pos)  # 비트맵에 비트 설정
        self.n += 1  # 항목 수 증가

    def contains(self, item):
        positions = self.getPositions(item)  # 해시로부터 위치 얻기
        for pos in positions:
            if not self.bf[pos]:  # 비트가 설정되어 있지 않으면
                return False
        return True  # 모든 비트가 설정되어 있으면 존재한다고 판단

    def reset(self):
        self.bf.reset()  # 비트맵 초기화
        self.n = 0  # 항목 수 초기화

    def __repr__(self):
        num_set_bits = self.bf.count()  # 설정된 비트 수 계산
        return f"M = {self.m}, F = {self.k}\n" \
               f"BitMap = {self.bf}\n" \
               f"항목의 수 = {self.n}, 1인 비트수 = {num_set_bits}"

if __name__ == "__main__":
    bf = BloomFilter(53, 3)  # Bloom Filter 생성 (53 비트 크기, 3개의 해시 함수 사용)
    for ch in "AEIOU":  # 모음 추가
        bf.add(ch)
    print(bf)  # 현재 상태 출력
    for ch in "ABCDEFGHIJ":  # A부터 J까지 존재 여부 확인
        print(ch, bf.contains(ch))

 

1. 클래스 초기화: __init__ 메서드는 Bloom Filter의 비트맵 크기(m)와 해시 함수의 수(k)를 설정합니다. 또한, 현재 추가된 항목 수(n)와 비트맵을 초기화합니다.
2. 위치 계산: getPositions 메서드는 주어진 항목에 대해 k개의 해시 값을 생성하고, 이 해시 값들을 사용하여 비트맵의 위치를 계산합니다.
3. 항목 추가: add 메서드는 항목을 Bloom Filter에 추가합니다. 이 메서드는 getPositions를 호출하여 위치를 얻고, 각 위치에 대해 비트를 설정합니다.
4. 존재 여부 확인: contains 메서드는 주어진 항목이 Bloom Filter에 존재하는지 확인합니다. 모든 해시 위치가 설정되어 있으면 항목이 존재한다고 판단합니다.
5. 비트맵 초기화: reset 메서드는 비트맵을 초기화하고, 항목 수를 0으로 설정합니다.
6. 정보 출력: __repr__ 메서드는 현재 Bloom Filter의 상태를 문자열로 반환합니다. 비트맵의 크기, 해시 함수의 수, 설정된 비트 수 등을 포함합니다.
7. 메인 실행: __main__ 블록에서 Bloom Filter를 생성하고, 모음(A, E, I, O, U)을 추가한 후, A부터 J까지의 문자에 대해 존재 여부를 확인하고 결과를 출력합니다.

이 코드를 통해 Bloom Filter의 작동 원리와 메모리 효율적인 데이터 존재 확인 방법을 이해할 수 있습니다.

 

깃허브

https://github.com/Ghoney99/Network-Secure-and-BlockChain