-
35fac884 :むつ
2006-04-22 19:07
-
今日は Bloom Filter で遊びました。
というかやっと理解できました。
Bloom Filter についてはこちらで： http://dev.ariel-networks.com/modules/xfsection/article.php?articleid=18
乱暴な話し、インデックスをハッシュ化＆ビットストリーム化してサイズを小さくするアルゴリズムです。
同じ手法で検索キーワードをハッシュ＆ビット化し、インデックスをハッシュ＆ビット化したものとAND 演算すれば
インデックスに同一の名前が「存在するかもしれない」か「絶対存在しない」かがわかるそうです。
インデックス：「今日」「の」「献立」
検索キーワード：「献立」
ハッシュ＆ビット化した場合仮りに以下のようになったとすると
インデックス：「01011」「01000」「11001」
検索キーワード：「11001」
Bloom Filter はビットの OR 演算（足し算だと思えばいい・笑。ただし 1+1=1）したものを扱えるのでインデックスは
インデックス：「11011」
となる。これと検索キーワードを AND 演算（比較する両者が共に 1 のときのみ 1 他は 0）すると
「11011」と「11001」なので「11001」となる。これは検索キーワードの「11001」と一致。
つまりこのインデックスに検索キーワードと同一の名前が存在する「かもしれない」。
実際のところビットストリームは 1024 バイトとか 1024 キロバイト（＝１メガ）とか長くするので誤認の可能性はとても低くできる。
（上の例はビットストリーム 5 バイト。実際この長さだったら誤認しまくりだと思います）。
なんでこんなので遊んでいたかというと、「cgi でつくるファイル共有ソフト」とか夢想したからです。
（それなんて新月？ とかゆーツッコミは無しでお願いします）。
ファイル検索は全てのインデックスを自分で持つようにすると作るのが簡単そうな気がしました。
（でなければ Gnutella のように周りのノードに伝言ゲームのように聞くか）。
で、試しに手元のファイルをインデックス化したところ、ちょうど１メガバイトになってショックでした。
（１メガのファイルを一定間隔で送受信し合うネットワークなんて嫌だ……。それに 10 人で 10M 100 人で 100M）。
なんとか小さくできないかと Bloom Filter に行きあたったのでした。これって PlanetP と同じなんですね。きっと PlanetP に関する記事が記憶にあったのでしょう。
ちなみに、「HyperEstraier でできる！ ファイル共有ソフト」なんて案もあります。きっとどちらも作らないでしょう（インターフェースまわりがやる気でないし）。
まあですね、httpd や ftpd と各サーバ横断的な検索方法があればファイル共有なんてかんたんですよとか、そんな感じです。
実のところ全然共有じゃないんですけどね。そこは「共有する思想で運営」ってことで。
#次は各ノードの経路制定思考実験。これも PlanetP そのまま真似るかなぁ。
Powered by shinGETsu.