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 はその最小の要素です。

またハッシュを使う

しかし、入力が文字列などの値で、単位区間に等間隔に並ぶという条件を満たさない場合は、これをどう使えばよいでしょうか。ここでもまた、おなじみのハッシュ関数を使います。任意の入力に対して単位区間の有理数を返すハッシュ関数は、簡単につくれます。

こうしてデータから有理数が得られますが、それらの数を等間隔に並ばせるにはどうすればよいでしょうか。それはさすがに無理ですが、別の方法で補えます。ハッシュ関数は、こちらから見るとかなり「ランダム」にふるまいます。例えば、「hello」、「hellp」、「hellq」のようによく似た語に対しても、ハッシュ関数はおそらく大きく異なるチェックサムを返します。言いかえると、1,000個の異なる値を単位区間にハッシュしたとき、例えば大部分の数が2分の1より小さくなることはまずありません。むしろ、これらの数はほぼ均等に分布する可能性が非常に高いのです。ハッシュするデータが多いほど、分布はより均等になります。

この考え方から、簡単なアルゴリズムが得られます。入力データを順に見ていき、各要素を単位区間にハッシュして、最小の値を覚えておきます。異なる要素の個数は、さきほどの式で推定します。Python での実装は次のとおりです。

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 を返します。データに同じ値がいくつ含まれていても、まったく関係がないことに注目しましょう。同じ値が2つあれば、ハッシュ関数はどちらにも同じ有理数を返すので、最小値には影響しません。そのため、このアルゴリズムで数えられるのは異なる要素の個数です。

結果はどうなるでしょうか（各行が推定した要素の個数で、正しい値は10,000です）。

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

あまりよくありません。アルゴリズムは、異なる値がそれぞれ1万個ある10通りの ID の集まりを処理しました。求めた推定値は、ほとんどが大きく外れています。平均をとると18,352になり、やはりかなり外れています。一方で、メモリの使用量を考えてみてください。一定なのです。最小値を求めるには、現在の最小値を入れておく変数を1つだけメモリに保持すれば済みます。つまり、推定はひどいものの、コストはほとんどかかりません。

改良

このアルゴリズムの最大の問題は、不安定なことです。あるときはかなりよい推定値（9,362）を返し、別のときはまったく外れた推定値（65,536）を返します。どうすればよいでしょうか。入力データをいくつかの部分に分け、それぞれの部分について異なる要素の個数を求め、最後にすべてを平均すれば改善できます。分け方は、例えば 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

まだよいとはいえませんが、確実に改善しています。アルゴリズムは前より安定しています。次に、グループを最初の1文字ではなく、例えば ID の最初の2文字で分けるように関数を変えてみましょう。

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

結果は次のようになります。

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

これなら悪くありません。さらに、異なる値を10万個、最初の2文字、n = 24 として試すと、次の結果になります。

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

なかなかの結果です。とはいえ、もっとよいアルゴリズムもあるので安心してください。

メモリの使用量はどうでしょうか。保持する必要があるのはグループごとの最小値だけです。ID が16進数の形式なら、覚えておく最小値は最大で 16^x 個です。ここで x は、グループのキーをつくるのに使う文字の個数です。最小値1つは有理数1つ、つまり double や float などの型の値です。

最後に注意を1つ。入力をいくつかのグループに分けられたのは、入力の ID がランダムな文字列のようにふるまったからです。入力がランダムな文字列ではなく、決まった形式のデータであれば、分け方を変える必要があります。例えば、どの ID も接頭辞 userid- で始まるなら、最初の1文字でグループに分ける方法はうまくいかないでしょう。