2017-02-04

GolangでBloomFilterを実装してみた

2018/02/17追記
Goらしくレシーバを使うようリファクタリングしました。実装が少し変わっていますが、考え方自体は本記事から変わりありません。リファクタリング後の実装は以下のGithubのとおりです。

github.com

前回調べたBloomFilterをGolangで実装してみました。

要素を蓄えるBloomFilterの用意

BloomFilterをサイズm[bit]のboolean配列として用意します。
実装中ではmをsizeという変数にしているので、適宜読み替えてください。今回はBloomFilter型を用意します。

gistf2f5c87d2ca403d6f1b3deacb4d52ab4

使用するハッシュ関数

要素の追加および要素の有無を検証するときに、k個のハッシュ関数を用意する必要があります。今回はハッシュ関数としてMD5を用いることにします。

gist4c6a2e7a9d80775c78c209540a9d90ed

最適なハッシュ関数の数

k個のハッシュ関数と述べましたが、kはどのように決定すればよいのでしょうか。結論からいうと最適なハッシュ関数の数kは以下のように得ることができます。

$k = \frac{m}{n} ln{2} \tag{1}$

ここでnはBloomFilterに蓄える要素の数です。

導出

式(1)は偽陽性確率を最小化するようにkを決定することで得られます。
Wikipedia にも記載されていますが、まずm[bit]の配列において、あるbitを、あるハッシュ関数でマッピングした場合を考えます。そのbitが0(false)のままである確率は以下のようになります。

$\displaystyle 1 - \frac{1}{m} \tag{2}$

k個の独立なハッシュ関数を用いてマッピングしても、そのbitがまだ0(false)のままである確率は、式(2)をk回の独立な試行を繰り返すことになるので以下です。

$\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{k} \tag{3}$

さらに、n個の要素を追加してなお、そのbitが0(false)のままである確率は

$\displaystyle \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{4}$

です。よってそのbitが1(true)になっている確率は1から式(4)を引けばよいので

$\displaystyle 1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \tag{5}$

として得られます。ここまでをBloomFilterに要素を蓄え終わった状態と考え、新たな要素が上記までで蓄えたBloomFilterに含まれているかを検証します。
このとき偽陽性確率は、新たな要素に対してk個のハッシュ値を計算し、そのマッピング先が既にすべて1(true)になっている場合です。つまり偽陽性確率は以下のように表されます。

$\displaystyle \Bigl(1 - \bigl(1 - \frac{1}{m} \bigr)^{nk} \Bigr)^{k} \tag{6}$

これを近似すると以下が得られます。

$\displaystyle \bigl(1 - e^{- \frac{kn}{m}} \bigr)^{k} \tag{7}$

上記に対して、m,nを固定してkの極値を求めることで最適なハッシュ関数の数 $k = \frac{m}{n} ln{2}$ を求めることができます。そもそもkはハッシュ関数の数なので整数ですし、離散最適化で考える必要があるような気もしましたが、Adamらの論文でも以下の記載があるので、実装上kを整数で丸めることにしました。

k must be an integer, and a smaller, suboptimal k might be preferred, since this reduces the number of hash functions that have to be computed.

gistcdae885488a6c951035e3aba4c3eed68

Double Hashing法

次に悩むポイントが、k種類のハッシュ関数をどのように用意すればいいのかです。Adamらの素敵な提案によると2つのハッシュ関数 $h_{1}(x), h_{2} (x)$ を用いて新しいハッシュ関数 $g_{i}(x), i = 1, 2, \cdots , k$ を以下のように得ることができます。

$\displaystyle g_{i}(x) = h_{1}(x) + i h_{2}(x) \tag{8}$

今回ハッシュ関数として用いたMD5の戻り値は128[bit]となるので、これを前半後半64[bit]ずつで分けて $h_{1}(x), h_{2} (x)$ とします。
ただし、これをそのままint64の変数として扱おうとすると式(8)を計算する際にoverflowしてしまいます。そこで多倍長計算を行うためにmath/bigパッケージを使用します。
C言語でいうところのGMPライブラリですね。

