ダメラウ・レーベンシュタイン距離

ひと言で

レーベンシュタイン距離に 「隣り合う2文字の入れ替え（転置）」を1手 として加えたもの。

ab を ba にする場合を比べると差が分かる。

手法	手順	距離
レーベンシュタイン	`a` → `b`、`b` → `a`（置換2回）	2
ダメラウ・レーベンシュタイン	`ab` → `ba`（入れ替え1回）	1

なぜ使うか

キーボード入力では、隣の文字を入れ替えてしまう打ち間違いが多い。

teh → the
recieve → receive
こんにちわ → こんにちは

この「入れ替え」を1手と数えたいときに使う。

手で計算する

基本はレーベンシュタインと同じで、d[i][j] を求めたあとに 入れ替えの候補 を追加する。

a = "ab", b = "ba"

a の i 文字目と b の j 文字目が入れ替わっている、
つまり a[i-1] == b[j-2] かつ a[i-2] == b[j-1] のとき

d[i][j] = min(d[i][j], d[i-2][j-2] + 1)   # 入れ替え1回

ab → ba の表を埋めると次のようになる。

	””	b	a
”“	0	1	2
a	1	1	1
b	2	1	1

右下のマスは、通常の計算だと 2 になるが、入れ替えの候補 d[0][0] + 1 = 1 が採用されて 1 になる。

Ruby実装

def damerau_levenshtein(a, b)
  a = a.chars
  b = b.chars
  m = a.size
  n = b.size
  d = Array.new(m + 1) { Array.new(n + 1, 0) }
  (0..m).each { |i| d[i][0] = i }
  (0..n).each { |j| d[0][j] = j }

  (1..m).each do |i|
    (1..n).each do |j|
      cost = a[i - 1] == b[j - 1] ? 0 : 1
      d[i][j] = [
        d[i - 1][j] + 1,       # 削除
        d[i][j - 1] + 1,       # 挿入
        d[i - 1][j - 1] + cost # 置換
      ].min

      # 隣り合う2文字の入れ替え
      if i > 1 && j > 1 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1]
        d[i][j] = [d[i][j], d[i - 2][j - 2] + 1].min
      end
    end
  end

  d[m][n]
end

[
  ["ab", "ba"],
  ["kitten", "sitting"],
  ["こんにちは", "こんばんは"],
  ["abc", "abc"]
].each do |a, b|
  puts "#{a.inspect} vs #{b.inspect} => #{damerau_levenshtein(a, b)}"
end

実行結果

"ab" vs "ba" => 1
"kitten" vs "sitting" => 3
"こんにちは" vs "こんばんは" => 2
"abc" vs "abc" => 0

ポイント

入れ替えを1手と数えるぶん、レーベンシュタイン距離より 同じか小さい値 になる。
上の実装は OSA (Optimal String Alignment) 版 と呼ばれる簡易版で、入れ替えの重ね掛けを考慮しない。厳密なダメラウ・レーベンシュタイン距離はさらに小さい値を返すことがある（例: ca と abc は OSA=3、厳密=2）。
実用上は OSA 版で十分なことが多い。厳密版が必要なら last occurrence テーブルを使う実装にする。

計算量と使いどころ

計算量: 時間 O(mn)、メモリ O(mn)
用途: キーボードの打ち間違い補正、名寄せ
入れ替えを考慮しないなら、まずはレーベンシュタイン距離で十分

前: レーベンシュタイン距離

次: ハミング距離