Min Value: 서로 다른 값의 개수를 추정하는 방법

지난 Linear Counting 글에서는 데이터에 들어 있는 서로 다른 값의 개수를 구하고 추정하는 기본 알고리즘을 살펴보았다. 이번에는 꽤 정확하면서도 메모리를 적게 쓰는 또 다른 확률적 알고리즘으로 서로 다른 값의 개수를 추정해 보자.

Min Value

이 글에서는 단위구간 (0, 1)의 실수만 다룬다. 이 구간에서 고르게 퍼져 있는 수의 집합, 예를 들어 집합 {0.25, 0.5, 0.75}를 생각해 보자. 이웃한 두 수 사이의 거리(그리고 0과 첫 수, 마지막 수와 1 사이의 거리)는 언제나 0.25이다. 이것이 서로 다른 원소의 개수를 세는 데 어떻게 도움이 될까?

단위구간에서 고르게 퍼져 있는 수의 집합이 있고, 이웃한 수 사이의 거리가 0.2라고 하자. 이 집합의 원소는 몇 개일까? 물론 이 집합은 {0.2, 0.4, 0.6, 0.8}이고 카디널리티는 4이다. 입력이 단위구간에서 고르게 퍼져 있는 수이고 이웃한 수 사이의 거리를 알면 원소의 개수를 쉽게 구할 수 있다.

그런데 이웃한 수 사이의 거리는 집합의 가장 작은 원소와 같다. 예를 들어 집합 {0.25, 0.5, 0.75}에서 이웃한 원소 사이의 거리는 0.25이다. 따라서 고르게 퍼져 있는 수의 개수를 구할 때는 가장 작은 원소만 알아내면 된다. 그러면 원소의 개수 p를 간단한 식으로 구할 수 있다.

$$p=\frac{1}{m}-1$$

여기서 m은 그 가장 작은 원소이다.

이번에도 해싱

그런데 입력이 문자열이나 다른 값이어서 단위구간에 고르게 퍼져 있다는 조건을 만족하지 않으면 이것을 어떻게 쓸 수 있을까? 이번에도 오래된 믿음직한 해시 함수를 쓴다. 해시 함수는 임의의 입력에 대해 단위구간의 유리수를 돌려줄 수 있다. 이런 해시 함수는 쉽게 만들 수 있다.

이렇게 하면 데이터에서 유리수를 얻지만, 이 수들이 고르게 퍼지도록 하려면 어떻게 해야 할까? 그렇게 만들 수는 없지만 다른 방법이 있다. 해시 함수는 겉보기에 꽤 “무작위”로 동작한다. “ahoj”, “ahok”, “ahol”처럼 아주 비슷한 문자열에 대해서도 해시 함수는 아마 아주 다른 체크섬을 돌려줄 것이다. 다시 말해 서로 다른 값 1,000개를 단위구간으로 해싱하면, 수의 대부분이 예를 들어 2분의 1보다 작을 가능성은 매우 낮다. 오히려 이 수들은 어느 정도 고르게 퍼져 있을 가능성이 매우 높다. 많은 데이터를 해싱할수록 더 고르게 퍼진다.

이 아이디어에서 간단한 알고리즘이 나온다. 입력 데이터를 훑으면서 각 원소를 단위구간으로 해싱하고 가장 작은 값을 기억해 둔다. 서로 다른 원소의 개수는 앞의 식으로 추정한다. 파이썬 구현은 다음과 같다.

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

함수 unit_interval_hash는 구간 (0, 1]의 부동소수점 수를 돌려준다. 함수 count_unique_using_minimum은 먼저 모든 입력값을 이런 수로 바꾸고, 최솟값을 찾아 1 / minimum - 1을 돌려준다. 데이터에 같은 값이 몇 개 있든 전혀 상관없다는 점에 주목하자. 같은 두 값에 대해 해시 함수는 같은 유리수를 돌려주므로 최솟값에는 아무 영향이 없다. 그래서 이 알고리즘으로 서로 다른 원소의 개수를 셀 수 있다.

결과는 어떨까? (각 줄은 추정한 카디널리티이고, 실제 카디널리티는 10,000이다.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

음, 별로이다. 알고리즘은 서로 다른 ID 묶음 10개를 처리했고, 각 묶음에는 언제나 서로 다른 값이 1만 개 있었다. 그런데 계산한 추정값은 대부분 크게 빗나갔다. 이 값들의 평균을 내면 18,352가 되는데, 여전히 많이 빗나간다. 하지만 메모리 사용량을 보자. 메모리 사용량이 일정하다! 최솟값을 찾으려면 현재 최솟값을 저장할 변수 하나만 메모리에 두면 된다. 그러니까 추정은 형편없지만 비용은 거의 들지 않는다.

개선하기

이 알고리즘은 무엇보다 불안정하다. 한 번은 꽤 좋은 추정값(9362)을 돌려주고, 다음에는 완전히 빗나간 추정값(65536)을 돌려준다. 어떻게 하면 될까? 입력 데이터를 여러 부분으로 나누어 부분마다 서로 다른 원소의 개수를 구한 다음, 마지막에 모두 평균을 내면 된다. ID의 첫 글자로 나눌 수 있다. 즉 글자 “a”로 시작하는 ID, 글자 “b”로 시작하는 ID 등으로 나누어 서로 다른 값의 개수를 따로 센다. 코드는 다음과 같다.

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

바뀐 곳은 함수 count_unique_using_minimum이다. 변수 min_values에 그룹마다 최솟값을 저장한다. 마지막에 모든 최솟값을 더하고 저장된 값의 개수로 나누어 평균 최솟값을 구한다. 식 1/average_minimum으로 각 그룹에 들어 있는 서로 다른 값의 평균 개수를 구하고, 이 값에 그룹의 개수를 곱하면 주어진 데이터에 들어 있는 서로 다른 값의 개수를 추정할 수 있다. 이렇게 고친 방법은 얼마나 잘 동작할까?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

음, 아직 좋지는 않지만 분명히 나아졌다. 알고리즘이 더 안정적이다. 그룹을 첫 글자가 아니라 예를 들어 ID의 첫 두 글자로 만들도록 함수를 고쳐 볼 수 있다.

first_char = str(item)[0:2] # ToDo: choose better name for variable

그러면 결과는 다음과 같다.

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

이제 꽤 쓸 만하지 않은가? 서로 다른 값 10만 개, 첫 두 글자, n = 24로 시험해 보면 다음 결과를 얻는다.

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

제법 괜찮다. 그래도 걱정할 것 없다. 더 좋은 알고리즘이 아직 남아 있다.

메모리 사용량은 어떨까? 그룹마다 최솟값만 저장하면 되고 그 밖에는 필요 없다. ID가 16진수 형식이면 최솟값을 많아야 16^x개 기억하면 된다. 여기서 x는 그룹의 키를 만드는 글자 수이다. 최솟값 하나는 유리수 하나, 즉 double이나 float 같은 자료형 하나이다.

끝으로 한 가지 덧붙이자. 입력을 여러 그룹으로 나눌 수 있었던 것은 입력인 ID가 무작위 문자열처럼 동작했기 때문이다. 입력이 무작위 문자열이 아니라 어떤 형식을 갖춘 데이터라면 다른 방법으로 나누어야 한다. 예를 들어 모든 ID가 접두사 userid-로 시작하면 첫 글자로 그룹을 나누는 방법은 당연히 잘 통하지 않는다.