giste254088e7a699d3955f1ba1d101c13a6

要素の追加

BloomFilterに要素を追加する関数です。

gist6b13fac1db57d676e72bb39d258e6888

追加したい要素からハッシュ値を計算し、それを半分に分けて、Double Hashing法でk個のハッシュ値を求めます。
さらにそれをBloomFilterに蓄えるために、k個のハッシュ値を配列BloomFilterのindexとして、対応する箇所をtrueとしてマッピングします。

要素の検証

BloomFilterに要素が含まれているかを検証する関数です。

gistab1072fe99b8250e0783334a6ea99c7c

Addと同様に、ハッシュ値を前半後半の2つに分けて、Double Hashing法でk個のハッシュ値を求めます。 k個のハッシュ値を配列BloomFilterのindexとして、値がひとつでもfalseであれば、要素は含まれていないと判断します(全部trueのときは偽陽性の可能性あり)。

使い方

[1, 2, 3, 4, 5]をBloomFilterに追加して、要素が含まれているか、検証してみます。

gist24ff41df156b37c624f28d0cb15406b4

確かに偽陽性は起こりうる(上の例だと999のとき)ことがわかります。
一方で、偽陰性はなく、1, 2, 3, 4, 5はすべてtrueになっていることがわかります。

コードはGithubにあげてあります。
ハッシュ関数の計算は並列で行っても問題ないため、goroutineで並列化したものも別ブランチで実装してみました。
goroutineの起動コストもあるらしいので、どっちがいいかは、ちゃんとベンチマークとりたいですね。

最後に

最近データ構造アルゴリズムを実装して遊んでいるので、試すためによさげなデータ・セットが欲しいこの頃です。
(ベンチマーク取るにしても良いデータじゃないと意味なさそう...)

Wikipedia にも載っていますが、要素の削除を可能にしたCounting filterやBloomFilterのリストを作り、scalableにしたBloomier filterなどBloomFilterの亜種がたくさん存在しているようなので、そっちも実装していきたいです。

参考

2017-01-28

BloomFilterについて調べてみた

BloomFilterとは

Wikipedia にも記載されていますが、ある要素が集合に属しているかを検査できるフィルタです。

一番最初に思いつく実装としては、こんな感じでしょうか。

集合の先頭から順に要素を比較していく
途中で見つかれば「属している」
最後まで見つからなければ「属していない」

この場合、要素数をNとして、O(N)の計算量が必要ですが、BloomFilterでは、BloomFilterで使用するハッシュ関数の個数をkとして、O(k)で計算ができます。
もちろん、これにはトレードオフがあり、「属している」と判断したものの、 実は「属していなかった」 という偽陽性を許容することで上記のような利点を実現しています。
※ただしBloomFilterでは、原理的に偽陰性はありません。

詳細はこのあとみていきますが、実際に動かしてみるとわかりやすいので、体験したい方はGUIでポチポチできるこちらがおすすめです。

空間効率性

以前、記事にも書きましたが、A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は $N log_2 \frac{1}{p} \times log_2 e$ [bit]です。
ここで、pを偽陽性確率、Nを集合の要素数とします。

単純に生データを格納することを考えると、 $N \times$ 要素の大きさ[bit]の領域を確保する必要があります。
例えばユーザIDを8文字英数と絞ったとして $N \times 8文字 \times 8(1Byte)$ [bit]が必要です。このことからもBloomFilterの空間効率性が高いことがわかります。

計算時間

前述の通り、kをBloomFilterで使用するハッシュ関数の個数として、O(k)で計算ができます。要素の追加もO(k)です。

セキュリティ

副次的なメリットですが、セキュリティ面でも有利な可能性があります。
redis4.0で使えるようになるかもしれないモジュールredabloomsでも使われているDebloom。
こちらのREADMEを読むまで発想すらなかったですが、アプリケーションでの応用を考えたときに実データを保持しなくてよいというセキュリティ上のメリットも考えられます。 READMEにあるのは以下の記載なので、そこまで踏み込んだ記載ではないですが……。

