2 바이트 배열의 가장 긴 공통 부분 시퀀스

Question

두 파일의 LCS를 이진 파일과 비교하기 위해 일반적인 LCS 소스 코드를 사용하고 GenStr 명령을 사용하여 파일의 바이트를 먼저 String으로 변경했습니다. 문자열을 비교하는 한계가 있으므로 바이트를 저장하는 배열을 사용하려고 계획하고 있으므로이 문자열을 비교하는 것이 문제입니다. LCS 알고리즘을 사용하여 두 바이트 배열을 비교할 수 있습니까?

편집 :

내가했지만,이 사용되거나 사용되지 않을 수 있는지 여부 때문에 일부 오류를 확인하지 못하고

public static byte[] Compare(byte[] x, byte[] y) { 

    int i, j; 
    final int x_length = x.length; 
    final int y_length = y.length; 
    int n = 2048; 
    int m = 2048; 


    // D[i][j] = direction, L[i][j] = Length of LCS 
    int[][] D = new int[n + 1][m + 1]; 
    byte[][] L = new byte[n + 1][m + 1]; // { 1, 2, 3 } 

    // D[i][0] = 0 for 0<=i<=n 
    // D[0][j] = 0 for 0<=j<=m 
    for (i = 1; i <= n; i++) { 
     for (j = 1; j <= m; j++) { 
      if (x[i - 1] == y[j - 1]) { 
       D[i][j] = D[i - 1][j - 1] + 1; 
       L[i][j] = 1; 
      } else if (D[i - 1][j] >= D[i][j - 1]) { 
       D[i][j] = D[i - 1][j]; 
       L[i][j] = 2; 
      } else { 
       D[i][j] = D[i][j - 1]; 
       L[i][j] = 3; 
      } 
     } 
    } 

    // Backtrack 
    ByteArrayOutputStream lcs = new ByteArrayOutputStream(); 
    i = n; 
    j = m; 
    while (i != 0 && j != 0) { 
     switch (L[i][j]) { 
      case 1: // diagonal 
       lcs.write(x[i - 1]); // Unreversed LCS 
       --i; 
       --j; 
       break; 
      case 2: // up 
       --i; 
       break; 
      case 3: // backward 
       --j; 
       break; 
     } 
    } 
    byte[] result = lcs.toByteArray(); 

    // Reverse: 
    for (i = 0, j = result.length - 1; i < j; ++i, --j) { 
     byte b = result[i]; 
     result[i] = result[j]; 
     result[j] = b; 
    } 
    return result; 

    //While not end of file 
    while(n < x_length && m < y_length){ 
     if(n+2048 < x.length){ 
      n = n+2048; 
     } else { 
      n = x.length; 
     } 

     if(m+2048 < y.length){ 
      m = m+2048; 
     } else { 
      m = y.length; 
     } 

    // D[i][j] = direction, L[i][j] = Length of LCS 
    int[][] D_new = new int[n + 1][m + 1]; 
    byte[][] L_new = new byte[n + 1][m + 1]; // { 1, 2, 3 } 

    // D[i][0] = 0 for 0<=i<=n 
    // D[0][j] = 0 for 0<=j<=m 
    for (i = i+2048; i <= n; i++) { 
     for (j = j+2048; j <= m; j++) { 
      if (x[i - 1] == y[j - 1]) { 
       D_new[i][j] = D_new[i - 1][j - 1] + 1; 
       L_new[i][j] = 1; 
      } else if (D_new[i - 1][j] >= D_new[i][j - 1]) { 
       D_new[i][j] = D_new[i - 1][j]; 
       L_new[i][j] = 2; 
      } else { 
       D_new[i][j] = D_new[i][j - 1]; 
       L_new[i][j] = 3; 
      } 
     } 
    } 

    // Backtrack 
    ByteArrayOutputStream lcs_next = new ByteArrayOutputStream(); 
    i = n; 
    j = m; 
    while (i != 0 && j != 0) { 
     switch (L[i][j]) { 
      case 1: // diagonal 
       lcs_next.write(x[i - 1]); // Unreversed LCS 
       --i; 
       --j; 
       break; 
      case 2: // up 
       --i; 
       break; 
      case 3: // backward 
       --j; 
       break; 
     } 
    } 
    byte[] result_new = lcs_next.toByteArray(); 

    // Reverse: 
    for (i = 0, j = result_new.length - 1; i < j; ++i, --j) { 
     byte b = result_new[i]; 
     result_new[i] = result_new[j]; 
     result_new[j] = b; 
    } 
    return result_new; 
    Arrays.fill(D_new, null); 
    Arrays.fill(L_new, null); 
    Arrays.fill(result_new, null); 
    lcs_next.reset(); 
} 
} 

