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

== 구현 ==

=== 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>

=== Java 구현 ===

<syntaxhighlight lang="java">
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter {
    private final int m;          // 비트 배열 크기
    private final int k;          // 해시 함수 개수
    private final BitSet bitSet;
    private int count;

    public BloomFilter(int n, double fpRate) {
        this.m = optimalM(n, fpRate);
        this.k = optimalK(m, n);
        this.bitSet = new BitSet(m);
        this.count = 0;
        System.out.printf("BloomFilter: m=%d bits, k=%d hash functions%n", m, k);
    }

    private static int optimalM(int n, double fpRate) {
        return (int) Math.ceil(-(n * Math.log(fpRate)) / (Math.log(2) * Math.log(2)));
    }

    private static int optimalK(int m, int n) {
        return Math.max(1, (int) Math.round(((double) m / n) * Math.log(2)));
    }

    private int[] hashIndices(String item) {
        int[] indices = new int[k];
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] digest = md.digest(item.getBytes(StandardCharsets.UTF_8));

            long h1 = bytesToLong(digest, 0);
            long h2 = bytesToLong(digest, 8);

            for (int i = 0; i < k; i++) {
                indices[i] = (int) Math.floorMod(h1 + (long) i * h2, m);
            }
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
        return indices;
    }

    private long bytesToLong(byte[] bytes, int offset) {
        long val = 0;
        for (int i = 0; i < 8; i++) {
            val = (val << 8) | (bytes[offset + i] & 0xFF);
        }
        return val;
    }

    public void add(String item) {
        for (int idx : hashIndices(item)) {
            bitSet.set(idx);
        }
        count++;
    }

    public boolean mightContain(String item) {
        for (int idx : hashIndices(item)) {
            if (!bitSet.get(idx)) return false;
        }
        return true;
    }

    public double estimatedFpRate() {
        return Math.pow(1 - Math.exp(-(double) k * count / m), k);
    }

    // 사용 예시
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(1_000_000, 0.01);

        bf.add("hello");
        bf.add("world");
        bf.add("java");

        System.out.println(bf.mightContain("hello")); // true
        System.out.println(bf.mightContain("python")); // false (높은 확률로)
        System.out.printf("추정 오탐률: %.6f%%%n", bf.estimatedFpRate() * 100);
    }
}
</syntaxhighlight>

=== JavaScript / TypeScript 구현 ===

<syntaxhighlight lang="typescript">
import * as crypto from 'crypto';

class BloomFilter {
  private readonly m: number;
  private readonly k: number;
  private readonly bitArray: Uint8Array;
  private count: number = 0;

  constructor(n: number, fpRate: number = 0.01) {
    this.m = BloomFilter.optimalM(n, fpRate);
    this.k = BloomFilter.optimalK(this.m, n);
    this.bitArray = new Uint8Array(Math.ceil(this.m / 8));
    console.log(`BloomFilter: m=${this.m} bits, k=${this.k} hash functions`);
  }

  private static optimalM(n: number, fpRate: number): number {
    return Math.ceil(-(n * Math.log(fpRate)) / (Math.LN2 ** 2));
  }

  private static optimalK(m: number, n: number): number {
    return Math.max(1, Math.round((m / n) * Math.LN2));
  }

  private getBit(index: number): boolean {
    return (this.bitArray[index >> 3] & (1 << (index & 7))) !== 0;
  }

  private setBit(index: number): void {
    this.bitArray[index >> 3] |= (1 << (index & 7));
  }

  private *hashIndices(item: string): Generator<number> {
    const hash = crypto.createHash('sha256').update(item, 'utf8').digest();
    const h1 = hash.readBigUInt64BE(0);
    const h2 = hash.readBigUInt64BE(8);
    for (let i = 0; i < this.k; i++) {
      yield Number((h1 + BigInt(i) * h2) % BigInt(this.m));
    }
  }

  add(item: string): void {
    for (const idx of this.hashIndices(item)) {
      this.setBit(idx);
    }
    this.count++;
  }

  has(item: string): boolean {
    for (const idx of this.hashIndices(item)) {
      if (!this.getBit(idx)) return false;
    }
    return true;
  }

  estimatedFpRate(): number {
    return Math.pow(1 - Math.exp(-this.k * this.count / this.m), this.k);
  }
}

// 사용 예시
const bf = new BloomFilter(1_000_000, 0.01);
bf.add("TypeScript");
bf.add("BloomFilter");
console.log(bf.has("TypeScript"));    // true
console.log(bf.has("JavaScript"));   // 아마도 false
console.log(`오탐률: ${(bf.estimatedFpRate() * 100).toFixed(6)}%`);
</syntaxhighlight>