この記事は Go Advent Calendar 2019 の2日目の記事です。
こんにちは！さいぺです。
サムネのGopherくんは最近趣味で描いたものを、せっかくなので載せました。
オリジナルのThe Go gopher（Gopherくん）は、Renée Frenchによってデザインされました。
さて、以下の動画を見てMiniSketchなるデータ構造があることを知りました。
MinisketchってIBLTを比較してメリデメとかあるんだろうか。そもそもどういうデータ構造使ってるんだろ。
— さいぺ (@cipepser) 2019年11月13日
【動画で学ぶブロックチェーン】Bitcoinの新しいTxリレープロトコルの提案 Erlay - 安土 茂亨氏 - YouTube https://t.co/mKB18CmWAF
動画中の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として、二つの要素と
を追加する例を考えます。3つの各テーブルのindexは0始まりで図示しています。
1つ目の要素に対して、3つのハッシュ値を計算し、該当するフィールド（中段図の赤字）をインクリメントします。
続けて、2つ目の要素に対して、3つのハッシュ値を計算し、該当するフィールド（下段図の赤字）をインクリメントします。
要素がいくつ追加されたのか知りたいときも同じような手順をとります。
例えば上記の例でがいくつ追加されたのか知りたいとします。
このとき要素
に対する3つのハッシュ値を計算します（図中の中段から下段に移動したときと同じ）。該当するフィールドの値を参照すると
1、2、1が得られます（下段図の赤字）。この3つの数字のうち、最小(min)の値を要素が追加された数として返すのがCount-min sketchです（今回の例では1を返す）。
と
が衝突しましたが、ハッシュ関数を3つ用意したことで、衝突していない残り2つの値が正しい答えとして、追加された要素の数を表現できていることがわかります。
実装
アルゴリズムが理解できたところで実装に移ります。 本記事ではポイントを絞って説明しますが、実装した一式はGitHubにあるので興味がある方はご覧ください。
データ構造
まずSketch型を以下のように定義します。
ここでkはハッシュ関数の数、Nは各テーブルのサイズです。
type Sketch [k][N]int
Addの実装
k個のハッシュ関数は、Double-hash法で用意します。
Double-hash法については、以前の記事で触れていますのでご参照ください。
今回は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個のハッシュ値のうち最小のものを、追加された要素の数として返します。
動作を確認する
実際に動かしてみましょう。
以下のようにa〜eをそれぞれ1〜5個追加します。
なお、ハッシュ関数の数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
ハッシュ衝突させてみる
ハッシュ衝突させてみたかったので、要素の数を増やしたところgとhで衝突しました。
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
今回はベンチマークまで取れていないのでkやNを大きくしたときにどうなるか調べるのもおもしろそうです。
あとはMiniSketchでの集合をreconcileもいずれ実装したいです。
