多重集合に含まれる異なる値の個数を推定するアルゴリズムのシリーズは、最先端のアルゴリズム HyperLogLog に進みます。ただし、このアルゴリズムの背後にある考え方はすべて、以前に説明した LogLog にもとづいています。読み進める前に、LogLog をよく理解しておいてください。

LogLog アルゴリズムには、大きな問題が2つありました。

外れ値

LogLog の推定値は、外れ値、つまりほかの値から大きく離れた値の影響を非常に受けやすいという弱点があります。よくあるのは、各グループの0の接尾辞の最大の長さがほとんど同じ、例えば12から15の間にあるのに、突然1つだけ長さ27の0の接尾辞が現れる場合です。この大きな違いが、異なる値の個数の推定値を狂わせます。ふつうの相加平均では、これにうまく対処できないからです。基本的には、ごく一部の経営者や役員の高い給料が、国全体の平均賃金を押し上げるのと同じしくみです。

アルゴリズムの考案者は、最初は外れ値を取り除き、最大値のうち大きいほうからいくつかを平均に入れないことで対処しようとしましたが、あまりよい方法ではありませんでした。のちに別の方法を試しました。相加平均の代わりに調和平均を使ったのです。調和平均は、平均から大きく離れた値があるときに、はるかによい性質をもちます。

カーディナリティが小さいときの非常に悪い結果

LogLog は、小さな多重集合のカーディナリティを推定させると、ひどい結果を出します。多重集合に異なる要素がほんの少ししかないと、LogLog はとんでもなく大きな推定値を返します。考案者はこれを巧みに解決しました。入力がカーディナリティの小さい多重集合の場合は、LogLog アルゴリズムを使わずに、まったく別のアルゴリズム、つまりおなじみの Linear Counting を使うのです。しかし、カーディナリティがわからないのに、入力の多重集合のカーディナリティが小さいことをどうやって知ればよいのでしょうか。

まず LogLog に異なる要素の個数を推定させ、その推定値が比較的小さいとわかったら、その推定値を捨てて Linear Counting で計算し直します。Linear Counting のしくみを簡単に復習しましょう。最初に、あらかじめ決めた大きさ（ふつうは2の累乗）の、すべて0の（ビット）配列を確保します。多重集合のすべての要素を順に見ていき、そのハッシュ値を計算して、0から配列の長さ引く1までの整数 i に変換します。そして、配列の添字 i の位置に1を保存します。最後に、配列に含まれる0と1の個数を数え、簡単な式でカーディナリティを推定します。

しかし、LogLog アルゴリズムは、計算したハッシュ値を「保存」するビット配列を使いません。代わりに、接尾辞の最大の長さを保持する配列を使います。この配列は、例えば次のようになります。

[2, 5, 9, 0, 5, 4, 4, 0]

各数は、計算したハッシュ値の各グループで、0の接尾辞の最大の長さを表します。すると、i 番目の位置の値が0でないことは、多重集合の値の中に、（3ビットの）ハッシュ値が i に等しい要素があることを必ず意味します。言いかえると、0はそのままにして、正の数をすべて1に変えれば、この配列を Linear Counting 用のビット配列に変換できます。上の配列からは、次のビット配列が得られます。

[1, 1, 1, 0, 1, 1, 1, 0]

これで、Linear Counting アルゴリズムを適用してカーディナリティを推定できます。

ただし、1つ落とし穴があります。配列には0の接尾辞の最大の長さを保存しますが、あるグループのハッシュ値がどれも1で終わっていたらどうなるでしょうか。例えば、最後の3ビットをハッシュ値が属するグループの番号として使う場合、ハッシュ値「01001100」の0の接尾辞の長さは0です。ビット列「01001」は1で終わるからです。そのため、最大値の配列の添字4（100₂=4₁₀）の位置には0が保存されます。すると Linear Counting アルゴリズムでは、ハッシュ値が4になる値は見つからなかったことになりますが、これは事実と異なります。

そこで、最大値の配列に0の接尾辞の最大の長さではなく、「右から最初の1」の位置（念のため書いておくと、位置は1から数えます）を保存するようにアルゴリズムを変えます。これは、0の接尾辞の長さに1を足すのと同じことです。こうすれば、添字 i の位置の0は、ハッシュ値が i に等しい値が1つもないことを意味するので、この配列を Linear Counting に使えます。

HyperLogLog の実装

順に見ていきましょう。

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

