GoでCount-min sketchを実装する

この記事は Go Advent Calendar 2019 の2日目の記事です。

f:id:cipepser:20191119213339j:plain

こんにちは!さいぺです。
サムネのGopherくんは最近趣味で描いたものを、せっかくなので載せました。 オリジナルのThe Go gopherGopherくん)は、Renée Frenchによってデザインされました。

さて、以下の動画を見てMiniSketchなるデータ構造があることを知りました。

動画中のMiniSketchでは集合のreconcileまで述べられていますが、今回はCount-min sketchを実装します。より具体的には、指定した要素がいくつ追加されたのかを返すデータ構造を実装します。

Count-min sketchとは

Count-min sketchは、追加された要素の数を記憶するデータ構造です。
BloomFilterに似た確率的データ構造で、BloomFilterが要素の有無をboolで返すのに対して、Count-min sketchは追加された要素の数をintで返します。
偽陽性を許容することで、追加された要素の数を得るための最悪計算量が O(1)、メモリサイズを固定にできます。

アルゴリズム

k個のハッシュ関数k個のテーブルを利用します。
各テーブルのフィールドは0に初期化されています。 それぞれのハッシュ関数とテーブルは1:1で対応しており、要素を追加する際にフィールドの値をインクリメントします。

ハッシュ関数の数k=3、テーブルのサイズN=10として、二つの要素 e_1 e_2を追加する例を考えます。3つの各テーブルのindexは0始まりで図示しています。

f:id:cipepser:20191201030221p:plain

1つ目の要素 e_1に対して、3つのハッシュ値を計算し、該当するフィールド(中段図の赤字)をインクリメントします。

続けて、2つ目の要素 e_2に対して、3つのハッシュ値を計算し、該当するフィールド(下段図の赤字)をインクリメントします。

要素がいくつ追加されたのか知りたいときも同じような手順をとります。
例えば上記の例で e_2がいくつ追加されたのか知りたいとします。 このとき要素 e_2に対する3つのハッシュ値を計算します(図中の中段から下段に移動したときと同じ)。該当するフィールドの値を参照すると121が得られます(下段図の赤字)。この3つの数字のうち、最小(min)の値を要素が追加された数として返すのがCount-min sketchです(今回の例では1を返す)。
 h_2(e_1) h_2(e_2)が衝突しましたが、ハッシュ関数を3つ用意したことで、衝突していない残り2つの値が正しい答えとして、追加された要素の数を表現できていることがわかります。

実装

アルゴリズムが理解できたところで実装に移ります。 本記事ではポイントを絞って説明しますが、実装した一式はGitHubにあるので興味がある方はご覧ください。

github.com

データ構造

まずSketch型を以下のように定義します。 ここでkハッシュ関数の数、Nは各テーブルのサイズです。

type Sketch [k][N]int

Addの実装

k個のハッシュ関数は、Double-hash法で用意します。 Double-hash法については、以前の記事で触れていますのでご参照ください。

cipepser.hatenablog.com

今回はDouble-hash法をこのように実装していますが、Sketchのアルゴリズムとは直接関係ないので本記事では省略します。

要素をSketchに追加するためのメソッドAddの実装は以下のようになります。

func (s *Sketch) Add(elem string) error {
    for i := 0; i < k; i++ {
        h, err := util.DoubleHashing(elem, i, N)
        if err != nil {
            return err
        }
        s[i][h] += 1
    }

    return nil
}

k個のテーブルそれぞれに紐づくハッシュ関数があるので、要素のハッシュ値を計算します。 そのハッシュ値ををテーブルのindexだと思って、対応するフィールドをインクリメントするだけです。

Countの実装

要素がいくつ追加されたのかを得るためのメソッドCountの実装は以下です。

func (s *Sketch) Count(elem string) (int, error) {
    min := math.MaxInt64

    for i := 0; i < k; i++ {
        h, err := util.DoubleHashing(elem, i, N)
        if err != nil {
            return 0, err
        }

        if s[i][h] < min {
            min = s[i][h]
        }
    }

    return min, nil
}

Addと同じくk個のハッシュ値を計算します。 k個のハッシュ値のうち最小のものを、追加された要素の数として返します。

動作を確認する

実際に動かしてみましょう。 以下のようにaeをそれぞれ15個追加します。 なお、ハッシュ関数の数k=3、テーブルのサイズN=10としています。

elements := []string{
    "a",
    "b", "b",
    "c", "c", "c",
    "d", "d", "d", "d",
    "e", "e", "e", "e", "e",
}

要素を追加する操作はこんな感じです。

for _, e := range elements {
    err := s.Add(e)
    if err != nil {
        panic(err)
    }
}

uniques := []string{"a", "b", "c", "d", "e"}として、すべての要素がいくつずつ追加されたのか出力させてみます。

for _, e := range uniques {
    cnt, err := s.Count(e)
    if err != nil {
        panic(err)
    }
    fmt.Println(e, ":", cnt)
}

実行結果です。しっかり追加した要素の数を取得できていますね。

❯ go run main.go
a : 1
b : 2
c : 3
d : 4
e : 5

ハッシュ衝突させてみる

ハッシュ衝突させてみたかったので、要素の数を増やしたところghで衝突しました。

elements := []string{
    "a",
    "b", "b",
    "c", "c", "c",
    "d", "d", "d", "d",
    "e", "e", "e", "e", "e",
    "f", "f", "f", "f", "f", "f",
    "g", "g", "g", "g", "g", "g", "g",
    "h", "h", "h", "h", "h", "h", "h", "h",
}

以下のようにg(7個)とh(8個)で15となりました。

❯ go run main.go
a : 1
b : 2
c : 3
d : 4
e : 5
f : 6
g : 15
h : 15

最後に

偽陽性はありますが、データ構造自体のサイズを固定できるのは魅力的です。 今回はテーブルサイズをかなり小さくしたので比較的容易にハッシュ衝突しましたが、もう少し大きなNを選べば十分実用的でしょう。1
今回はベンチマークまで取れていないのでkNを大きくしたときにどうなるか調べるのもおもしろそうです。 あとはMiniSketchでの集合をreconcileもいずれ実装したいです。

References


  1. 本当は偽陽性確率がどれくらいに抑えられるかも本記事に間に合わせたかった