.

질문 :

1. 가 어떻게 라인 (return result) 및 라인 (return result_new)의 LCS를 추가합니까?
2. 어떻게 다른 입력을 반복해서 사용할 수 있도록 배열을 지우시겠습니까? (Array.fill(D_new, null) 및 Array.fill(L_new, null)) 작동하지 않습니까?

대신 byte 배열을 사용하여 당신을 막을 거기에 아무것도 미리

Answer 1

에 감사드립니다. 이것은 int 배열의 메모리의 절반을 사용하지만 그 중 최대 값이 인 경우는 Integer.MAX_VALUE입니다. RAM이 부족하지만 길이 제한을 초과하지 않는 경우이 방법을 사용하면 시간을 절약 할 수 있습니다.

파일에서 오는 것이라면 어쨌든해야합니다. 정말로 전체 문자열로 읽지 않아야합니다. 바이트별로 읽으십시오.

파일 크기가 2GB 이상인 경우이 작업을 수행하는 올바른 방법은 미리 파일을 읽는 대신 이동하면서 파일을 처리하는 것입니다. 또한 파일을 사용하여 LCS 데이터를 저장합니다. 당신이 만들고 있어요. 알고리즘에 대한 좋은 점은 모든 액세스가 지역화되어 있다는 것입니다. 즉, 입력 파일을 순차적으로 스캔하므로 사전에 읽을 필요가 없습니다. 새로운 값을 계산할 때 이전 행과 현재 행만을 고려하여 순차적으로 배열을 상당히 가깝게 작성합니다 (따라서 RAM에 두는 것으로 많은 이득을 얻지 못합니다).

이렇게하면 파일을 임의로 확장 할 수 있습니다. 그러면 CPU 시간이 결정적인 요소가됩니다. 디스크 캐시는 파일을 먼저 읽고 RAM에서 수행함으로써 얻을 수있는 것과 동일한 성능을 제공합니다.

Answer 2

알고리즘을 고려하지 않은 변환.

자바에서 new은 0/0.0/false/null로 초기화됩니다.

반면에 lcs에 선행하는 것은 out-of-the-box로 수행 될 수 없습니다. 그러나 배열을 뒤집는 것은 간단합니다.

public static byte[] compare(byte[] x, byte[] y) { 
    int i, j; 
    final int n = x.length; 
    final int m = y.length; 
    /* D[i][j] = direction, L[i][j] = Length of LCS */ 
    int[][] D = new int[n + 1][m + 1]; 
    byte[][] L = new byte[n + 1][m + 1]; // { 1, 2, 3 } 

    /* D[i][0] = 0 for 0<=i<=n */ 
    /* D[0][j] = 0 for 0<=j<=m */ 
    for (i = 1; i <= n; i++) { 
     for (j = 1; j <= m; j++) { 
      if (x[i - 1] == y[ - 1]) { 
       D[i][j] = D[i - 1][j - 1] + 1; 
       L[i][j] = 1; 
      } else if (D[i - 1][j] >= D[i][j - 1]) { 
       D[i][j] = D[i - 1][j]; 
       L[i][j] = 2; 
      } else { 
       D[i][j] = D[i][j - 1]; 
       L[i][j] = 3; 
      } 
     } 
    } 

    /* Backtrack */ 
    ByteArrayOutputStream lcs = new ByteArrayOutputStream(); 
    i = n; 
    j = m; 
    while (i != 0 && j != 0) { 
     switch (L[i][j]) { 
      case 1: /* diagonal */ 
       lcs.write(x[i - 1]); // We want lcs reversed though. 
       --i; 
       --j; 
       break; 
      case 2: /* up */ 
       --i; 
       break; 
      case 3: /* backward */ 
       --j; 
       break; 
     } 
    } 
    byte[] result = lcs.toByteArray(); 
    // Reverse: 
    for (i = 0, j = result.length - 1; i < j; ++i, --j) { 
     byte b = result[i]; 
     result[i] = result[j]; 
     result[j] = b; 
    } 
    return result; 
}