そもそもスペルチェックってどうやるの
ある単語が辞書に含まれているかどうかをチェックするという超地味な処理をします。ふつうにやると、辞書に含まれる単語数をnとして、O(n)の計算時間がかかります。
ブルームフィルタ
とはいえ、1単語打ち込むごとにO(n)の処理が走っているとちょっと嫌です。そこで、より簡便な計算で、単語が辞書に含まれているかを確認する手法がブルームフィルタになります。
ブルームフィルタは定数時間O(k)で動作します。
このkは辞書内の単語数nとは無関係の定数で、さらにちょっと小細工することでk=1でも動作可能です。
なのでめちゃくちゃ速い！
O(n)の計算量で線形探索した場合は、ある単語が辞書に存在するか、存在しないか、100%正しい判定ができます。
一方で、ブルームフィルタの場合は、存在しないという判定は100%正しくできます（偽陰性FNはない）が、存在すると判定した場合は100%正しいとは限りません（偽陽性FPはある）。
なので、ブルームフィルタの出力としては、「その単語は絶対に辞書にないよ！」か「その単語は辞書にあるよ！（もしかしたら超低い確率であるかもしれない）」の2つです。
「ない」と言われた場合は絶対にないことが保証されているので、例えばスペルチェッカーでは、辞書にない単語としてアラートを出します（その単語に赤線を引くなど）。
また、後述しますが、ブルームフィルタのサイズパラメータを調整することで、偽陽性率を実用的なライン(1%以下)まで落とすことができます。
より厳密な判定が求められるアプリケーションでは、「ある」と判定されたケースのみ、実際に総当りの線形探索などで辞書をチェックします。
一方、「ない」と判定された場合は絶対ないので、こちらのケースではコストのかかる線形探索をしなくて済みます。
すり抜けたもの（「ある」のケース）のみ、よりコストのかかる処理を行えばよいという点が、この手法がフィルタと呼ばれる所以です。
ブルームフィルタを使用する際の処理
ハッシュ関数というのは、データを入力すると、そのデータから計算された（一見ランダムに見える）数値を返してくれる関数のことです。
入力が同じであれば、（一見ランダムに見える）出力の数値も同じになるので、データの改ざん検出などに使用されます。
このようなハッシュアルゴリズムは数多く考案されていますが、BFの実装にはどれを使っても構いません。
ハッシュアルゴリズムには有名なMD5を使用します。
MD5では、入力から計算された数値は、16進数で32桁の数値になります。
MD5で
この値をインデックスと考えて、0で初期化しておいた配列の対応するビットを1に変えます。
プラスアルファで細かい注意点として、以下の2点があります。
次に使う際の動きです。
まず、同様にMD5で計算します。
先ほどと同じ、
次にこの値をインデックスとして、配列を参照します。
このビットは、先程
逆に登録していない場合は、初期状態のまま0なので、ビットの値(0/1)によって単語の有無を判定できるわけです。
大枠の流れは以上です。
以下は、BFを実用的なものにするための工夫になります。
ビットが0の場合は、そのビットは書き換えられていないので、同じ単語が辞書に含まれていないことは保証されます。
これが偽陰性は無いことが保証される理由です。
逆にビットが1の場合ですが、先ほどの
ところが、ハッシュには衝突という厄介な性質があります。
ハッシュアルゴリズムで生成される（一見ランダムに見える）数値は、実は元データと一対一に対応していません。
とても低い確率で、異なるデータから同じハッシュ値が生成されてしまうことがあります。
これをハッシュの衝突といい、衝突率の低さはハッシュアルゴリズムを評価する指標のひとつにもなっています。
なので、すごく低い確率ですが、辞書内の別々の単語から同一のハッシュができてしまう可能性もあります。
また、ハッシュアルゴリズムと配列サイズによっては剰余の計算が必要になるのでした。
そのため、最終的なインデックスが被ってしまう（別々の単語なのに同じインデックスにビットを立ててしまう）可能性がさらに高くなります。
これが、辞書に本来存在しない単語を「ある」と判定してしまう、偽陽性が生じる理由です。
この問題を回避するために、BF作成処理の１は「ハッシュ値をいくつか作る」となっています。
ハッシュ値がひとつだけだと、偶然被ってしまう可能性があります。
一方、ハッシュ値をいくつか作ると、存在条件はすべてのハッシュ値が一致すること（すべてのインデックスのビットが1になっていること）になり、そのすべてが偶然1になっている確率をとても低くできます。
ハッシュ値をいくつか作るもっとも単純な方法は、別々のハッシュ関数を複数使うことです。
ここでハッシュ関数をk個使用した場合のkが、計算量O(k)のkになっています。
MD5もそうですが、多くのハッシュ関数では、16進数で32桁、64桁、128桁などの大きな数字ができるので、8桁ずつに区切って、それをインデックスにすればよいのです。
例えば、
そのためk=1となり計算量をO(1)にできるのですが、厳密には配列のk個の要素を参照する必要はあり、その部分にこだわるのなら計算量はO(k)のままです。
このアルゴリズムのパラメータは、データ数n、ハッシュ値の種類k、配列の長さmの3つです。
実際のアプリケーションでは、これを上手いこと調整する必要があります。
以下の証明は覚えておく必要ないですが、最後の結果の式だけは覚えておくと役に立ちます。
例えば、配列の要素の大半が1になっている状況を考えます。
このようなBFでは、ほとんどの単語は存在すると判定されてしまい、使い物になりません。
逆に、配列の長さmを無限に大きくすれば、0が大半のスカスカな配列（疎な配列）になりますが、それだけメモリを消費しますし、無限というのは実用的でありません。
情報量の観点からいうと、ビット配列は0と1が半々のケースで情報量が最大になります。
このとき適当に参照したビットが1になっている確率は \( (\frac{1}{2})^k \) ですね。
また、あるハッシュ値で配列のひとつのビットが0のままである確率は \( 1-\frac{1}{m} \) なので、すべての単語を登録した後に、あるビットが0のままである確率は \( (1-\frac{1}{m})^{kn} \) 、逆に1になっている確率は \( 1-(1-\frac{1}{m})^{kn} \) です。
よって、適当なハッシュ値k個でビットを参照したときに、すべて1になっている確率は以下になります。
これが \( (\frac{1}{2})^k \) と等しくなるとよいので、最適なkは \( k = \frac{m}{n}\log{2} \) になります。
この式は覚えておきましょう。
Pythonの実装例を載せます。
n=7単語の場合、m=40でだいたいk=4くらいになります。
これでも偽陽性率は16分の1=6%程度に抑えられます。
また、k=4なら、ちょうどMD5の8桁ずつのハッシュ値が使えますね。
ちなみに、k=4を維持するためには、単語数nの6倍程度の配列サイズmを用意する必要がありますが、単語数10万でも6e5程度で済みます。
なのでめちゃくちゃ速い！
O(n)の計算量で線形探索した場合は、ある単語が辞書に存在するか、存在しないか、100%正しい判定ができます。
一方で、ブルームフィルタの場合は、存在しないという判定は100%正しくできます（偽陰性FNはない）が、存在すると判定した場合は100%正しいとは限りません（偽陽性FPはある）。
なので、ブルームフィルタの出力としては、「その単語は絶対に辞書にないよ！」か「その単語は辞書にあるよ！（もしかしたら超低い確率であるかもしれない）」の2つです。
「ない」と言われた場合は絶対にないことが保証されているので、例えばスペルチェッカーでは、辞書にない単語としてアラートを出します（その単語に赤線を引くなど）。
また、後述しますが、ブルームフィルタのサイズパラメータを調整することで、偽陽性率を実用的なライン(1%以下)まで落とすことができます。
より厳密な判定が求められるアプリケーションでは、「ある」と判定されたケースのみ、実際に総当りの線形探索などで辞書をチェックします。
一方、「ない」と判定された場合は絶対ないので、こちらのケースではコストのかかる線形探索をしなくて済みます。
すり抜けたもの（「ある」のケース）のみ、よりコストのかかる処理を行えばよいという点が、この手法がフィルタと呼ばれる所以です。
ブルームフィルタのアルゴリズム
ブルームフィルタの作成する際の処理- 適当な長さの配列を0で初期化する
- 辞書の単語すべてについて適当なハッシュ関数でハッシュ値をいくつか作る
- 各単語のハッシュ値をインデックスとして、1で用意した配列にビットを立てる
ブルームフィルタを使用する際の処理
- 作成時と同様の処理でハッシュ値を作る
- 各ハッシュ値をインデックスとして、配列のビットを参照する
- 参照したビットがすべて1であるならば、その単語は辞書に含まれている可能性が極めて高い
- 参照したビットがひとつでも0であるならば、その単語は辞書に含まれていないことが保証される
ハッシュ関数というのは、データを入力すると、そのデータから計算された（一見ランダムに見える）数値を返してくれる関数のことです。
入力が同じであれば、（一見ランダムに見える）出力の数値も同じになるので、データの改ざん検出などに使用されます。
このようなハッシュアルゴリズムは数多く考案されていますが、BFの実装にはどれを使っても構いません。
sunnyという単語を辞書に登録して見てみましょう。ハッシュアルゴリズムには有名なMD5を使用します。
MD5では、入力から計算された数値は、16進数で32桁の数値になります。
MD5で
sunnyを計算すると984aff4a e95d5c7e 1bb25ae8 96b2ece5になります。この値をインデックスと考えて、0で初期化しておいた配列の対応するビットを1に変えます。
プラスアルファで細かい注意点として、以下の2点があります。
- 値が配列のサイズを超える場合は、配列サイズの剰余をインデックスとすること、
- 対応するビットが元から1である(他の単語によってすでにビットが立っている)場合は、何もしない
次に使う際の動きです。
sunnyが辞書に含まれいたかを確認しましょう。まず、同様にMD5で計算します。
先ほどと同じ、
984aff4a e95d5c7e 1bb25ae8 96b2ece5が得られるはずですね。次にこの値をインデックスとして、配列を参照します。
このビットは、先程
sunnyを登録した際に立てたので、1になっているはずです。逆に登録していない場合は、初期状態のまま0なので、ビットの値(0/1)によって単語の有無を判定できるわけです。
大枠の流れは以上です。
以下は、BFを実用的なものにするための工夫になります。
ビットが0の場合は、そのビットは書き換えられていないので、同じ単語が辞書に含まれていないことは保証されます。
これが偽陰性は無いことが保証される理由です。
逆にビットが1の場合ですが、先ほどの
sunnyの例では登録時にsunnyによって立てられたビットだったので期待動作になります。ところが、ハッシュには衝突という厄介な性質があります。
ハッシュアルゴリズムで生成される（一見ランダムに見える）数値は、実は元データと一対一に対応していません。
とても低い確率で、異なるデータから同じハッシュ値が生成されてしまうことがあります。
これをハッシュの衝突といい、衝突率の低さはハッシュアルゴリズムを評価する指標のひとつにもなっています。
なので、すごく低い確率ですが、辞書内の別々の単語から同一のハッシュができてしまう可能性もあります。
また、ハッシュアルゴリズムと配列サイズによっては剰余の計算が必要になるのでした。
そのため、最終的なインデックスが被ってしまう（別々の単語なのに同じインデックスにビットを立ててしまう）可能性がさらに高くなります。
これが、辞書に本来存在しない単語を「ある」と判定してしまう、偽陽性が生じる理由です。
この問題を回避するために、BF作成処理の１は「ハッシュ値をいくつか作る」となっています。
ハッシュ値がひとつだけだと、偶然被ってしまう可能性があります。
一方、ハッシュ値をいくつか作ると、存在条件はすべてのハッシュ値が一致すること（すべてのインデックスのビットが1になっていること）になり、そのすべてが偶然1になっている確率をとても低くできます。
ハッシュ値をいくつか作るもっとも単純な方法は、別々のハッシュ関数を複数使うことです。
ここでハッシュ関数をk個使用した場合のkが、計算量O(k)のkになっています。
MD5もそうですが、多くのハッシュ関数では、16進数で32桁、64桁、128桁などの大きな数字ができるので、8桁ずつに区切って、それをインデックスにすればよいのです。
例えば、
sunnyのMD5ダイジェストを984aff4a、e95d5c7e、1bb25ae8、96b2ece5の4個のハッシュ値と考えることもできるわけです。そのためk=1となり計算量をO(1)にできるのですが、厳密には配列のk個の要素を参照する必要はあり、その部分にこだわるのなら計算量はO(k)のままです。
ブルームフィルタの数理
このアルゴリズムのパラメータは、データ数n、ハッシュ値の種類k、配列の長さmの3つです。
実際のアプリケーションでは、これを上手いこと調整する必要があります。
以下の証明は覚えておく必要ないですが、最後の結果の式だけは覚えておくと役に立ちます。
例えば、配列の要素の大半が1になっている状況を考えます。
このようなBFでは、ほとんどの単語は存在すると判定されてしまい、使い物になりません。
逆に、配列の長さmを無限に大きくすれば、0が大半のスカスカな配列（疎な配列）になりますが、それだけメモリを消費しますし、無限というのは実用的でありません。
情報量の観点からいうと、ビット配列は0と1が半々のケースで情報量が最大になります。
このとき適当に参照したビットが1になっている確率は \( (\frac{1}{2})^k \) ですね。
また、あるハッシュ値で配列のひとつのビットが0のままである確率は \( 1-\frac{1}{m} \) なので、すべての単語を登録した後に、あるビットが0のままである確率は \( (1-\frac{1}{m})^{kn} \) 、逆に1になっている確率は \( 1-(1-\frac{1}{m})^{kn} \) です。
よって、適当なハッシュ値k個でビットを参照したときに、すべて1になっている確率は以下になります。
\( (1-(1-\frac{1}{m})^{kn})^k \approx (1-\exp(-\frac{kn}{m}))^{k} \)
これが \( (\frac{1}{2})^k \) と等しくなるとよいので、最適なkは \( k = \frac{m}{n}\log{2} \) になります。
この式は覚えておきましょう。
ブルームフィルタの実装
Pythonの実装例を載せます。
n=7単語の場合、m=40でだいたいk=4くらいになります。
これでも偽陽性率は16分の1=6%程度に抑えられます。
また、k=4なら、ちょうどMD5の8桁ずつのハッシュ値が使えますね。
ちなみに、k=4を維持するためには、単語数nの6倍程度の配列サイズmを用意する必要がありますが、単語数10万でも6e5程度で済みます。
0 件のコメント:
コメントを投稿