制限ダメラウ・レーベンシュタイン距離とは？ わかりやすく解説

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

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

制限ダメラウ・レーベンシュタイン距離は、レーベンシュタイン距離を計算するワグナー・フィッシャー動的計画法アルゴリズムを単純に拡張することで計算できる。その擬似コードは： algorithm OSA-distance is input: strings a[1..length(a)], b[1..length(b)] output: distance, integer let d[0..length(a), 0..length(b)] // d は整数二次元配列で次元は length(a)+1, length(b)+1 // ここでは d は添字が 0 から始まる配列であり、a と b は添字が 1 から始まる配列であることに注意する for i := 0 to length(a) inclusive do d[i, 0] := i for j := 0 to length(b) inclusive do d[0, j] := j for i := 1 to length(a) inclusive do for j := 1 to length(b) inclusive do if a[i] = b[j] then cost := 0 else cost := 1 d[i, j] := minimum(d[i-1, j] + 1, // 削除 d[i, j-1] + 1, // 挿入 d[i-1, j-1] + cost) // 置換 if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then // 隣接文字交換：ここから d[i, j] := minimum(d[i, j], d[i-2, j-2] + cost) // 隣接文字交換：ここまで return d[length(a), length(b)] レーベンシュタイン距離を求めるアルゴリズムとの違いは、隣接文字交換にあたる計算が含まれる点である。

※この「制限ダメラウ・レーベンシュタイン距離」の解説は、「ダメラウ・レーベンシュタイン距離」の解説の一部です。
「制限ダメラウ・レーベンシュタイン距離」を含む「ダメラウ・レーベンシュタイン距離」の記事については、「ダメラウ・レーベンシュタイン距離」の概要を参照ください。