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

== 핵심 원리 ==

=== 구성 요소 ===

블룸 필터는 두 가지 핵심 구성요소로 이루어진다.

==== 비트 배열 (Bit Array) ====

크기 '''m'''인 비트 배열(또는 비트 벡터)을 유지한다. 초기에는 모든 비트가 '''0'''으로 설정된다.

<pre>
초기 상태 (m = 10):
인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][0][0][0][0][0][0][0][0][0]
</pre>

==== 해시 함수들 (Hash Functions) ====

'''k'''개의 서로 다른(독립적인) 해시 함수들을 사용한다. 각 해시 함수는 임의의 원소를 입력으로 받아 {0, 1, ..., m-1} 범위의 인덱스를 반환한다. 이 해시 함수들은:
* 서로 독립적이어야 한다.
* 출력이 비트 배열 전체에 균일하게 분포해야 한다.
* 빠르게 계산될 수 있어야 한다.

실제로는 [[MurmurHash]], [[FNV Hash]], [[xxHash]] 같은 비암호화 해시 함수가 자주 쓰이며, 하나의 해시 함수에 서로 다른 시드(seed)를 주어 k개를 흉내내는 기법도 사용된다.

=== 동작 원리 ===

==== 삽입 (Insert) ====

원소 x를 블룸 필터에 추가하려면:
# k개의 해시 함수 h₁, h₂, ..., hₖ 각각에 x를 입력한다.
# 각 해시 함수가 반환하는 인덱스 h₁(x), h₂(x), ..., hₖ(x)에 해당하는 비트를 모두 '''1'''로 설정한다.

<pre>
예시: m=10, k=3, 원소 "apple" 삽입
h1("apple") = 2  →  비트[2] = 1
h2("apple") = 5  →  비트[5] = 1
h3("apple") = 8  →  비트[8] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][0][1][0][0][1][0][0][1][0]
</pre>

이어서 "banana"를 삽입하면:

<pre>
h1("banana") = 1  →  비트[1] = 1
h2("banana") = 5  →  비트[5] = 1  (이미 1)
h3("banana") = 7  →  비트[7] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][1][1][0][0][1][0][1][1][0]
</pre>

==== 조회 (Query / Lookup) ====

원소 y가 집합에 있는지 확인하려면:
# k개의 해시 함수 각각에 y를 입력한다.
# h₁(y), h₂(y), ..., hₖ(y)에 해당하는 비트를 모두 확인한다.
# '''하나라도 0이면''' → "확실히 없다(Definitely Not)" 반환.
# '''모두 1이면''' → "아마도 있다(Possibly Yes)" 반환.

<pre>
"apple" 조회:
h1("apple") = 2  →  비트[2] = 1 ✓
h2("apple") = 5  →  비트[5] = 1 ✓
h3("apple") = 8  →  비트[8] = 1 ✓
→  결과: "아마도 있다" (실제로 삽입했으므로 정확)

"cherry" 조회 (삽입 안 함):
h1("cherry") = 1  →  비트[1] = 1 ✓
h2("cherry") = 5  →  비트[5] = 1 ✓
h3("cherry") = 9  →  비트[9] = 0 ✗
→  결과: "확실히 없다" (정확)

"grape" 조회 (삽입 안 함):
h1("grape") = 1  →  비트[1] = 1 ✓
h2("grape") = 5  →  비트[5] = 1 ✓
h3("grape") = 7  →  비트[7] = 1 ✓
→  결과: "아마도 있다" (거짓 긍정! 실제로는 없음)
</pre>

"grape"의 경우처럼, 우연히 다른 원소들에 의해 해당 비트들이 모두 1이 되어 있으면 '''거짓 긍정(False Positive)'''이 발생한다. 이것이 블룸 필터의 본질적인 한계이자, 공간을 아끼기 위해 치르는 대가다.

==== 삭제 불가 ====

기본 블룸 필터는 '''원소를 삭제할 수 없다'''. 만약 특정 원소에 해당하는 비트를 0으로 되돌리면, 같은 비트를 공유하던 다른 원소의 정보도 손상되기 때문이다. 예를 들어 위 예시에서 비트[5]는 "apple"과 "banana" 둘 다 사용하고 있는데, "apple"을 삭제하겠다고 비트[5]를 0으로 만들면 "banana"도 조회되지 않게 된다.

이 문제를 해결한 변형이 [[#카운팅 블룸 필터(Counting Bloom Filter)|카운팅 블룸 필터]]다.

=== 거짓 긍정률 (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가 필요한 것과 비교하면, 블룸 필터의 공간 절약 효과가 극적임을 알 수 있다.