2009-03-01から1ヶ月間の記事一覧

編集距離 (Levenshtein Distance)

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿…

最長共通部分列問題 (Longest Common Subsequence)

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言いま…

第11回 Kansai.pm / スペルミス修正プログラムを作ろう

昨日は第11回 Kansai.pm でした。今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資…

ダイクストラ法, 貪欲アルゴリズム

現実逃避をしながらウェブを眺めていたら ダイクストラ法(最短経路問題) にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションが…

PDL で PageRank

id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使え…

第11回 Kansai.pm を開催します

3月22日(日) 13:30 から、京都ははてなオフィスにて第11回 Kansai.pm を開催します。 http://kansai.pm.org/cgi-bin/wiki.cgi?page=%A5%A4%A5%D9%A5%F3%A5%C8%2F%C2%E811%B2%F3%A5%DF%A1%BC%A5%C6%A5%A3%A5%F3%A5%B0%B9%F0%C3%CE 11回目の Kansai.pm は、無…

Introduction to Information Retrieval #18 の復習資料

Introduction to Information Retrieval 輪読会 18章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_18.ppt 18章のテーマは "Matrix decompositions and latent semantic indexing" で、行列の特異値分解と Latent se…

HITS, 主成分分析, SVD

ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の …