LogLog：異なる値の個数を推定する方法

Linear Counting と Min Value に続いて、いよいよデータに含まれる異なる値の個数を推定する確率的アルゴリズムの中でもほぼ最高のもの、LogLog を紹介します。これよりよいのは、LogLog をもとにした弟分の HyperLogLog だけですが、それは次回にしましょう。

問題を確認しておきます。入力はデータの集まり、つまり多重集合で、例えば ID の配列やジェネレータです。この配列には同じ値が何回か含まれていて、配列に含まれる異なる値の個数を求めたいとします。この個数をカーディナリティといいます。カーディナリティは非常に大きいと想定します。そうでなければ、ふつうのアルゴリズムで数えれば済むからです。

LogLog アルゴリズムの考え方

2進数のベクトル（ビット列）の集まりを考えます。難しく考える必要はありません。例えば、0001011001001100 は長さ16のビット列です。長さ32のビット列が全部で100万個あり、どれも完全にランダムに生成したものだとします。0で終わるビット列はいくつあるでしょうか。

もちろん正確にはわかりませんが、本当にランダムに生成したのなら、ほぼ半分、つまり50万個が0で終わるはずです。00で終わるものはいくつでしょうか。4分の1です。000で終わるものは8分の1です。以下同様です。これを表にすると、おおよそ次のようになります。

ビット列の形      全体に占める割合
...xxxxxx0        50%
...xxxxx00        25%
...xxxx000        12.5%
...xxx0000        6.25%
     ...          ...

長さ d の接尾辞（接尾辞とは、ある文字列の末尾の部分になっている文字列のことで、接頭辞の反対です）について考えると、その接尾辞で終わるビット列は v 個見つかると期待できます。v の値は次の式で求められます。

$v = \frac{1}{2^{d}} \cdot N$

ここで、N は集まりに含まれるビット列全体の個数です。長さ3の接尾辞（例えば …010）は、1/2^3 N = 1/8 N 個、つまり全体の12.5%のビット列に現れるはずです。

ここで、ちょっと頭をひねってみましょう。異なるビット列1,024個からなる多重集合を考えます。接尾辞0000000000（0が10個）で終わるビット列はいくつあるはずでしょうか。式に代入すると、次のようになります。

$v = \frac{1}{2^{10}} \cdot 1024 = \frac{1}{1024} \cdot 1024 = 1$

なんと1個です。約1,000個のランダムに生成したビット列の中に、0が10個続いて終わるものが1個あるはずなのです。では、これを異なる要素の個数の推定にどう使えばよいでしょうか。逆向きに考えればよいのです。入力のビット列をすべて調べて、0が10個続いて終わるビット列がただ1つだけあるとわかったらどうでしょうか。それなら、集まりには1,024個のビット列があったと推定できます。

一般化してアルゴリズムを組み立てる

目標は、ただ1つのビット列にだけ含まれる接尾辞で、しかもできるだけ短いものを見つけることです。しかし、これは非常に難しいことです。そのようなビット列を本当に見つけるには、すべての接尾辞を保存しておく必要があり、それではメモリを使いすぎてしまいます。そこで代わりに、ビット列の末尾に続く0の列のうち、最も長いものを探すことにします。

具体的には、すべてのビット列を順に見ていき、それぞれの末尾にある0の個数を数え、その最大値を1つの変数に保持しておきます。すべてのビット列を見終わると、0だけからなる接尾辞のうち最も長いものの長さがわかります。この長さを文字 d で表します。ここで、さきほどの式を変形して変数 N について解きます。N をアルゴリズムの入力ではなく出力にするためです。このとき、そのようなビット列はただ1つ見つかる、つまり v=1 が成り立つと期待するので、v には1を代入します。

$\begin{array}{rcl} v & = & \frac{N}{2^{d}} \\ v \cdot 2^{d} & = & N \\ 2^{d} & = & N \end{array}$

したがって、末尾の0の列のうち最も長いものの長さ d がわかれば、カーディナリティは式 N=2^d で推定できます。

ランダムなビット列をどう得るか

ランダムなビット列ならこのアルゴリズムで推定できますが、実際のデータにはどう適用すればよいでしょうか。いつものように、ここでも適当なハッシュ関数を使います。入力が例えば ID（文字列）のデータなら、まずそれをハッシュします。n ビットのハッシュ関数の出力は n 個のビットで、実用上はランダムに生成したビット列のように見えます。

これでアルゴリズムを書けます。

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

関数 trailing_zeroes は、数の末尾にある0の個数を返します。どうやって数えているかは、コードを読めばわかるでしょう。この関数の精度はどうでしょうか。異なる要素を10万個含む集合に対して、関数は推定値524,288を返しました。

うーん……。

あまりよくありません。でも大丈夫です。前回の Min Value とまったく同じ方法で、アルゴリズムを改良してみましょう。入力データを互いに素ないくつかのグループに分け、グループごとに末尾の0の列の最大の長さを求め、最後にその長さの平均を求めて、異なる値の個数の推定に使います。

例えば、各ビット列の最後の2ビットを、そのビット列が属するグループの番号にすると決めます。次の6個のビット列

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

は、末尾の2ビットによって4つのグループに分けられます。

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

次に、各ビット列の末尾の0の列のうち最も長いものの長さを求めます。ただし、グループの番号に使ったビットは飛ばします。0の「接尾辞」を緑色で示します。

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

最後に書いてあるのが、各グループで最も長い0の接尾辞の長さです。これらの長さの相加平均を求めると2.75になります。この値を式に代入すると、次のようになります。

$2^{2.75} ≒ 6.727$

これで、各グループに含まれる異なる要素の個数の平均が得られます。もちろん実際とはまったく合いませんが、気にすることはありません。小さな集合に対しては、LogLog アルゴリズムはひどい結果を出すのです。