関数 alpha は、計算した推定値の補正を返します。これは前回すでに見ましたが、HyperLogLog では、alpha の値がグループの個数によって変わります。

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

数の末尾にある0のビットの個数を返す関数です。

def count_maxims(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) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

すべての値を順に見ていき、num_buckets 個のグループに分け、グループごとに右から最初の1の位置（0の接尾辞の最大の長さに1を足した値）を求める関数です。

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Linear Counting アルゴリズムを計算する関数を少し変えたものです。

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

すべてをまとめるメインの関数です。まず、改良した LogLog で推定値を求めます。4行目では、相加平均の代わりに調和平均を使います。最後に、2つの条件が成り立つときは、Linear Counting による補正を適用します。1つ目の条件は、計算した推定値がグループの個数の2.5倍以下であることです（この範囲では、LogLog のふつうの推定値は Linear Counting を使った場合より悪くなると考えられます）。2つ目の条件は、最大値の配列に0が少なくとも1つあることです（すべて1の配列は Linear Counting に使えません。前回の記事を参照してください）。HyperLogLog の結果はどうなるでしょうか。

カーディナリティが順に10、100、…、1,000,000の集合について、カーディナリティを推定するテストコードを実行してみます。

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

結果は次のとおりです。

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

結果は、どれも正しい値からのずれが1%未満です。十分な精度です。

HyperLogLog のさらなる改良

HyperLogLog には、ほかにも興味深い改良がいくつか加えられています。残っている問題の1つは、メモリの使用量が多いことです。前回はメモリの使用量の少なさをほめちぎり、最大値の配列を保存するには768バイトで足りることも計算したので、これは奇妙に聞こえるでしょう。しかし、巨大な多重集合1つではなく、数百万個の小さな多重集合のカーディナリティを並行して求めたい場合や、計算した最大値の配列をあとでいろいろ処理するためにデータベースに保存しておきたい場合には、問題になります。

例えば、10億個の多重集合のカーディナリティを同時に求めるとすると、今の実装では 1,000,000,000 × 768バイト、つまり768GBが必要です。悪くないともいえますが、HyperLogLog はもっとうまく実装できます。

疎な表現

k=12 とする、つまり12ビットをグループの識別に使い、ハッシュ値のグループが 2¹² 個できるとします。アルゴリズムの最初に、長さ4,096の配列を確保する必要があります（関数 count_maxims の3行目を参照）。そして、多重集合に異なる要素が3つしかないとします。すると、配列のうち値を設定するのは3か所だけで、残りの4,093個の値は0のまま、つまりまったく使われません。これはあまり効率的ではありません。

大部分が0で使われていないのに、貴重なメモリを占める配列を避けるには、最初のうちは値を [添字, 値] の組として保存すればよいのです。例を見てみましょう。次の配列

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

は、2つの組として、メモリをはるかに効率よく表現できます。

[0, 7], [4, 12]

使わない領域を大量にメモリに確保しておく代わりに、本当に必要な領域だけを少しずつ確保できます。この表現を疎な表現（スパース表現）といいます。ただし、ある時点でこの表現は、配列にそのまま保存するよりメモリを多く使うようになります。そのときは、情報を失うことなく、疎な表現をふつうの配列に変換できます。

オフセット

実際には、配列の値はどれもほぼ同じであることがわかっています。最大値の配列は、ふつう例えば次のようになります。

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

どの値も13の前後です。このような配列を小さくするもう1つの方法は、各要素から一定の値を引き、その値を覚えておくことです。例えば8を引くと、次のようになります。

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

これで、配列の各値が使うメモリは少なくなります。最初の配列では0から15までの数を保存する必要があり、それには4ビットが必要ですが、2つ目の配列では0から7までの数しか保存しないので、3ビットで足ります。もちろん、これは配列をビット単位で実装することが前提です。配列から値を読み出すときは、覚えておいた値を足して元にもどす必要があります。

ほかにも改良はたくさんあります。この分野の研究はまだ続いているので、これからも興味深いアイデアが出てくるでしょう。次回は HyperLogLog のベクトルの和と共通部分について、そして近いうちに、HyperLogLog のベクトルを何十億個も保存しておくと役に立つ理由について説明する予定です。

リンクと参考文献

• 実装の全体は GitHub で見られます。
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF]：HyperLogLog を初めて発表した論文。
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF]：もとの HyperLogLog を、前に述べた疎な表現などで改良した版。