レーベンシュタイン距離

ひと言で

2つの文字列を同じにするのに必要な 「1文字の追加・削除・置換」の最小回数。

たとえば kitten を sitting に変えるには最低3手で済む。

手順	文字列	操作
開始	`kitten`	-
1手目	`sitten`	`k` → `s`（置換）
2手目	`sittin`	`e` → `i`（置換）
3手目	`sitting`	`g` を追加（挿入）

だから kitten と sitting のレーベンシュタイン距離は 3。

なぜ使うか

打ち間違いの検出: appel に一番近い単語は apple（距離1）
表記ゆれや重複データの判定
スペルチェッカー、あいまい検索

距離が小さいほど似ていて、同じ文字列なら 0。

手で計算する

d[i][j] を 「a の先頭 i 文字を b の先頭 j 文字に一致させる最小手数」 と定義する。

1行目 d[0][j] = j … b の j 文字を挿入する手数
1列目 d[i][0] = i … a の i 文字を削除する手数
それ以外は3択の最小値
- 上から: 文字を削除する d[i-1][j] + 1
- 左から: 文字を挿入する d[i][j-1] + 1
- 左上から: 文字を置換する d[i-1][j-1] + cost（同じ文字なら cost = 0）

kitten → sitting の表を埋めると次のようになる。

	””	s	i	t	t	i	n	g
”“	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

右下のマスが答えで 3。どのマスも「そこまでの最小手数」になっている。

Ruby実装

def 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 } # 1列目: 削除だけで一致させる手数
  (0..n).each { |j| d[0][j] = j } # 1行目: 挿入だけで一致させる手数

  (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 # 置換(一致なら0)
      ].min
    end
  end

  d[m][n]
end

[
  ["kitten", "sitting"],
  ["flaw", "lawn"],
  ["abc", "abc"],
  ["", "abc"],
  ["本日", "ほんじつ"],
  ["こんにちは", "こんばんは"]
].each do |a, b|
  puts "#{a.inspect} vs #{b.inspect} => #{levenshtein(a, b)}"
end

実行結果

"kitten" vs "sitting" => 3
"flaw" vs "lawn" => 2
"abc" vs "abc" => 0
"" vs "abc" => 3
"本日" vs "ほんじつ" => 4
"こんにちは" vs "こんばんは" => 2

ポイント

a と b を入れ替えても距離は変わらない（対称）。
空文字との距離は、もう一方の文字数そのもの。
日本語も String#chars で1文字ずつ扱えるので、そのまま動く。
「似ている度合い(0〜1)」が欲しいときは正規化編集距離を使う。

計算量と使いどころ

計算量: 時間 O(mn)、メモリ O(mn)（直前の行だけ残せば O(n)）
用途: スペルチェック、表記ゆれ検出など汎用性が高い
長い文字列では O(n^2) になるため、閾値で枝刈りするかトークン単位で比較する

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