集合全体のカーディナリティを推定するには、この値にグループの個数をかけます。6.727 · 4 = 26.908 です。アルゴリズムの推定では、集まりに含まれる異なる値はおよそ27個です。実際は6個なので大きく外れていますが、今はまったく問題ありません。

アルゴリズムの実装

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

パラメータ k は、何ビットをグループ（バケット）の番号として使うかを決めます。このパラメータがアルゴリズムの精度を決め、k が大きいほど精度が上がります。変数 bucket_index にはグループの番号が入ります。等号の右辺の不思議な式は、どういうしくみなのでしょうか。

変数 num_buckets はグループの個数で、常に2の累乗です。例えば k = 3 なら num_buckets=8 です。8は2進法で1000です。1を引くと7になり、これは0111です。num_buckets から1を引くと、常に末尾に1が k 個並び、その前がすべて0の数になります。次に論理積（演算子 &）をとります。ビット列 1110110010100101 なら、この演算は次のようになります。

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

この不思議な式の目的は、先頭がすべて0で、最後の k ビットがハッシュ値 h と同じ数を得ることです。

次に bucket_hash を求めます。これは、もとのハッシュ値全体を k ビット右にずらして、最後の k ビットを取り除いたものです。右シフトでは、数のすべてのビットが k ビットずつ右にずれ、左側は0で埋められます（1ビットの右シフトは、数を2で割って余りを切り捨てるのと同じです）。ビット列 1110110010100101 を3ビット右シフトすると、0001110110010100 が得られます。このビット列が変数 bucket_hash に入ります。

次に、このビット列の末尾にある0の個数を数えます。この値が、配列 max_zeroes の添字 bucket_index の位置に保存されている現在の最大値より大きければ、値を書きかえます。

最後に、すべてのグループについて末尾の0の個数の平均を求め、各グループに含まれる異なる要素の個数の平均（2 ** average_max_zeros）を求めます。グループは全部で num_buckets 個あるので、この値にグループの個数をかければ、異なる要素の個数の最終的な推定値が得られます。これで完成です。異なる値を250,000個含むいくつかのデータについて、k=10 としたときの結果は次のとおりです。

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

残念ながら、まだ外れています。でも、かなり近づいているので安心してください。結果がどれも正しい値より大きいことに注目しましょう。アルゴリズムの途中でさまざまな誤差が積み重なるので、推定値は正しい値よりはっきり大きくなるのです。ただし、この誤差はかなり一定していて、どれくらいの誤差が生じたかを見積もれます。推定値に補正定数0.79402をかけると、結果は大幅によくなります。

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

カーディナリティが100万の多重集合でも試してみました。結果は次のとおりです。

結果                  誤差
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

上出来です。誤差は2.5%未満で、十分な性能です。これが LogLog アルゴリズムです。補正定数を含めた最終的な実装は次のとおりです。

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

このアルゴリズムをどう改良すれば、名高い最高のアルゴリズム HyperLogLog になるのかは、次回説明します。ここでは、このアルゴリズムがどれだけメモリを使うかを見てみましょう。

メモリの使用量

このアルゴリズムは、使うメモリの点で非常に効率的です。覚えておく必要があるのは、最大値を保持する配列だけです。この配列の長さは k の値、つまりビット列のうちグループの番号として使うビットの個数で決まります。k が与えられると、グループは全部で 2^k 個あるので、最大値の配列の長さは 2^k です。この値を、実装では num_buckets とよんでいました。

配列の1つのセルはどれくらいの大きさが必要でしょうか。セルには0の接尾辞の長さを保存します。先にいっておくと、64ビットのハッシュ値があれば、考えうる世界中のどんな多重集合にもおそらく十分です。そのため、この配列には0（すべて1のビット列）から64（すべて0のビット列）までの数を保存できる必要があります。さらに、k が常に0より大きいと仮定すれば、保存するのは0から63までの数だけで済みます。それには6ビットあれば足ります。2⁶ = 64 だからです。

つまり、1つのセルの大きさが6ビットの「配列」があれば済みます。さらに、k=10 とすれば、数億のオーダーまでのカーディナリティをかなりよく推定できます。このように設定したアルゴリズムは、大きさ 2¹⁰ = 1024 の配列をつくり、各セルは6ビットを使います。この配列全体で6,144ビット、つまり768バイトです。1キロバイトにも満たない大きさです。

必要なのはこれだけです。

ほかに保存しておくものはありません。計算したハッシュ値はすぐに捨ててよく、ビット列の末尾の0の個数さえわかれば済みます。

もっと大きいハッシュ関数、例えば128ビットを返すハッシュ関数を使っても、メモリの使用量はあまり変わらないことに注意しましょう。保存する必要があるのは0から127までの数で、7ビットあれば足ります。メモリの使用量を主に決めるのは、パラメータ k、つまりグループの個数です。

LogLog が特に役に立つのは、カーディナリティが非常に大きい多重集合を数える必要があるときです。上の簡単な例でもわかるように、LogLog はカーディナリティの小さい多重集合をあまりうまく扱えません。ただし、これも補えます。例えば、多重集合のカーディナリティが小さいとわかったら、別のアルゴリズム、例えば前に説明した Linear Counting で推定すればよいのです。これについても次回説明します。

参考文献：

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation（LogLog のコードはほぼここから借りました）

章: Linear Counting：異なる値の個数を推定する方法, Min Value：異なる値の個数を推定する方法, LogLog：異なる値の個数を推定する方法, HyperLogLog：異なる値の個数を高い精度で推定する方法

« 前へ: Min Value：異なる値の個数を推定する方法

次へ: HyperLogLog：異なる値の個数を高い精度で推定する方法 »