블룸 필터 편집하기 (부분)

=== Python 구현 ===

<syntaxhighlight lang="python">
import math
import hashlib
from bitarray import bitarray

class BloomFilter:
    """
    기본 블룸 필터 구현
    """
    def __init__(self, n: int, fp_rate: float = 0.01):
        """
        Parameters
        ----------
        n       : 예상 원소 개수
        fp_rate : 허용 거짓 긍정률 (기본값 1%)
        """
        self.n = n
        self.fp_rate = fp_rate

        # 최적 비트 배열 크기 계산
        self.m = self._optimal_m(n, fp_rate)
        # 최적 해시 함수 개수 계산
        self.k = self._optimal_k(self.m, n)

        self.bit_array = bitarray(self.m)
        self.bit_array.setall(0)
        self.count = 0

        print(f"BloomFilter 초기화: m={self.m} bits, k={self.k} hash functions")

    @staticmethod
    def _optimal_m(n: int, fp_rate: float) -> int:
        """최적 비트 배열 크기"""
        m = -(n * math.log(fp_rate)) / (math.log(2) ** 2)
        return int(math.ceil(m))

    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        """최적 해시 함수 개수"""
        k = (m / n) * math.log(2)
        return max(1, int(round(k)))

    def _hash_indices(self, item: str):
        """k개의 해시 인덱스 생성 (double hashing 기법)"""
        # SHA-256으로 두 개의 기본 해시 생성
        h = hashlib.sha256(item.encode('utf-8')).digest()
        h1 = int.from_bytes(h[:8], 'big')
        h2 = int.from_bytes(h[8:16], 'big')

        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item: str):
        """원소 추가"""
        for idx in self._hash_indices(item):
            self.bit_array[idx] = 1
        self.count += 1

    def contains(self, item: str) -> bool:
        """
        원소 포함 여부 조회
        Returns
        -------
        False : 확실히 없음
        True  : 아마도 있음 (거짓 긍정 가능)
        """
        return all(self.bit_array[idx] for idx in self._hash_indices(item))

    def __contains__(self, item: str) -> bool:
        return self.contains(item)

    def estimated_fp_rate(self) -> float:
        """현재 채워진 상태에서의 추정 오탐률"""
        return (1 - math.exp(-self.k * self.count / self.m)) ** self.k

    def fill_ratio(self) -> float:
        """비트 배열에서 1인 비율"""
        return self.bit_array.count(1) / self.m


# === 사용 예시 ===
if __name__ == "__main__":
    bf = BloomFilter(n=1_000_000, fp_rate=0.01)

    # 데이터 삽입
    words = ["apple", "banana", "cherry", "date", "elderberry"]
    for word in words:
        bf.add(word)

    # 조회 테스트
    test_cases = ["apple", "banana", "grape", "mango", "cherry"]
    for word in test_cases:
        result = "아마도 있음" if word in bf else "확실히 없음"
        print(f"  '{word}': {result}")

    print(f"\n현재 추정 오탐률: {bf.estimated_fp_rate():.6%}")
    print(f"비트 배열 충전률: {bf.fill_ratio():.4%}")
</syntaxhighlight>