以前の記事で、標準化レーベンシュタイン距離(標準化編集距離)というのを紹介し、
自分も使っていたのですが挙動に少し違和感があったので確認しました。
レーベンシュタイン距離はその名の通り、距離関数なのですが、
これを標準化してしまうとどうも距離関数っぽくない動きをしてるように思えたのです。
念の為、距離関数というもの自体の定義をおさらいしておきましょう。
集合$X$に対して、$d:X\times X \rightarrow \mathbb{R}$ が距離関数であるとは、
$x,y,z \in X$に対して次の条件が成り立つ時に言います。
1. $d(x,y) \geq 0$ (非負性)
2. $d(x, y) = 0 \Leftrightarrow x = y$ （同一律）
3. $d(x, y) = d(y, x)$ (対象律)
4. $d(x, z) \leq d(x, y) + d(y, z)$ (三角不等式)
この条件のうち、 1. 2. 3. は特に問題ないのですが、
標準化レーベンシュタイン距離 については、4. の三角不等式がちょっと怪しかったです。
で、反例を探してみたところ簡単に見つかりました。
$ld(*,*)$をレーベンシュタイン距離、$nld(*,*)$を標準化レーベンシュタイン距離とし、
x = ‘ab’, y= ‘aba’, z = ‘ba’ とおきます、
すると、
$ld(x, z) = 2$ なので、$nld(x, z) = 1$ ですが、
$ld(x, y) = ld(y, z) = 1$ なので、$nld(x, y) = nld(y, z) = \frac13$ です。
そのため、 $nld(x, z) > nld(x, y) + nld(y, z) = \frac23$ となり、
三角不等式を満たしません。
標準化レーベンシュタイン距離 は 標準化レーベンシュタイン という名前の距離関数と考えるのは誤りで、
レーベンシュタイン距離 という距離関数を標準化したもの(その結果距離関数ではなくなってしまったもの)と、
考える必要があります。
現状これで激しく困ったということはないのですが、
一部のライブラリにある、自分で作った距離関数を引数に渡せるようなものには、
標準化レーベンシュタイン距離は突っ込まない方が安全そうです。