正規化編集距離
正規化編集距離
ひと言で
レーベンシュタイン距離 を 文字列の長さで割って 0〜1 に収めたもの。
- 類似度
1 - d / max(|a|, |b|)… 1に近いほど似ている - 距離
d / max(|a|, |b|)… 0に近いほど似ている
kitten と sitting は編集距離 3、長いほうは7文字なので、類似度は 1 - 3/7 = 0.5714。
なぜ使うか
- 長さの違う文字列を公平に比べたい
- 「0.8以上なら同じとみなす」のような 閾値 を決めやすい
- 編集距離のままだと、長い文字列ほど値が大きくなって比較しづらい
手で計算する
編集距離 d = 3
長いほうの長さ max(|a|, |b|) = max(6, 7) = 7
類似度 = 1 - 3 / 7 = 0.5714
距離 = 3 / 7 = 0.4286
編集距離は必ず 0 〜 max(|a|, |b|) の範囲に収まるので、max で割れば必ず 0〜1 になる。
| ペア | 編集距離 | 長いほう | 類似度 | 距離 |
|---|---|---|---|---|
abc / abc |
0 | 3 | 1.0000 | 0.0000 |
abc / abd |
1 | 3 | 0.6667 | 0.3333 |
kitten / sitting |
3 | 7 | 0.5714 | 0.4286 |
"" / abc |
3 | 3 | 0.0000 | 1.0000 |
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 }
(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
end
end
d[m][n]
end
def normalized_similarity(a, b)
max = [a.length, b.length].max
return 1.0 if max.zero?
1.0 - (levenshtein(a, b).to_f / max)
end
def normalized_distance(a, b)
max = [a.length, b.length].max
return 0.0 if max.zero?
levenshtein(a, b).to_f / max
end
[
["kitten", "sitting"],
["abc", "abc"],
["abc", "abd"],
["", "abc"],
["こんにちは", "こんばんは"]
].each do |a, b|
puts "#{a.inspect} vs #{b.inspect} => 類似度=#{format('%.4f', normalized_similarity(a, b))}, 距離=#{format('%.4f', normalized_distance(a, b))}"
end
実行結果
"kitten" vs "sitting" => 類似度=0.5714, 距離=0.4286
"abc" vs "abc" => 類似度=1.0000, 距離=0.0000
"abc" vs "abd" => 類似度=0.6667, 距離=0.3333
"" vs "abc" => 類似度=0.0000, 距離=1.0000
"こんにちは" vs "こんばんは" => 類似度=0.6000, 距離=0.4000
ポイント
- 両方とも空文字のときは
0で割ってしまうため、先に1.0/0.0を返す。 - 分母は
maxのほか、minや平均を使う流派もある。用途に合わせて選ぶ。 - 日本語も1文字単位で長さを数えるので、そのまま正規化できる。
- 正規化した値なら、異なる長さのペアを一覧で並べて比較できる。
計算量と使いどころ
- 計算量: 編集距離と同じ
O(mn)、正規化はO(1) - 用途: 名寄せの閾値判定、重複検出、レコードのクラスタリング
- 例: 類似度
0.8以上を「同じ」とみなす、など