Берроуз-Уилер двинуться вперед - PullRequest
Новая
       7

Берроуз-Уилер двинуться вперед

1 голос
/ 30 июля 2009

Для проекта, над которым я работаю, мне нужно реализовать преобразование Берроуз-Уилера MoveToFront в пространстве O (n). Однако по какой-то причине мой код работает с большинством значений, которые я к нему добавляю, но не со всеми.

Моя реализация выглядит примерно так: 

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

Какой-нибудь совет, что я здесь делаю не так? Кажется, что это не работает, когда встречаются не алфавитно-цифровые символы (то есть кодирование само по себе, кажется, что / * и т. Д. Испортят его).

1 Ответ

1 голос
/ 30 июля 2009

После запуска различных тестов для этого кода он выглядит так, как будто работает правильно. Проблемы, которые вы видите, возможно, связаны с расширением знака в реализации 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 никогда не достигается. Я получил java.lang.StackOverflowError с входным массивом длиной 5214. Я бы предложил изменить это на итеративное, а не рекурсивное (это должно быть довольно просто, так как вы знаете длину входного массива, и это также предотвратит лишние циклы патологический случай, когда все байты во входном массиве равны).

...