반복 버전은

Question

Levenshtein 거리를 반복적으로 두 개의 행이 방법을 사용하여 계산 될 수있다 : 나는 조옮김 고려 않는 Optimal String alignment distance 통해 온

https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

. 위키 백과는 일반 Levenshtein 알고리즘의 간단한 확장 기능을 사용하여 계산 될 수 있다고 말한다 :

if i > 1 and j > 1 and a[i-1] = b[j-2] and a[i-2] = b[j-1] then 
    d[i, j] := minimum(d[i, j], 
         d[i-2, j-2] + cost) // transposition 

는 그러나, 나는 반복 버전의 코드에 해당 페이지의 의사 코드 알고리즘의 확장 포트에 수 아니에요. 어떤 도움이라도 대단히 감사합니다.

Answer 1

당신은 내가 코드를 확인할 수 없습니다,이 새로운 버전을 계산하기 위해 세 개의 행이 필요하지만 난 그것에 대해 매우 확신합니다 :

int DamerauLevenshteinDistance(string s, string t) 
{ 
// degenerate cases 
if (s == t) return 0; 
if (s.Length == 0) return t.Length; 
if (t.Length == 0) return s.Length; 

// create two work vectors of integer distances 
int[] v0 = new int[t.Length + 1]; 
int[] v1 = new int[t.Length + 1]; 
int[] v2 = new int[t.Length + 1]; 

// initialize v0 (the previous row of distances) 
// this row is A[0][i]: edit distance for an empty s 
// the distance is just the number of characters to delete from t 
for (int i = 0; i < v0.Length; i++) 
    v0[i] = i; 

    // compute v1 

    v1[0] = 0; 

    // use formula to fill in the rest of the row 
    for (int j = 0; j < t.Length; j++) 
    { 
     var cost = (s[0] == t[j]) ? 0 : 1; 
     v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost); 
    } 

if (s.Length == 1) { 
    return v1[t.Length]; 
} 

for (int i = 1; i < s.Length; i++) 
{ 
    // calculate v2 (current row distances) from the previous rows v0 and v1 

    // first element of v2 is A[i+1][0] 
    // edit distance is delete (i+1) chars from s to match empty t 
    v2[0] = i + 1; 

    // use formula to fill in the rest of the row 
    for (int j = 0; j < t.Length; j++) 
    { 
     var cost = (s[i] == t[j]) ? 0 : 1; 
     v2[j + 1] = Minimum(v2[j] + 1, v1[j + 1] + 1, v1[j] + cost); 
     if (j > 0 && s[i] = t[j-1] && s[i-1] = t[j]) 
      v2[j + 1] = Minimum(v2[j+1], 
        v0[j-1] + cost); 
    } 

    // copy v2 (current row) to v1 (previous row) and v1 to v0 for next iteration 
    for (int j = 0; j < v0.Length; j++) 
     v0[j] = v1[j]; 
     v1[j] = v2[j]; 
} 

return v2[t.Length]; 
} 

원래 코드는 위에서 언급 한 위키 피 디아 구현에서오고있다.