✖

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

データの量が本当に多いとき、その中に含まれる異なる値の個数はどうすれば数えられるでしょうか。例えば、ある大きなウェブサイト、あるいは .jp や .com のドメイン全体のユニークユーザー数を測るサービスを考えてみましょう。

素朴な方法

難しく考える必要はない、と思うかもしれません。データを順に見ていき、それぞれの値を適当なデータ構造に1回だけ保存すればよいのです。Python なら、次のように書けます（わざと冗長に書いています）。

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

これで正しく動きます。では、データが36文字のユニークな v4 識別子で、異なる ID が1,000万個もあったらどうでしょうか。プログラムはそれでも正しい値を計算しますが、メモリをどれだけ使うでしょうか。計算してみましょう。簡単のため、UUID は実際に36文字の文字列として保存するとします。UUID 1つで36バイトなので、1,000万個の ID では360MBになります。

決して少なくはありません。異なる ID が1億個なら、使うメモリはギガバイト単位になります。しかも、これはデータそのものの分だけです。Python や JavaScript のオーバーヘッドを加えると、1,000万個の ID でもギガバイト単位に達することがあります。

これは避けたいところです。どうすればよいでしょうか。

ID そのものをもっと効率よく保存する方法も考えられますし、Python の代わりに C を使えばメモリの使用量は大きく減ります。それでも十分とはいえず、プログラムは依然として膨大なメモリを使います。そこで、次のように問い直してみましょう。異なる値の個数が9,563,618なのか、1の位まで正確に知る必要が本当にあるでしょうか。9,547,666として扱ったら何か困るでしょうか。正確な値がどうしても必要なら、それはそれで構いません。そうでなければ、データに含まれる異なる値の個数を、できるだけ正確に、速く、少ないメモリで推定する方法を見ていきましょう。

救世主はハッシュ関数

入力として文字列を受け取り、ある n ビットの数を出力するハッシュ関数を考えます。ハッシュ関数は文字列を返すもの、というイメージがあるなら、その文字列をさらに数に変換すると考えれば同じことです。ビット数は、その数の大きさを表します。8ビットの関数は8ビットに収まる数を返し、8ビットには 28 通りの値、ふつうは0から255までの整数を保存できます。ここからは24ビットのハッシュ関数を使います。この関数は 224 通り、つまり16,777,216通りの値を返します。

値そのものの代わりに、その24ビットのハッシュ値を保存することにします。1,000万個の24ビットのハッシュ値を保存するには30MBあれば足ります。さきほどの360MBより1けた少なくなりました。コードは次のようになります。

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

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

関数 hash は Python の組み込み関数で、整数を返します。関数 nhash は n ビットのハッシュ関数の素朴な実装です。しくみを理解する必要はありません。実はこの関数は正しく動かず、結果は24ビットに収まらないのですが、ここで伝えたいのは考え方なので気にしないことにします。

その次の関数 count_unique_using_nhash が、異なる値の個数を数えます。すべての値を順に見ていき、ハッシュ値を計算して、その値がまだ変数 found に入っていなければ保存します。

この方法の問題は、ハッシュ関数が異なる文字列に対して同じチェックサムを返すことがある、つまり衝突が起こりうることです。衝突が多いほど、結果は不正確になります。関数 count_unique_using_nhash は、ほとんどの場合、実際の個数より少ない値を返します。

では、どのハッシュ関数を選べばよいでしょうか。それほど重要ではありませんが、一般には MurmurHash の何らかの変種がすすめられています。

ビットマップ

C 言語の入門の授業で、ビットマップを習ったでしょうか。習っていれば、もうご存じでしょう。これをどう使えばよいでしょうか。

考え方を配列で説明します。計算したチェックサムを保存しておく必要はありません。長さ 224 の配列をつくり、すべての要素を0で初期化しておきます。そして、あるチェックサム（これは数です！）が出てきたら、この配列の添字 checksum の位置に1を書き込み、このチェックサムはもう見つかったという印にします。異なる要素の個数は、この配列に含まれる1の個数とほぼ等しくなります。コードは次のようになります。

def count_unique_using_array(values):
    # 長さ 2^24 の、すべて0で初期化したリスト
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

ただし、この場合に配列を使うと、メモリを非常に多く使います。各セルには1か0しか保存しないからです。代わりにビット配列が使えます。例えば、整数（integer）は32ビットに保存できます。354を2進法に直すと101100010です。354はコンピュータの中では32ビットの整数として（細かいことは省きます）次のように保存されます。

00000000 00000000 00000001 01100010

これはなかなか使えそうな形です。この関数で保存したいのは1と0だけで、ふつうの数も実は0と1の集まりにすぎません（コンピュータの中のものはみなそうですが）。つまり、ビット演算を使えば、1を本当に1ビットだけで保存できます。

配列を使った関数にもどりましょう。これをビット配列で書き直すと、24ビットのハッシュ関数なら大きさ 224 ビットのビット配列、つまり2MiBで足ります。大きな進歩です。

