Burrows-Wheeler 앞으로 이동

Question

내가 작업하고있는 프로젝트의 경우 O (n) 공간에서 Burrows-Wheeler의 MoveToFront 변환을 구현해야합니다. 그러나 어떤 이유로 든 내 코드는 대부분의 값에 대해 작동하지만 모든 값에 대해서는 작동하지 않습니다.

public byte[] transform (byte[] input) 
{ 
    if (input.length == 0) 
     return input; 
    IndexedByte[] bytes = new IndexedByte[input.length]; 
    for (int i = 0; i < input.length; i++) 
    { 
     bytes[i] = new IndexedByte(input[i],i); 
    } 
    for (int i = 0; i < input.length -1; i++) 
    { 
     bytes[i].next = bytes[i+1]; 
    } 
    bytes[input.length - 1].next = bytes[0]; 
    Arrays.sort(bytes); 

    byte[] newBytes = new byte[input.length]; 
    for (int i = 0; i < bytes.length; i++) 
     newBytes[i] = bytes[i].b; 

    int[] indexes = new int[input.length]; 
    for (int i = 0; i < indexes.length; i++) 
     indexes[i] = (bytes[i].origIndex + (input.length - 1)) % input.length; 
    int x = 0; 
    String str = new String(input); 
    for (int i = 0; i < input.length; i++) 
    { 
     if (bytes[i].origIndex == 0) 
     { 
      x = i; 
      break; 
     } 
    } 
      byte[] header = intToByteArray(x); 
    byte[] result = new byte[indexes.length+header.length]; 
    for (int i = 0; i < header.length; i++) 
     result[i] = header[i]; 
    for (int i = 0; i < indexes.length; i++) 
     result[i+header.length] = input[indexes[i]]; 
    return result; 
} 

내가 잘못 여기서 뭘하는지에 대한 조언 :

내 구현은 다음과 같이 보입니다? 영숫자가 아닌 문자가 발견되면 (즉, 인코딩 자체가/* 등으로 표시 될 때) 이것이 작동하지 않는 것으로 보입니다.

Answer 1

이 코드에서 여러 가지 테스트를 실행 한 후에 올바르게 작동하는 것처럼 보입니다. 보고있는 문제는 byteArrayToInt 구현의 부호 확장 때문일 수 있습니다. 예를 들어, 다음 코드를 인쇄 -128보다는이 128 예상 :

System.out.println(byteArrayToInt(intToByteArray(128))); 

은에 코드를 변경해보십시오 : IndexedByte.compareTo 내 옆 MAXIMUM = 50000 한계에 도달되지 않습니다

private int byteArrayToInt(byte[] b) { 
    return (b[0] << 24) + 
      ((b[1] & 0xFF) << 16) + 
      ((b[2] & 0xFF) << 8) + 
      (b[3] & 0xFF); 
} 

으로. 나는 길이 배열 5214의 입력 배열을 가진 java.lang.StackOverflowError을 가지고있다. 나는 이것을 재귀 적이기보다는 반복적 인 것으로 바꿀 것을 제안한다. (이것은 입력 배열의 길이를 알기 때문에 상당히 쉽다. 또한 병리학 적 케이스에서 불필요한 반복을 막을 것이다. 입력 배열의 모든 바이트가 동일한 경우).