비대칭 Levenshtein 거리

Question

두 비트 열 x와 y가 y보다 길고 y가 주어지면이 두 비트 사이의 Levensthein 거리의 비대칭 변형을 계산하고 싶습니다. x로 시작하여 x를 y로 바꾸는 데 필요한 최소 삭제 및 대체 수를 알고 싶습니다.

일반적인 Levensthein 거리를 사용하거나 알고리즘을 어떻게 수정해야합니까? 즉, 삭제, 대체 및 추가 편집의 일반적인 세트를 사용하면 두 문자열 간의 길이 차이를 삭제 한 다음 비트를 다시 추가하는 것이 도움이됩니까? 나는 그 대답이 '아니오'라고 생각하지만 확실하지 않습니다. 내가 틀렸다면 삭제를 허용하지 않기 위해 Levenshtein 거리의 정의를 수정해야합니까? 어떻게해야합니까?

마지막으로 y (짧은 문자열)로 시작하고 추가 및 대체 만 허용하면 동일한 거리를 얻을 것이라고 직관적으로 기대합니다. 이게 옳은 거니? 나는이 답이 무엇인지에 대한 감각을 가지고있다, 나는 단지 그것들을 증명할 수 없다.

Answer 1

정확하게 이해한다면 대답은 '예'라고 생각합니다. Levenshtein 편집 거리는 더 큰 문자열 만 삭제하고 대체 할 수있는 알고리즘과 다를 수 있습니다. 이 때문에 제한된 버전을 얻으려면 다른 알고리즘을 수정하거나 만들어야합니다.

두 개의 문자열 "ABCD"와 "ACDEF"를 고려하십시오. Levenshtein 거리는 3입니다 (ABCD-> ACD-> ACDE-> ACDEF). 긴 문자열로 시작하고 삭제 및 대체에 제한을두면 4 개의 편집 (1 개의 삭제 및 3 개의 대체)을 사용해야합니다. 그 이유는 작은 문자열에 삭제가 적용되어 큰 문자열로 효율적으로 이동할 수 없기 때문입니다 무료 삽입 작업이 없기 때문에 더 긴 문자열로 시작하면 달성 할 수 있습니다. (허용하지 않으므로)

마지막 단락은 참보다 짧음에서 길음까지의 경로가 삽입 및 대체 만 사용하는 경우, 허용되는 경로는 길고 짧은 방향으로 간단하게 바꿀 수 있습니다. 방향은 상관 없지만 대체는 동일하지만 방향이 바뀔 때 삽입물이 삭제됩니다.

나는 이것을 철저히 테스트하지 않았습니다. b 이 수정은 제가 취할 방향을 보여 주며, 제가 테스트 한 값들과 함께 작동하는 것처럼 보입니다. 그것은 C#으로 작성되었으며 Levenshtein 거리에 대한 wikipedia 항목의 psuedo 코드를 따릅니다. 명백한 최적화가 가능하지만, 그렇게하지 않으므로 표준 알고리즘을 통해 변경 한 사항이 더 분명합니다. 중요한 견해는 문자열이 동일한 길이 인 경우 (제약 조건을 사용하여) 대체가 허용되는 유일한 작업이라는 것입니다.

static int LevenshteinDistance(string s, string t) { 
     int i, j; 
     int m = s.Length; 
     int n = t.Length; 

     // 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)*(n+1) values 
     var d = new int[m + 1, n + 1]; 

     // set each element to zero 
     // c# creates array already initialized to zero 

     // source prefixes can be transformed into empty string by 
     // dropping all characters 
     for (i = 0; i <= m; i++) d[i, 0] = i; 

     // target prefixes can be reached from empty source prefix 
     // by inserting every character 
     for (j = 0; j <= n; j++) d[0, j] = j; 

     for (j = 1; j <= n; j++) { 
      for (i = 1; i <= m; i++) { 
       if (s[i - 1] == t[j - 1]) 
        d[i, j] = d[i - 1, j - 1];  // no operation required 
       else { 
        int del = d[i - 1, j] + 1; // a deletion 
        int ins = d[i, j - 1] + 1; // an insertion 
        int sub = d[i - 1, j - 1] + 1; // a substitution 
        // the next two lines are the modification I've made 
        //int insDel = (i < j) ? ins : del; 
        //d[i, j] = (i == j) ? sub : Math.Min(insDel, sub); 
        // the following 8 lines are a clearer version of the above 2 lines 
        if (i == j) { 
         d[i, j] = sub; 
        } else { 
         int insDel; 
         if (i < j) insDel = ins; else insDel = del; 
         // assign the smaller of insDel or sub 
         d[i, j] = Math.Min(insDel, sub); 
        } 
       } 
      } 
     } 
     return d[m, n]; 
    }