出力が 232 通り、つまり4,294,967,296通りある32ビットのハッシュ関数を使う場合は、512MiB のビット配列が必要です。数十億のオーダーまで異なる値を数えられることを考えれば、悪くありません。

Linear Counting

すでに述べたように、ハッシュ関数を使うと、異なる値の個数の推定値しか得られません。異なる値の個数がハッシュ関数の出力の種類の数に近づくほど、この推定は不正確になります。異なる値が50億個あるデータを24ビットのハッシュ関数で数えられないのは当然です。

それでも、ハッシュ関数で求めた推定値は、さらに精度を上げられます。そのために使うのは、データに含まれる異なる値が多いほど、衝突が起こる確率が高くなるという単純な考え方です（衝突とは、2つの異なる入力に対してハッシュ関数が同じ出力、つまり同じチェックサムを返すことです）。ここから少し計算をするので、変数をいくつか導入します。

  • n ビットのハッシュ関数 h を使います。
  • 関数 h の出力としてありうるものの個数は 2n です。この個数を文字 m で表します。つまり m=2n です。
  • どのチェックサムが見つかったかを保存するビット配列を、大文字 A で表します。配列 A の長さは m です。
  • アルゴリズムでデータ全体を処理し終えると、ビット配列の値は0のものと1のものに分かれます。特に注目するのは「0の個数を配列の長さで割った値」、つまりビット配列に占める0の割合です。最初は配列がすべて0で初期化されているので、この割合は1です。0と1が半々なら、割合は2分の1です。この値を Z で表し、Z = 0の個数 / m として計算します。

このとき、Z の値が大きいほど、異なる値の個数の推定が正確だと確信できます。例えば、空のデータを処理すると、ビット配列はすべて0のままで、Z の値は1です。このときは、データに含まれる異なる要素の個数がビット配列の1の個数、つまり0に等しいと完全に確信できます。

Z の値が0.99なら、ビット配列の100分の1が1で埋まっていることになります。配列の99%は0です。これならまだ大丈夫です。計算の途中で衝突はあまり起こらなかったと考えられ、修正はまったく不要か、ごくわずかで済むでしょう。一方、Z の値が0.05なら、配列のうち0のままなのは5%だけで、計算の途中で非常に多くの衝突が起こったと考えられます。この場合は大きな修正が必要です。

では、この修正はどう計算すればよいでしょうか。対数、正確には自然対数（ネイピア数を底とする対数）を使います。自然対数の関数のグラフは次のような形です。

注目するのは、区間 (0, 1] にある赤い部分です。x 軸に Z の値をとると、Z が大きいほど y の値は0に近づきます。逆に、Z が小さいほど y の値は小さくなります。この値に -m をかけると、最終的な推定値が得られます。Z の値が十分小さいと -1 より小さい値が得られ、それに -m をかけると m より大きい推定値になることに注意しましょう。つまり、異なる値の個数が、ハッシュ関数 h から出てきうるチェックサムの総数より多いと推定したことになります。

異なる値の個数 p を求める式は、次のとおりです。

p=−m⋅log⁡Z

（ビット配列を使わず、ふつうの配列だけを使った）実装は、例えば次のようになります。

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

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

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # ここでの log は e を底とする自然対数
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

関数 linear_counting では、まず、n ビットのハッシュ関数を使うさきほどのアルゴリズムで、最初の推定値を求めます。次に、配列に占める0の割合を求め、式にしたがって修正します。コードの中の対数は自然対数です。変数 nonunique_values には number_of_unique_values 個の異なる文字列が入っているので、この例ではリスト nonunique_values に異なる値が1万個あります。6行目の見慣れないコードは、配列に同じ値が複数含まれるようにするためのものです。リストの末尾に同じ値のリストをつなげるので、どの値も配列に2回ずつ現れます。あとは計算するだけです。理想的には、関数はリストに含まれる異なる値の個数として1万を返すはずです。出力は次のとおりです。

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

リスト nonunique_values は毎回新しく生成されるので、結果は呼び出すたびに変わります。ここでは16ビットのハッシュ関数を使いました。関数 count_unique_using_array による最初の推定では、リストに含まれる異なる値は9,289個でした。この推定値を修正して10,017個まで精度を上げました。これはなかなかの結果です。修正後の推定値は実際より0.17%大きいだけですが、修正前は7.11%も小さかったのです。

もっと「大きい」ハッシュ関数、例えば24ビットのハッシュ関数を使えば、さらに正確な結果が得られます。

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

もとの推定値の時点ですでに十分よく、修正後はぴったり1万になりました。試しに、異なる ID を100万個、つまり number_of_unique_values = 1000000 としてみましょう。24ビットのハッシュ関数を使うと、次の結果になります。

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

悪くない結果です。しかも、ビット配列で実装すれば、配列が使うメモリは前に述べた2MB（とプログラミング言語自体のオーバーヘッド）だけです。かなり優秀だといえるでしょう。とはいえ、まだまだ改善できます。それは次回にしましょう。

それまでに、論文 A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] を読んでみるのもよいでしょう。あるいは、シリーズの次の回、Min Value アルゴリズムに進んでください。

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