Bloom filterの説明 — ありえるえりあ
Bloom filterの説明 以前、bloom filterに言及したことがあるのですが、実は、言及しただけで何も調べていませんでした。 来週、ある人の話を聞く時、知らないとついていけない可能性があるので、調べてみました。 - 参考サイト 感想ですが、予想以上にシンプルでした。 動作イメージ(だけ)は誰でもイメージできます(実装も簡単)。 上の参考サイトも、英語に気後れせず、図だけでも見てください。動作は想像できるはずです。そして、たぶん、その想像は当たっています。 参考サイトを読めば分かることを日本語で改めて説明するのも気がひけますが、どうしても英語を読みたくない人のために、簡単に説明してみます。 動作イメージ あ る入力文書が与えられたとして、後で、その文書に、ある単語fooが存在するかを高速にチェックしたい、という問題を想定するのが理解しやすいと思いま す。入力文書に対する前処理を
検索と挿入がともにO(1)であるようなHashを作るにはコツがいる
このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言っておくがおまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。 言葉と前提とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、 class Hash { typedef lis
ベイジアンフィルター Perlで作りたい人に教えてあげたいちょっとしたこと - プログラマでありたい
昨日のはてなのホットエントリーに『入門ベイズ統計』の読みどころという記事が載っていました。ベイズ理論の人気は根強いですね。 ベースとしての数式は割とシンプルなので、自分で実装してもそれ程手間は掛からないかもしれません。しかし、CPANのモジュールとして提供されているので、そちらを使用するのも良いかと思います。私が知っている所では、Algorithm::NaiveBayesが簡単で使いやすかったです。 昔書いたコードですが、下のサンプルでは簡単なスパムフィルターを作っています。spam.txtとham.txtは、それぞれのコーパスを形態素解析して作った単語のみのリストです。test.txtは、判定したい文章から抽出した単語のリストです。スパムとハムの量を増やせば、これだけでも割と使い物になります。 応用例としては、スパムとハムの2種類のカテゴリだけではなく、複数種類のカテゴリを作ればブログの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
