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

=== 거짓 긍정률 (False Positive Rate) 수학적 분석 ===

==== 단일 비트가 0일 확률 ====

크기 m인 비트 배열에 k개의 해시 함수로 n개의 원소를 삽입했을 때, 특정 비트가 여전히 0일 확률을 계산한다.

하나의 해시 함수가 특정 비트를 설정하지 않을 확률 = <math>(1 - 1/m)</math>

k개의 해시 함수가 모두 해당 비트를 설정하지 않을 확률 = <math>(1 - 1/m)^k</math>

n개의 원소를 삽입한 후에도 해당 비트가 0일 확률:

<math>P(bit = 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)</math>

==== 거짓 긍정률 계산 ====

새 원소를 조회할 때, <math>k</math>개의 비트가 모두 1일 확률 (즉 거짓 긍정률 ε):

<math>ε ≈ (1 - e^(-kn/m))^k</math>

이 식에서 중요한 사실을 알 수 있다.
* '''m이 클수록''' (비트 배열이 클수록) → ε 감소 (오탐 줄어듦)
* '''n이 클수록''' (원소 수가 많을수록) → ε 증가 (오탐 늘어남)
* '''k가 너무 작으면''' → 구별력이 없어짐 → ε 증가
* '''k가 너무 크면''' → 비트가 빠르게 포화됨 → ε 증가
* '''k에 최적값이 존재함'''

==== 최적 해시 함수 개수 ====

<math>ε</math>를 최소화하는 최적의 <math>k</math> 값은 미분을 통해 구할 수 있다:

<math>k_opt = (m/n) × ln(2) ≈ 0.693 × (m/n)</math>

이 최적 <math>k</math>를 사용하면 거짓 긍정률이:

<math>ε_opt ≈ (1/2)^k = 0.5^k = (0.6185)^(m/n)</math>

==== 비트 배열 크기 설계 ====

원하는 오탐률 <math>ε</math>와 예상 원소 수 <math>n</math>이 주어졌을 때 필요한 최소 비트 배열 크기 m:

<math>m = -(n × ln(ε)) / (ln(2))² ≈ -(n × ln(ε)) / 0.4805</math>

'''실용적인 수치 예시:'''

{| class="wikitable" style="text-align:center;"
|-
! 원소 수 (n) !! 오탐률 (ε) !! 비트 배열 크기 (m) !! 해시 함수 수 (k) !! 원소당 비트 수
|-
| 1,000,000 || 1% || 9,585,060 bit (~1.14 MB) || 7 || 약 9.58 bit
|-
| 1,000,000 || 0.1% || 14,377,590 bit (~1.71 MB) || 10 || 약 14.38 bit
|-
| 1,000,000 || 0.01% || 19,170,120 bit (~2.28 MB) || 13 || 약 19.17 bit
|-
| 1,000,000 || 0.001% || 23,962,650 bit (~2.85 MB) || 17 || 약 23.96 bit
|-
| 10,000,000 || 1% || 95,850,584 bit (~11.4 MB) || 7 || 약 9.58 bit
|}

일반적인 해시 테이블에서 백만 개의 문자열을 저장하면 수백 MB가 필요한 것과 비교하면, 블룸 필터의 공간 절약 효과가 극적임을 알 수 있다.