[B! DP][perl] toocheapjpのブックマーク

toocheapjp id:toocheapjp

DPとperlに関するtoocheapjpのブックマーク (2)

Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを素直に Perl で実装したみた。さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索（あいまい検索）」に使うと便利なalgorithm。実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "
toocheapjp 2009/04/02
algorithm

DP

perl
リンク
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。例えば伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
toocheapjp 2009/03/29
algorithm

NLP

perl

実装

編集距離

DP
リンク
1