編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
ruby でレーベンシュタイン距離（編集距離）の計算 - Λάδι Βιώσας
なんとなく暇だったので、ruby でレーベンシュタイン距離（編集距離）を求めるコードを書いてみた。編集距離とは、文字列間の類似度を求める方法のことらしいです。詳しくは、wikipedia:レーベンシュタイン距離を見てください。コードはこんな感じ↓。 # doctest: abc and abc # >> levenshtein_distance("abc", "abc") # => 0 # doctest: kitten and sitting # >> levenshtein_distance("kitten", "sitting") # => 3 # doctest: aaaaa and bbbbb # >> levenshtein_distance("aaaaa", "bbbbb") # => 5 def levenshtein_distance(str1, str2) col, r
編集距離が近いメソッドを勝手に呼ぶ - hitode909の日記
メソッド名を打ち間違えてメソッドを呼べないことがあって寂しかったので，呼ぼうとしたメソッドがないときは編集距離が近いメソッドを勝手に呼ぶのを作ってみた． module AutoCall def method_missing(method, *args) __send__(find_nearest_method(method), *args) end private def find_nearest_method(method) methods.sort_by{ |my_method| levenshtein_distance(my_method, method) }.first end # http://d.hatena.ne.jp/kenkitii/20090204/ruby_levenshtein_distance def levenshtein_distance(str1, str2
MySQLでレーベンシュタイン距離を使ったあいまい検索 - eringi.com
Captcha security check eringi.com is for sale Please prove you're not a robot View Price Processing
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
