編集距離
今月号のWeb+DB Pressを読んでいたら文字列間の差異の程度を表す編集距離の求め方が載っていた。
ちょっと面白かったので再帰呼び出しでもっと綺麗に書いてみようかなと思ったら、ごちゃごちゃしそうだったので挫折。単なる Perl -> Ruby の移植になってしまった。
module LDist def get_ld another splitter = respond_to?(:split) ? lambda {|e| e.split(//)} : lambda {|e| e} a1, a2 = [self, another].map {|elms| splitter.call(elms)} matrix = Array.new(a1.size + 1) {|i| Array.new(a2.size + 1)} 0.upto(a1.size) {|i| matrix[i][0] = i} 0.upto(a2.size) {|i| matrix[0][i] = i} 1.upto(a1.size) do |i1| 1.upto(a2.size) do |i2| diff = (a1[i1 - 1] == a2[i2 - 1] ? 0 : 1) matrix[i1][i2] = [ matrix[i1 - 1][i2] + 1, matrix[i1][i2 - 1] + 1, matrix[i1 - 1][i2 - 1] + diff ].min end end matrix[a1.size][a2.size] end end str = "abcd" str.extend LDist puts str.get_ld "abdc" puts str.get_ld "ab" puts str.get_ld "abcc" puts '----------------------' arr = [1, 3, 5, 7] arr.extend LDist puts arr.get_ld [2, 3, 5, 7] puts arr.get_ld [7, 5, 3, 1] puts '----------------------' $KCODE = 'u' mstr = "あいうえお" mstr.extend LDist puts mstr.get_ld "あいうえ" puts mstr.get_ld "かきうえこ" puts mstr.get_ld "さしすせそ" puts mstr.get_ld "あえいうえおあお"
一応、配列にも対応。
komamitsu@potato:~/lab/ruby$ ruby ldist.rb 2 2 1 ---------------------- 1 4 ---------------------- 1 3 5 3