Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
はてなダイアリー日記 - リンクスコアシステムの変更につきまして
本日、はてなダイアリーのキーワードリンクシステムのリンクスコア（キーワードをダイアリーからリンクするか、しないかの閾値を決める投票システム）の変更を行いました。変更内容は以下のとおりです。 リンクスコアをキーワード単位から言葉（単語）単位に変更 はてなダイアリーキーワードシステムでは、同音異義語に対応するため、同じ言葉に対して複数のキーワードを登録できます（たとえば「abc」という言葉に対しては「初歩を意味する言葉」と「放送局名」といった複数のキーワード情報が登録されています）。そして、これまでリンクスコアはそれぞれのキーワードごとに投票できるようになっておりました。つまり「初歩を意味する言葉」には「リンク可」に投票し「放送局名」には「リンク不可」と投票することが可能でした。しかし、キーワードリンクのシステムでは、日記内で使われた言葉に対してリンクが張られ、その文脈の解釈は行っておりません
Rabin Karp アルゴリズムでコード重複の検出 blog.bulknews.net
Rabin Karp アルゴリズムでコード重複の検出 YAPC::NA で会った Fotango の Norman Nunley がつくってる Algorithm::RabinKarp モジュールが面白げです。 Rabin Karp 文字列探索アルゴリズム (wikipedia) を使って文字列のハッシュ（ダイジェスト）をチェックし、同一の値を示す部分を重複しているとみなしてレポートしてくれます。つまり、プロジェクト内のコードのコピーペーストを検出するツールとして使えるというわけ。 ためしに Plagger で試してみた結果は rabin.txt のようになりました。プラグインの register_hook や CustomFeed での Feed オブジェクトの生成など、イディオム的に使う部分が大半になってしまっていますが、いくつか実際コピペで再利用しているコードが検出できています。 c
ITmedia News：アルゴリズム検索はもう限界か
インターネットの進化を振り返ると、その発展の過程はニューヨークのマンハッタン島の歴史とよく似ている。どちらも最初に住所システムが作られた。片や碁盤目状のストリート（東西方向）とアベニュー（南北方向）、片や8ビットの数字で表されるツリー構造のIPネットとサブネットだ。この2つの体系的な住所システムは、どちらも後に、名前による場所の表記が組み合わされた。前者では地下鉄の駅名、後者ではDNSディレクトリだ。 だが現状では、この豊かで多様などちらの空間でも、そこに詳しい人以外が一般に目にするものは、そのリソースのごく一部に限られてしまっている。よそからニューヨークを訪れる人は観光ガイドに相談するし、一般のインターネットユーザーは、Googleが検索結果の最初のページに表示するものしか見ないからだ（4月26日の記事参照）。どちらの場合も、見えない力が選択肢を狭め、ほとんどのユーザーは排除された選択肢
キーワード置換アルゴリズム - ita’s diary
http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 うわーこれはこまったね。いままでは長いキーワードから抜き出していってたけど、TRIE 構造を使って文の前方からマッチを探して行くから短いのが優先されたりする。たとえば 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさしという文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かきく」が抽出される。マッチがあっても何文字か進む間保留しとくとかの方法で解決できるのかな。LZ圧縮とかも辞書にマッチするパターンを番号で置き換えるとかしてると思ったんで、標準的なアルゴリズム何かあるんじゃないかねぇ。 追記：LZ系は保留はしない模様。ふーむ。 とりあえず、n文字のマッチがあった場合、これを候補１として仮採用し、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www2.muroran-it.ac.jp/circle/mpc/program/algorithm/index.html
