レーベンシュタイン距離

ふとレーベンシュタイン距離 (編集距離) の計算を書きたくなったので書いてみた。わりと綺麗に書けたと思った。

def levenshtein_distance(s, t)
  t.chars.with_index.inject(0..s.size) do |r, (a, z)|
    z += 1
    [z] + s.chars.zip(r.each_cons(2)).map do |b, (x, y)|
      z = [y + 1, z + 1, x + (a == b ? 0 : 1)].min
    end
  end.last
end

p levenshtein_distance("kitten", "sitting")   #=> 3
p levenshtein_distance("Saturday", "Sunday")  #=> 3

んー、でも、with_index が 0 origin 固定なのがいまいちですね。あと scanl や mapAccumL が欲しい、かなあ。

やはり Haskell はいい感じ。もっと綺麗に短く書けるかな？

levenshtein_distance :: Eq a => [a] -> [a] -> Int
levenshtein_distance s t = last $ foldl f [0..length s] $ zip t [1..]
  where f r (a, z) = scanl (g a) z $ zip3 s r (tail r)
        g a z (b, x, y) = minimum [y + 1, z + 1, x + fromEnum (a /= b)]

main :: IO ()
main = do
  print $ levenshtein_distance "kitten" "sitting"  -- 3
  print $ levenshtein_distance "Saturday" "Sunday" -- 3