A Bloom filter gives the application cheap, memory efficient set operations, with no actual data stored about the given element.

どういうことかと言うと、BloomFilterでは実データのハッシュを計算し、その結果をもとに配列へのマッピングを行うため、実データそのものをストアしておく必要がありません。
当然、この場合は暗号学的な現像計算困難性や衝突困難性を満たすようなハッシュ関数を選択する必要があります。 MD5のようなハッシュ関数を使用している場合は、この限りではありません。

応用先

Broderらのsurveyによると1970年にBloomによって提案されて以来、初期のUNIXのスペルチェックで使われていたそうで、今でもデータベースの分野でよく使われているそうです。

セキュリティ の箇所でも述べましたが、 redis にも以下の記載があり、使われているようです。

Encode a lot of data in little space, or create a Redis backed Bloom Filter using GETBIT and SETBIT.

Broderらのsurveyでも述べられていますが、リストで持つようなデータではBloomFilterに応用できる可能性があるということの実例ですね(リストで保持している=検索したいという考えのもとで)。

ほかにもsquid-cache でも使われていたり、http2のcache-aware server pushの文脈でもBloomFilterが登場します。cache-aware server pushでは、Golomb coded setが使われているみたいです。
Golomb coded setについては以前まとめたのでこちらをどうぞ。

最後に

応用先について、調べれば調べるほど出てきてまだまだ出てきそうです。読んでいる途中の論文でも登場しているので、まとまったら追記したいです。
実装もそのうち記事にします。。。

2017/2/4 追記
実装も記事にしました。

参考

2017-01-22

Golangでソートアルゴリズムのベンチマークを書いてみる

前回はテストを書いたので、今回はベンチマークです。対象アルゴリズムは前回同様、以下7つのソートアルゴリズムです。

ベンチマークの書き方

Go言語標準のtestパッケージにあるようにBenchMark<関数名>の形で関数を書き、引数をb *testing.Bにします。
するとb.Nが自動的に設定され、[0, b.N)でループし、ベンチマークが計測されます。
前回と同様にBubbleSortを例に取ると以下のようになります。

gistb8368c3fa411a7150eaa662d441979a1

ここで注意が必要なのは、ソート対象を毎回初期化してあげることです。
今回のコードではsliceを渡しているので値渡しではなく、参照渡しとなります。そのため、2回目以降のループではソート済みのsliceをソートすることになり、正しくベンチマークできません。
詳細は「ソート対象の初期化漏れ」にて後述します。

今回やりたいのは他のソートアルゴリズムも含めた比較なので、ソート対象の変数は以下のように別ファイルで定義することにします。
(以下の例の対象は適当です)

gistf3b900057c02e0905169e3e7ebf0aac7

-benchオプションを付けて実行してみると以下のようになります。

# go test -bench BubbleSort
PASS
BenchmarkBubbleSort-2         20000000         111 ns/op

2000万回実行し、一回あたり平均で111nsでした。簡単にベンチマークが書けていいですね。
ディレクトリ内をまとめて実行したい場合はgo test -bench .とすればOKです。

ハマったところ

ベンチマーク結果の前にハマったところです。

ソート対象の初期化漏れ

ソート対象をsliceとしてソートアルゴリズムに渡していることに注意を払っておらず、ソート済みの配列でベンチマークを取っていました。
毎回、sliceを初期化してあげないと二回目以降のループでソート済みの配列をソートすることになってしまいます。 (前述の通り、値渡しではなく、参照渡しのため)

実際、初期化をせずに行ったベンチマークの結果は以下です。

// ソート対象: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0}

