1

私が取り組んでいるプロジェクトでは、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;
}

私がここで間違っていることについて何かアドバイスはありますか？英数字以外の文字が検出された場合、これは機能しないようです（つまり、それ自体をエンコードする場合、/ *などがそれを台無しにするようです）。

4

1 に答える 1

1

このコードでさまざまなテストを実行すると、正しく機能しているように見えます。表示されている問題は、おそらくbyteArrayToInt実装の符号拡張が原因です。たとえば、次のコード-128は期待どおりではなく出力され128ます。

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

コードを次のように変更してみてください。

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

余談ですが、MAXIMUM = 50000範囲内の制限にIndexedByte.compareTo達することはありません。長さ5214の入力配列を使用しましたjava.lang.StackOverflowError。これを再帰的ではなく反復的に変更することをお勧めします（入力配列の長さがわかっているので、これはかなり簡単です。また、病理学的な場合の余分なループを防ぐことができます。入力配列のすべてのバイトは等しい）。

于 2009-07-30T16:00:23.037 に答える