Flajolet-Martin

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

문제 상황

크기가 N인 집합에 속한 원소들만 담은 스트림이 있다고 합시다. 이 스트림에서 서로 다른 원소들의 개수를 구하려면 집합을 만들어 스트림의 모든 아이템을 집합에 넣으면 됩니다. 집합은 동일한 아이템을 원소로 가지지 않기 때문에 이를 통해 쉽게 찾을 수 있습니다.

하지만 생성해야 할 집합의 크기가 너무 커져 메모리에 올릴 수 없는 정도라면 어떻게 찾아야 할까요?

Flajolet-Martin(ver. 1)

Flajolet-Martin 알고리즘을 통해 이를 대략적으로 구할 수 있습니다. 이 알고리즘을 위해 아이템을 \(log_2 N\)의 bit로 변환하는 해시 함수(h)를 준비합니다. 그리고 임의의 아이템 a의 해시 값 h(a)에서 least significant set bit의 위치를 r(a)라고 합시다. Least significant set bit은 비트의 가장 우측을 0으로 기준을 잡고 1이 처음 나온 위치입니다. 예시를 들어보면 아래의 표와 같습니다.

 

h(a)	r(a)
0001	0
0100	2
0110	1
1000	3

 

스트림으로 들어오는 아이템 a에 대해 r(a)의 최댓값(R)을 기록합니다. 최댓값을 통해 서로 다른 아이템의 개수를 \(2^R\)이라 유추하는 것이 flajolet-martin 알고리즘입니다.

이 알고리즘은 우연히 나오는 큰 결과 값에 약하다는 단점이 있습니다. 영어 소문자를 담은 집합의 원소들만 있는 스트림에 다음과 같이 들어왔다고 합시다.

 

스트림에 들어온 순서	아이템	h(a)	r(a)
1	a	01101	0
2	c	10110	1
3	b	01010	1
4	f	10000	4
5	a	01101	0
6	f	10000	4

 

이와 같은 상황에서 R 값은 4이므로 서로 다른 아이템의 수는 16이라 추측하게 됩니다. 실제로 들어온 서로 다른 아이템의 수는 a, b, c, f로 4가지 있는 사실과 너무 큰 차이를 나타냅니다.

Flajolet-Martin(ver. 2)

이 문제를 완화시키기 위해 길이가 \(log_2 N\)인 비트 배열(B)을 사용합니다. 그리고 스트림으로 들어오는 아이템 a에 대해 B[r(a)] 값을 1로 설정합니다. 최종적으로 서로 다른 아이템의 수는 \(2^R\) / \(\phi\)로 계산합니다. \(\phi\)의 값은 0.77351...로 이 값에 대한 설명은 논문에 나와있다고 합니다.

여기서 차이점은 R의 내용입니다. 이전에는 r(a)의 최댓값이었지만, 여기서의 R은 비트 배열의 least significant unset bit입니다. 즉, 우측부터 볼 때 0이 처음 나오는 위치를 의미합니다.

이를 통해 위의 예시를 다시 살펴봅시다. 먼저 길이가 5인 비트 배열을 만들고, 0으로 초기화합니다. 그 후로 스트림으로 들어오는 a 값에 대해 B[r(a)] 값을 1로 갱신을 하면 아래와 같습니다.

 

1

0

0

1

1

 

여기서 주의해야 할 점은, 비트 배열의 인덱스의 시작은 우측이라는 점입니다. 그렇기에 위의 비트 배열의 인덱스를 나열하면 4, 3, 2, 1, 0입니다.

R = 2이므로 이를 계산하면 4 / 0.77351 \(\approx\) 5.171로 ver. 1 때보다 정확한 값을 얻을 수 있습니다.