# go test -bench .
PASS
BenchmarkBubbleSort-2        20000000           83.7 ns/op
BenchmarkHeapSort-2           3000000          572   ns/op
BenchmarkInsertionSort-2    100000000           17.7 ns/op
BenchmarkMergeSort-2          2000000          804   ns/op
BenchmarkMQuickSort-2        20000000           86.8 ns/op
BenchmarkSelectionSort-2     20000000           99.6 ns/op
BenchmarkShellSort-2          3000000          528   ns/op

やたらと挿入ソート(InsertionSort)が早くなっていることがわかります。
ちなみにBubbleSortを例としたコードは以下です。 2回目以降はソート対象aが初期化されず、ソート済み配列となります。

gistc5799874dd907597a619a0f2d60f8c84

ベンチマークのループ内で`StartTimer()`と`StopTimer()`を呼ぶと遅い

今回の場合、ソース対象を初期化したり、乱数でソート対象を生成してベンチマークを測定します。その処理はソートアルゴリズムの実行時間とは関係ないので、初期化処理中はベンチマークのタイマーを止めたくなります。
実際、testパッケージにはStartTimer()とStopTimer()が用意されています。

ところがこれはベンチマークループの外で呼ぶべきです。
ベンチマークタイマーの計測開始は、[0, b.N)のループからではなく、BenchMark<関数名>(b *testing.B)が実行されたときから、だからです。

stackoverflowですが、Golang benchmarking b.StopTimer() hangs — is it me? にも書いてあるように、b.Nが10億などとなった場合、ループ中でStartTimer()やStopTimer()を呼ぶとベンチマークに膨大な時間を要します。
例えば1回のタイマー停止/開始に要するが100nsだとしても、現実世界では10億回のループ中に100秒が経過してしまいます。
これとは別にStartTimer()やStopTimer()を呼ぶコストやベンチマーク対象の時間が乗ってきます。

今回はその回避策として、初期化処理だけのベンチマークを測定し、それに要する時間をソートアルゴリズムのベンチマークから引く方法を取ります。
計測用のコードは以下です。

gist68c61fa11c1371912da88d55ef316e5d

~~Base(baseline)じゃなくてoffsetで名前統一すべきだった~~

結果

以下の3パターンをベンチマークしてみます。

無印: {0, 3, 1, 2, 3, 4, 5, 1, 9, 0}
Sorted: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
RandomizedData: [0, 9]をランダムに並べた順列(重複なし)

# go test -bench .
PASS
BenchmarkBaseCopy-2                    200000000          8.14 ns/op
BenchmarkBaseRandom-2                     100000         14619 ns/op
BenchmarkBubbleSort-2                   10000000           111 ns/op
BenchmarkBubbleSorted-2                 20000000          90.1 ns/op
BenchmarkBubbleSortRandomizedData-2       100000         14923 ns/op
BenchmarkHeapSort-2                      2000000           696 ns/op
BenchmarkHeapSorted-2                    2000000           615 ns/op
BenchmarkHeapSortRandomizedData-2         100000         15420 ns/op
BenchmarkInsertionSort-2                10000000           149 ns/op
BenchmarkInsertionSorted-2              50000000          23.2 ns/op
BenchmarkInsertionSortRandomizedData-2    100000         14848 ns/op
BenchmarkMergeSort-2                     2000000           884 ns/op
BenchmarkMergeSorted-2                   2000000           771 ns/op
BenchmarkMergeSortRandomizedData-2        100000         15719 ns/op
BenchmarkQuickSort-2                    10000000           206 ns/op
BenchmarkQuickSorted-2                  20000000          90.5 ns/op
BenchmarkQuickSortRandomizedData-2        100000         14814 ns/op
BenchmarkSelectionSort-2                10000000           184 ns/op
BenchmarkSelectionSorted-2              20000000           108 ns/op
BenchmarkSelectionSortRandomizedData-2    100000         15197 ns/op
BenchmarkShellSort-2                     2000000           668 ns/op
BenchmarkShellSorted-2                   3000000           529 ns/op
BenchmarkShellSortRandomizedData-2        100000         15568 ns/op

