文字列間の距離を見つけるための Wagner-Fischer アルゴリズムを理解しようとしています。次のリンクで疑似コードを調べています: http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
int EditDistance(char s[1..m], char t[1..n])
// For all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t.
// Note that d has (m+1) x(n+1) values.
let d be a 2-d array of int with dimensions [0..m, 0..n]
for i in [0..m]
d[i, 0] ← i // the distance of any first string to an empty second string
for j in [0..n]
d[0, j] ← j // the distance of any second string to an empty first string
for j in [1..n]
for i in [1..m]
if s[i] = t[j] then
d[i, j] ← d[i-1, j-1] // no operation required
else
d[i, j] ← minimum of
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
return d[m,n]
実際、私はアルゴリズムの要点を理解し、直感的に理解しています。なぜなら、d[i-1, j] + 1, d[i, j-1] + 1 と d[i-1, j-1 ] + 1は、削除、挿入、置換と見なされます。誰かが実装のニュアンスをより詳細に説明してくれれば幸いです。