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

== 블룸 필터 관련 이론 ==

=== 정보 이론적 하한 ===

n개의 원소로 이루어진 집합을 u개의 가능한 원소 공간에서 표현하되, 거짓 긍정률 ε를 허용할 때, 필요한 최소 비트 수는 정보 이론적으로:

<math>n × log₂(1/ε) bits</math>

블룸 필터의 최적 m은 이 값의 약 1/ln(2) ≈ 1.44배다. 즉, 블룸 필터는 이론적 하한 대비 약 44% 더 많은 공간을 사용한다. 이 비효율은 블룸 필터가 비적응적(non-adaptive) 구조이기 때문이며, 최적 부호화를 사용하는 이론적 구조로는 하한에 도달할 수 있지만 실제 구현은 훨씬 복잡해진다.

=== 로딩 팩터(Loading Factor)와 오탐률의 관계 ===

비트 배열에서 1인 비트의 비율을 '''로딩 팩터(f)'''라 할 때:

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

최적 k에서 <math>f ≈ 0.5</math>, 즉 절반의 비트가 1로 설정된다. 이는 직관적으로도 납득 가능하다: 비트가 너무 드물면(낮은 f) 해시 충돌이 적어 좋지만 공간 낭비, 너무 촘촘하면(높은 f) 거짓 긍정 폭증. 최적은 50% 충전이다.

=== 독립성 가정과 현실 ===

블룸 필터의 이론적 오탐률 계산은 '''해시 함수들이 완전히 독립적이고 균일하게 분포'''한다고 가정한다. 실제 해시 함수들은 이 조건을 완벽히 만족하지 않으므로, 실제 오탐률이 이론값과 약간 다를 수 있다. 그러나 좋은 품질의 해시 함수를 사용하면 이 차이는 무시할 만한 수준이다.