流石に生そのままだと見づらいので、グラフにします。 offsetも引いてあります。

f:id:cipepser:20170122171809p:plain

ソート済みの挿入ソート圧倒的ですね。また要素数が10個程度なのでバブルソートでも有用な感じですね。せっかくなので要素数を多くしてみましょう。手でソート対象を10万個も書くのは大変なのでソート済みと乱数のみにします。
結果は以下です。軸は縦横ともにlogスケールにしています。

f:id:cipepser:20170122171811p:plain

f:id:cipepser:20170122171815p:plain

こちらでもソート済みであれば、挿入ソートの速さが伺えます。
また乱数の結果から、一般にはクイックソートが速いというのもわかりますね。

各ソートアルゴリズムの平均計算量は、以下です。

ソートアルゴリズム	平均計算量
バブルソート	O(n²)
ヒープソート	O(n log n)
挿入ソート	O(n²)
マージソート	O(n log n)
クイックソート	O(n log n)
選択ソート	O(n²)
シェルソート	O(n log n)

乱数のほうを見ると要素数が大きくなるにつれて、O(n²)と $O(n log n)$ ではっきりとわかれてくることがわかります。
要素数が小さい範囲では、クイックソートが最速ではないので、実用上は入力の要素数によってソートアルゴリズムを使い分けるのがよさそうです。

最後に

コードはGitHubにもあげてあります。

2017/1/14 修正 Gitではなく、GitHubとの指摘を頂いたので修正しました。

Reference

2017-01-15

Golangでソートアルゴリズムのテストを書いてみる

背景

先日書いた記事にてクイックソートのバグをご指摘頂きました。
実装中は適当に入力値を変えてソートがうまくできていることを確認していたものの、実装して満足してしまったためにバグが混入していました。
やはり テストはしっかり書かなくてはいけない と思い、go testしようじゃないかと思い立ちました。

どうやってテストするか

未整列な配列は用意するにしても、いちいちそれを手作業で正しい順番にするのもめんどくさいしですし、それこそバグが混入するかもしれません。
テスト対象と比較すべきは、正しい結果 です。 Go言語標準のsortパッケージを使いましょう。
Godocにもあるように以下のように使用します(l.11)。

gist432ad7127932ecf06acd2978e0dcc2a1

配列同士の比較はreflectパッケージのDeepEqual を使用します。

gistf0ec9f7b3753cda59d84d05d2b631557

今回ソートアルゴリズムについて、テストの入力パターンは[]intに限るとすると go test で出来ることのTipsが有効なのでループでテストさせます。

テストパターンはソートアルゴリズムにまたがり共通なので以下のように別出ししておきます。
パッケージ名はMySortとしました。

gist4a671073d198359db81104618e763db2

BubbleSortでの例は以下です。

gista7dace84aae086af18858a69693ad9c4

gist59f87abcfd8397c552fcaddf79e143ca

テスト結果

では前回実装した以下7つのソートをテストしてみましょう。

実装はgitにあげてあります。

いよいよテストです。
git testを実行する際はMySortディレクトリ内で行います。

# go test
PASS
ok      MySort  0.004s

通ってますね。
ちなみにわざと失敗するケースとしてactualとexpectedの比較の前にactual[0] = 100とすると以下のようになります。
どのように表示するかはif文の中に書けばよいので見やすいよう成形しましょう。

