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：脇IndexedByte.compareTo内MAXIMUM = 50000制限に達することがないよう

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

：

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

はにコードを変更してみてください。私はjava.lang.StackOverflowErrorの長さ5214の入力配列を持っています。これを反復的ではなく反復的に変更することをお勧めします（これは、入力配列の長さを知っているので非常に簡単であり、病理学的なケースでの余分なループも防ぎます）入力配列内のすべてのバイトが等しい）。