2010-08-28 文字列の一致度を計算する memo 昔、GNU diffのアルゴリズムを解説した文章*1でみた図の感じで、「文字列がどれだけ一致するか」を調べることはできないか、といろいろ探した結果をメモ。 この値はwikipedia:レーベンシュタイン距離というらしい。各種言語での実装*2もあるけど、apache commons lang *3にもあるそうな。 *1:印刷したの、まだ持っているはず *2:http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance *3:http://commons.apache.org/lang/