# go test
--- FAIL: TestSort (0.00s)
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 2 3 4 5]
        actual: [100 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [1 1 2 3 4 5]
        actual: [100 1 2 3 4 5]
    BubbleSort_test.go:27:
        expected: [0 1 2]
        actual: [100 1 2]
    BubbleSort_test.go:27:
        expected: [1 1 1 1 1 1 1 1]
        actual: [100 1 1 1 1 1 1 1]
FAIL
exit status 1
FAIL    MySort  0.007s

最後に

テスト書きましょうというのは、よく聞くものの実はこれまでテストというものを書いたことがありませんでした。
今回、実際に書いてみてどんなものなのかイメージが掴めました。
が、テストパターンが足りてない気配しかないので網羅性難しいですね......。

またせっかくソートを実装しているので次はベンチマークやりたいですね。
テストだとうまく実装できていれば同じ結果になるので比較して楽しみたいところです。

Reference

2017-01-09

基本的なソートアルゴリズムをGolangで実装してみた

2017/1/14 修正
intelf000さんのご指摘を受け、クイックソートについて、以下のバグを修正しました。
(合わせてsliceが参照渡しであることにも注意し、実装を改めています)

[内容]
a[left], a[right], pivotが同一の値となった場合に panic: runtime error: index out of range が発生。

背景

ソートアルゴリズムの話をするときに、自分の中で整理できていなかったので以下のアルゴリズムを実装してみました。

Goで書いたのは筋トレも兼ねているだけです。

そもそもGoにはsortパッケージがあります。
ちなみにリンク先を見て頂ければわかりますが、sortパッケージはクイックソートで実装されています。
(実体としては、データ長に応じて、ヒープソートと挿入ソートを併用する実装になっています)

ある程度ソート済みのアルゴリズムでは挿入ソートのほうが高速なのでソートしたいデータの特性によってはsortパッケージ以外を使用する選択肢もありそうです。

バブルソート

隣同士比較して交換するだけです.

gist95666e2ef1f45fece4b45fbafdff0f27

選択ソート

最小値(あるいは最大値)を「選択」し、小さい順に並べていくソートです。

gista224fb335644d3ca8567ec6aff87acb7

挿入ソート

整列済みのデータに対して、要素を正しい位置に挿入します。整列済みであることを意識して、比較は後ろから行うようにしてみました。

連結リストで実装するのがよかったですね......。

gistfb4e64acc94d5b92a0227e898df99aa1

シェルソート

適当な間隔 $h_i$ ずつ空けて、グループを作り、グループ内でソートします。さらに間隔を狭めていき、間隔が1になったところで全体をソートします。

上記の過程である程度ソートされていき、最後は挿入ソートで締めます。

Knuth先生のThe Art of Computer Programmingによると以下を満たすよう間隔を選んでいくと $O(n^{1.25})$ になるそうです。
(未読ですが......)

$h_{i+1} = 3h_i + 1$
$h_0 = 1, h_i \in {\cal N}$

giste344fbfc474b18e3e0f548dfaeb65ec8

マージソート

データを適当に分けていき、それをマージする際にソートします。

gist695d1274cca4314d1c755368ccd6abc0

クイックソート

一般なデータに対しては最も高速といわれているそうです。ピボットより小さい値を持つグループと大きい値を持つグループにわけ、再帰的にソートしていきます。

ピボットの選び方によっては無限ループに入ってしまったり、計算量が増えてしまうので注意が必要です。

2017/1/14 訂正（詳細は記事冒頭に記載）

giste9999b007076c5c77f23b9188dc79598

ヒープソート

ヒープ木では根が最大(または最小)になるので、根を取り除き、残った部分をさらにヒープ木にすることを繰り返します。
こちらが大変参考になります。

UpHeapとDownHeapをまとめてヒープ木を作る関数にするのもありかと思ったのですが、それだと必要以上に計算が多くなるので微妙なんでしょうか。

gist71006d4ed430ae94e04dd6fe3c182ada

感想

全体的にGoの配列(slice)の操作に苦戦しました。複数の値をまとめて代入できなかったり、配列を添え字で抜き出すところとか自分の想像する挙動と微妙に異なるので境界は特に気を遣いながら書きました。

上記以外にも様々なソートアルゴリズムがあるので実装していきたいです。特にデータの特性に応じて、一定の条件下ではより高速になるようなソートはおもしろそうですね。

Reference

2017-01-01

Golangで言語処理100本ノック2015 第1章: 準備運動

言語処理100本ノック 2015の第1章: 準備運動の10問です。

00. 文字列の逆順

文字列"stressed"の文字を逆に（末尾から先頭に向かって）並べた文字列を得よ．

gist09251fc66515bb60f15d58721c08466a

rune(int32のalias)使ってみました。

01. 「パタトクカシーー」

「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ．

gistedcd4efc4d726baa40b331b7e5266e9b

拡張性に乏しいコードになってしまいました......。

02. 「パトカー」＋「タクシー」＝「パタトクカシーー」

「パトカー」＋「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ．

gist2bb8c732a7892380679b0d89c75104a0

range使いたかったものの2つの配列だと難しいですね。

03. 円周率

"Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."という文を単語に分解し，各単語の（アルファベットの）文字数を先頭から出現順に並べたリストを作成せよ．

gist7aad5498729843d80b17ee165820e1c7

04. 元素記号

"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."という文を単語に分解し，1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字，それ以外の単語は先頭に2文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

gist9992125ab064053287a0dd4dd4ae4c0a

マグネシウム......

05. n-gram

与えられたシーケンス（文字列やリストなど）からn-gramを作る関数を作成せよ．この関数を用い，"I am an NLPer"という文から単語bi-gram，文字bi-gramを得よ．

gistcbc1ee78191bf3f77d7a49df56d45a19

結構めんどくさかったものの、文字列はruneとして扱って、最後表示するときだけstringにするほうがバグの混入も減りそうな気がしました。

06. 集合

"paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を，それぞれ, XとYとして求め，XとYの和集合，積集合，差集合を求めよ．さらに，'se'というbi-gramがXおよびYに含まれるかどうかを調べよ．

giste1d1767b1727a65b3d4b1702cfab0dbc

sliceに対してappendだけじゃなくてremoveも欲しくなりました。

07. テンプレートによる文生成

引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ．さらに，x=12, y="気温", z=22.4として，実行結果を確認せよ．

gist916d6c7abb3721d8c4df8e285afc51b2

08. 暗号文

与えられた文字列の各文字を，以下の仕様で変換する関数cipherを実装せよ．

英小文字ならば(219 - 文字コード)の文字に置換その他の文字はそのまま出力この関数を用い，英語のメッセージを暗号化・復号化せよ．

gist89bee82fa497b427b37eef97744b58ce

09. Typoglycemia

スペースで区切られた単語列に対して，各単語の先頭と末尾の文字は残し，それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ．ただし，長さが４以下の単語は並び替えないこととする．適当な英語の文（例えば"I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind ."）を与え，その実行結果を確認せよ．

gist72bf7cadaab3f3219dab0349223925ad

部分配列取り出すとき、a[0:3]のようにしたときa[0], a[1], a[2]が取り出されてa[3]は含まれないのをいつも勘違いするので気をつけていきたいです。

Reference

2016-12-25

Golomb-coded setについて調べてみた

Oku KazuhoさんのHTTP/2の課題と将来を拝見していたらGolomb-coded setなるものが登場したのでいろいろ調べたメモです。

BloomFilterについてもそのうち記事にするかもしれないです。
~~むしろBloomFilterを先に書くべきでは。~~

前提、やりたいこと

やりたいことの例としてhttp2のcache-aware server pushを考える。
clientからserverへリクエストするとき、htmlよりcssを先にpushするといったような優先度付けをしたい。
一方で、既にclientでcacheしていたら、改めてserverからpushするのは無駄。
そこでclientからのリクエスト中のcookieにcache済みのjsやcssといったasset情報埋め込んでserverに教えてあげる。

とはいえ、そのままassetごとにpath/file名とか書くと無駄が大きいし、file名は変わらないけど中身が変わっていたりすると区別ができなくてつらい。
→ハッシュして送る。

ここで偽陽性はある程度許容する。
やりたいことは、すでにcache済みだったら送らない(≒送る数を減らしたい)なので、確実にcacheされてないと言えるなら送る。
(偽陽性で、cache済みと判断したけど実はcacheされてないやつはclientが改めてGETする)
→BloomFilterのような確率的データ構造が適している。

BloomFilterの空間効率性

A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は以下。

BloomFilterで使うbit数: $N log_2 \frac{1}{p} \times log_2 e$

確率的データ構造に使うbit数(理論値): $N log_2 \frac{1}{p}$

$N: 貯めておく要素数$
$p: 偽陽性確率$

$log_2 e ≒ 1.44$ なので44%程度、BloomFilterは理論値より空間効率が悪い。

挿入するデータの分布に適した方法でデータを格納すれば理論値に近づく。
→Golomb-coded setは、ハッシュ値の均一性を利用し、幾何分布のときにHuffman符号と同じ効率になるGolomb符号により理論値に近づける。

Golomb-coded set

※例は以下の参考文献のなぞり。

Golomb-coded sets: smaller than Bloom filters

変数はさっきと一緒。

$N: 貯めておく要素数$
$P: 偽陽性確率$

例題として以下のフォネティックコード( $N = 26$ )を考える。

['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu']

許容する偽陽性確率を $P = \frac{1}{64}$ とする。

要素は適当なハッシュ取ってから $mod (N \times \frac{1}{P} (= 1664)$ する。

※cache-aware server pushで使う場面では、sha-2にするというようなセキュリティ性は担保しなくてよく、均一性と速度のほうが重要なのでMD5やsha-1で十分。

→ $[0, (N \times \frac{1}{P} ) ] = [0, 1664$ ]でハッシュ値が分布する。
ここで $N(= 26)$ 要素をハッシュ計算してからソートする。
十分に均一なハッシュならソート後の要素列のi番目とi+1番目の差は $\frac{1}{P} (=64)$ くらいになる(ことが多いと期待される)。
→ $\frac{1}{P} (=64)$ で割ると、商は0 or 1になることが多い。
→これ幾何分布となるのでGolomb符号使うと効率がよい。

符号化は以下の表のように行う。

商	符号化
0	0
1	10
2	110
3	1110
4	11110

余りはそのまま2進数でくっつける。
例) 68 / 64 = 1 ... 4 → 68 = 0b(10 100)
※10と100の間のblankは便宜的に入れてるだけ。

これでフォネティックコードを符号化すると以下になる(197 bits)。

11001011 10101001 00100000 11110111 10000000 01100110 00111010 00000110 00011111 00100000 01100101 00011001 10001010 10110001 00000011 00101101 01100010 01001100 01010000 00110011 00011110 01100110 10101110 10011000 00011

それぞれデータの格納に必要なbit数は以下のようになるので、BloomFilterより理論値に近くなっていることがわかる。

理論値: 156 bits  
BloomFilter: 225 bits (最適なハッシュ関数の数で同じ偽陽性確率を許容する場合)  
Golomb-coded set: 197 bits

要素を蓄えるBloomFilterの用意

使用するハッシュ関数

最適なハッシュ関数の数

導出

Double Hashing法

要素の追加

要素の検証

使い方

最後に

参考

BloomFilterとは

空間効率性

計算時間

セキュリティ

応用先

最後に

参考

ベンチマークの書き方

ハマったところ

ソート対象の初期化漏れ

ベンチマークのループ内でStartTimer()とStopTimer()を呼ぶと遅い

結果

最後に

Reference

背景

どうやってテストするか

テスト結果

最後に

Reference

背景

選択ソート

挿入ソート

感想

Reference

Golangで言語処理100本ノック2015 第1章: 準備運動

00. 文字列の逆順

01. 「パタトクカシーー」

02. 「パトカー」＋「タクシー」＝「パタトクカシーー」

03. 円周率

04. 元素記号

05. n-gram

06. 集合

07. テンプレートによる文生成

08. 暗号文

09. Typoglycemia

Reference

前提、やりたいこと

BloomFilterの空間効率性

Golomb-coded set

参考

ベンチマークのループ内で`StartTimer()`と`StopTimer()`を呼ぶと遅い