이식 C# Levenshtein Java와의 거리

Question

이 코드 부분을 변경하는 데 도움이 될 수있는 하나의 맞춤법 검사기 응용 프로그램을 개발 중이므로 포인터가 없거나 동등한 글꼴이 없으므로 stackalloc을 Java로 포팅 할 수 없습니다. 정확히 동일한 기능을 가진 자바 메소드.

public static unsafe double GNULevenstein(string word1, string word2) 
    { 
     // this algorithm normally computes un-normalized distance between two string. 
     fixed (char* word1Ptr = word1) 
     fixed (char* word2Ptr = word2) 
     { 
      char* pointerToWord1 = word1Ptr; 
      char* pointerToWord2 = word2Ptr; 

      /* skip equal start sequence, if any */ 
      if (word1.Length >= word2.Length) 
      { 
       while (*pointerToWord1 == *pointerToWord2) 
       { 
        /* if we already used up one string, 
        * then the result is the length of the other */ 
        if (*pointerToWord1 == '\0') break; 
        pointerToWord1++; 
        pointerToWord2++; 
       } 
      } 
      else // wordl < word2 
      { 
       while (*pointerToWord1 == *pointerToWord2) 
       { 
        /* if we already used up one string, 
        * then the result is the length of the other */ 
        if (*pointerToWord2 == '\0') break; 
        pointerToWord1++; 
        pointerToWord2++; 
       } 
      } 

      /* length count #1*/ 
      int len1 = word1.Length - (int)(pointerToWord1 - word1Ptr); 
      int len2 = word2.Length - (int)(pointerToWord2 - word2Ptr); 


      /* if we already used up one string, then 
      the result is the length of the other */ 
      if (*pointerToWord1 == '\0') 
       return ExportResult(len2 , word1.Length,word2.Length , false); 
      if (*pointerToWord2 == '\0') 
       return ExportResult(len1, word1.Length, word2.Length, false); 

      /* length count #2*/ 
      pointerToWord1 += len1; 
      pointerToWord2 += len2; 

      /* cut of equal tail sequence, if any */ 
      while (*--pointerToWord1 == *--pointerToWord2) 
      { 
       len1--; 
       len2--; 
      } 

      /* reset pointers, adjust length */ 
      pointerToWord1 -= len1++; 
      pointerToWord2 -= len2++; 

      /* possible dist to great? */ 
      //if ((len1 - len2 >= 0 ? len1 - len2 : -(len1 - len2)) >= char.MaxValue) return 1; 
      if (Math.Abs(len1 - len2) >= char.MaxValue) 
       return ExportResult(1, false); // no similarity 

      char* tmp; 
      /* swap if l2 longer than l1 */ 
      if (len1 < len2) 
      { 
       tmp = pointerToWord1; 
       pointerToWord1 = pointerToWord2; 
       pointerToWord2 = tmp; 
       len1 ^= len2; 
       len2 ^= len1; 
       len1 ^= len2; 
      } 

      /* fill initial row */ 

      int i, j, n; 

      n = (*pointerToWord1 != *pointerToWord2) ? 1 : 0; 
      char* r = stackalloc char[len1 * 2]; 

      char* p1, p2; 
      for (i = 0, p1 = r; i < len1; i++, *p1++ = (char)n++, p1++) 
      { /*empty*/} 


      /* calc. rowwise */ 
      for (j = 1; j < len2; j++) 
      { 
       /* init pointers and col#0 */ 
       p1 = r + ((j & 1) == 0 ? 1 : 0); 
       p2 = r + (j & 1); 
       n = *p1 + 1; 
       *p2++ = (char)n; p2++; 
       pointerToWord2++; 

       /* foreach column */ 
       for (i = 1; i < len1; i++) 
       { 
        if (*p1 < n) n = *p1 + (*(pointerToWord1 + i) != *pointerToWord2 ? 1 : 0); /* replace cheaper than delete? */ 
        p1++; 
        if (*++p1 < n) n = *p1 + 1; /* insert cheaper then insert ? */ 
        *p2++ = (char)n++; /* update field and cost for next col's delete */ 
        p2++; 
       } 
      } 

      /* return result */ 
      return ExportResult(n - 1, word1.Length, word2.Length, false); 
     } 


    } 

Answer 1

이 방법은 C#으로 작성하는 대신 C/C++에서 느리게 이식 된 것처럼 보입니다. C#에서 문자열 조작 방금 Levenshtein distance의 자바 구현을 원하는처럼

난 그냥 메소드 이름을 봤

은, 그래서, 보이는 ... 보통 unsafe을 사용하고 char*의 직접 작업하는 시간과 노력의 낭비임을 충분히 빨리이다 , 같은 링크에서 :

public class LevenshteinDistance { 
     private static int minimum(int a, int b, int c) { 
       return Math.min(Math.min(a, b), c); 
     } 

     public static int computeLevenshteinDistance(CharSequence str1, 
         CharSequence str2) { 
       int[][] distance = new int[str1.length() + 1][str2.length() + 1]; 

       for (int i = 0; i <= str1.length(); i++) 
         distance[i][0] = i; 
       for (int j = 1; j <= str2.length(); j++) 


       distance[0][j] = j; 

      for (int i = 1; i <= str1.length(); i++) 
        for (int j = 1; j <= str2.length(); j++) 
          distance[i][j] = minimum(
              distance[i - 1][j] + 1, 
              distance[i][j - 1] + 1, 
              distance[i - 1][j - 1] 
                  + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 
                      : 1)); 

      return distance[str1.length()][str2.length()]; 
    } 
}