Burrows-Wheeler passe à l'avant

Question

Pour un projet sur lequel je travaille, je dois implémenter la transformation MoveToFront de Burrows-Wheeler dans l'espace O (n). Pour une raison quelconque, cependant, mon code fonctionne sur la plupart des valeurs que je lui lance, mais pas sur toutes.

Mon implémentation ressemble à ceci:

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;
}

Un conseil sur ce que je fais mal ici? Il semble que cela ne fonctionne pas lorsqu'un caractère non alphanumérique est rencontré (c'est-à-dire qu'il se codifie lui-même, il semble que le / *, etc. le bousillera).

Answer 1

Après avoir exécuté divers tests sur ce code, il semble que cela fonctionne correctement. Les problèmes que vous rencontrez sont probablement dus à une extension de signature dans l'implémentation byteArrayToInt . Par exemple, le code suivant imprime -128 plutôt que le 128 attendu:

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

Essayez de remplacer le code par:

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

De plus, la limite MAXIMUM = 50000 dans IndexedByte.compareTo n'est jamais atteinte. J'ai un java.lang.StackOverflowError avec un tableau en entrée de longueur 5214. Je suggérerais de changer cela pour qu'il soit itératif plutôt que récursif (cela devrait être assez facile, car vous connaissez la longueur du tableau en entrée Cela évitera également les boucles superflues dans le cas pathologique où tous les octets du tableau en entrée sont égaux).