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

ウィキペディア小見出し辞書

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/25 09:06 UTC 版)

「ダメラウ・レーベンシュタイン距離」の記事における「ダメラウ・レーベンシュタイン距離と制限ダメラウ・レーベンシュタイン距離」の解説

同じ文字列を2度以上編集することを許さない条件のもとで求められる編集距離を制限編集距離と呼ぶ。制限編集距離は最適文字列整列距離と呼ばれる量に一致することが知られている。この条件を課さない（つまり同じ文字列を1回より多く編集してよい）場合には、単に編集距離と呼ぶ。制限レーベンシュタイン距離は常にレーベンシュタイン距離に一致する。これは、レーベンシュタイン距離の計算では編集操作は1文字ごとであり、1度編集した文字列を2度編集する必要がないからである。しかし2文字の編集操作が存在するダメラウ・レーベンシュタイン距離に関しては、制限ダメラウ・レーベンシュタイン距離とダメラウ・レーベンシュタイン距離とが一致しない場合がある。 例として、CAとABCの編集距離を求める。CAに1回の隣接文字交換および1回の文字挿入を施せば CA → AC → ABC となるから、ダメラウ・レーベンシュタイン距離は LD ⁡ ( CA , ABC ) = 2 である。これに対して、制限距離（あるいは最適文字列整列距離 Optimal String Alignment, OSA）を求めるための編集は1回の文字削除に続いて2回の文字挿入を施す CA → A → AB → ABC であり、制限距離は OSA ⁡ ( CA , ABC ) = 3 {\textstyle \operatorname {OSA} ({\text{CA}},{\text{ABC}})=3} である。ダメラウ・レーベンシュタイン距離を求めるときに使った編集 CA → AC → ABC が使えないのは、B を挿入する時点で同じ文字列を2回編集しており、この編集は制限距離を求める操作では禁止されているからである。制限距離については、三角不等式が一般には成立しないことに注意する。実際、 OSA ⁡ ( CA , AC ) + OSA ⁡ ( AC , ABC ) < OSA ⁡ ( CA , ABC ) である。つまり制限距離は計量ではない。 ここでは計算が簡単な制限ダメラウ・レーベンシュタイン距離を求める。文字列 a {\textstyle a} の先頭から数えて i {\textstyle i} 番目の1文字を a [ i ] {\textstyle a[i]} とし、 a {\textstyle a} の先頭から i {\textstyle i} 番目までの長さ i {\textstyle i} の部分文字列を a [ 1 , i ] {\textstyle a[1,i]} とする。2つの文字列 a および b {\textstyle b} の間の制限ダメラウ・レーベンシュタイン距離を定義するためにまず、文字列 a {\textstyle a} の部分文字列 a [ 1 , i ] {\textstyle a[1,i]} と、 b {\textstyle b} の部分文字列 b [ 1 , j ] {\textstyle b[1,j]} の間の制限距離関数 d a , b ⁡ ( i , j ) {\textstyle \operatorname {d} _{a,b}(i,j)} を、次のように再帰的に定義する： :A:11 d a , b ⁡ ( i , j ) = min { 0 if  i = j = 0 d a , b ⁡ ( i − 1 , j ) + 1 if  i > 0 d a , b ⁡ ( i , j − 1 ) + 1 if  j > 0 d a , b ⁡ ( i − 1 , j − 1 ) + 1 ( a [ i ] ≠ b [ j ] ) if  i , j > 0 d a , b ⁡ ( i − 2 , j − 2 ) + 1 if  i , j > 1  and  a [ i ] = b [ j − 1 ]  and  a [ i − 1 ] = b [ j ] ここで 1 ( a [ i ] ≠ b [ j ] ) {\textstyle 1_{(a[i]\neq b[j])}} は、 a [ i ] = b [ j ] {\textstyle a[i]=b[j]} のとき 0 {\textstyle 0} になり、それ以外の場合に 1 {\textstyle 1} となる指示関数である。これらの場合分けはそれぞれ、次に示す部分文字列末尾の編集操作（あるいは編集操作しないこと）に対応している： 0 {\textstyle 0} ：2つの長さ 0 {\textstyle 0} の文字列を一致させるのに必要な編集回数は 0 {\textstyle 0} d a , b ⁡ ( i − 1 , j ) + 1 {\textstyle \operatorname {d} _{a,b}(i-1,j)+1} ： a [ 1 , i ] {\textstyle a[1,i]} が、 a [ 1 , i − 1 ] {\textstyle a[1,i-1]} に1回の挿入をすることで得られたと見なして編集回数を 1 {\textstyle 1} だけ増やす d a , b ⁡ ( i , j − 1 ) + 1 ： b [ 1 , j ] {\textstyle b[1,j]} が、 b [ 1 , j − 1 ] {\textstyle b[1,j-1]} に1回の挿入をすることで得られたと見なして編集回数を 1 {\textstyle 1} だけ増やす d a , b ⁡ ( i − 1 , j − 1 ) + 1 ( a [ i ] ≠ b [ j ] ) {\textstyle \operatorname {d} _{a,b}(i-1,j-1)+1_{(a[i]\neq b[j])}} ： a [ i ] {\textstyle a[i]} と b [ j ] {\textstyle b[j]} が一致する場合には、 a [ 1 , i ] {\textstyle a[1,i]} と b [ 1 , j ] {\textstyle b[1,j]} の間の距離は a [ 1 , i − 1 ] {\textstyle a[1,i-1]} と b [ 1 , j − 1 ] {\textstyle b[1,j-1]} の間の距離に等しいので編集回数を変更しない。 a [ i ] {\textstyle a[i]} と b [ j ] {\textstyle b[j]} が一致しない場合には、 a [ i ] {\textstyle a[i]} を b [ j ] {\textstyle b[j]} に、あるいは b [ j ] {\textstyle b[j]} を a [ i ] {\textstyle a[i]} に置換したと見なして編集回数を 1 {\textstyle 1} だけ増やす d a , b ⁡ ( i − 2 , j − 2 ) + 1 {\textstyle \operatorname {d} _{a,b}(i-2,j-2)+1} ： a [ i ] = b [ j − 1 ] {\textstyle a[i]=b[j-1]} かつ a [ i − 1 ] = b [ j ] {\textstyle a[i-1]=b[j]} のとき、 a [ i − 1 ] {\textstyle a[i-1]} と a [ i ] {\textstyle a[i]} の交換、あるいは a [ i − 1 ] {\textstyle a[i-1]} と a [ i ] {\textstyle a[i]} の交換をしたと見なして編集回数を 1 {\textstyle 1} 回だけ増やす a {\textstyle a} と b {\textstyle b} の間の制限ダメラウ・レーベンシュタイン距離は、文字列全体の関数値 d a , b ⁡ ( | a | , | b | ) {\textstyle \operatorname {d} _{a,b}(|a|,|b|)} で与えられる。ここで | a | {\textstyle |a|} および | b | {\textstyle |b|} はそれぞれ文字列 a {\textstyle a} および b {\textstyle b} の長さ（文字数）である。