Использование алгоритма массива суффиксов для преобразования Берроуза-Уилера

Я успешно реализовал этап BWT (используя обычную сортировку строк) для тестового стенда сжатия, который я пишу. Я могу применить BWT, а затем обратное преобразование BWT, и результат будет соответствовать входу. Теперь я хотел ускорить создание индексной таблицы BW с помощью массивов суффиксов. Я нашел 2 относительно простых, предположительно быстрых алгоритма O(n) для создания массива суффиксов, DC3 и SA-IS, которые поставляются с исходным кодом C++/C. Я пытался использовать исходники (готовый исходный код для компиляции SA-IS также можно найти здесь), но не удалось получить правильный массив суффиксов/таблицу индексов BWT. Вот что я сделал:

1. T = входные данные, SA = выходной массив суффиксов, n = размер T, K = размер алфавита, BWT = индексная таблица BWT

2. Я работаю с 8-битными байтами, но обоим алгоритмам нужен уникальный маркер Sentinel/EOF в виде нулевого байта (DC3 нужно 3, SA-IS нужен один), поэтому я конвертирую все свои входные данные в 32-битные целые числа, увеличиваю все символы на 1 и добавить нулевые байты дозорного. Это т.

3. Я создаю целочисленный выходной массив SA (размером n для DC3, n+1 для KA-IS) и применяю алгоритмы. Я получаю результаты, аналогичные моему BWT-преобразованию сортировки, но некоторые значения нечетные (см. ОБНОВЛЕНИЕ 1). Также результаты обоих алгоритмов немного различаются. Алгоритм SA-IS создает избыточное значение индекса в начале, поэтому все результаты необходимо копировать слева на один индекс (SA[i]=SA[i+1]).

4. Чтобы преобразовать массив суффиксов в правильные индексы BWT, я вычитаю 1 из значений массива суффиксов, делаю по модулю и должен иметь индексы BWT (согласно это): BWT[i]=(SA[i]-1)%n.

Это мой код для подачи алгоритмов SA и преобразования в BWT. Вы должны быть в состоянии более или менее просто подключить код построения SA из документов:

std::vector<int32_t> SuffixArray::generate(const std::vector<uint8_t> & data)
{
    std::vector<int32_t> SA;
    if (data.size() >= 2)
    {
        //copy data over. we need to append 3 zero bytes, 
        //as the algorithm expects T[n]=T[n+1]=T[n+2]=0
        //also increase the symbol value by 1, because the algorithm alphabet is [1,K]
        //(0 is used as an EOF marker)
        std::vector<int32_t> T(data.size() + 3, 0);
        std::copy(data.cbegin(), data.cend(), T.begin());
        std::for_each(T.begin(), std::prev(T.end(), 3), [](int32_t & n){ n++; });
        SA.resize(data.size());
        SA_DC3(T.data(), SA.data(), data.size(), 256);

        OR

        //copy data over. we need to append a zero byte, 
        //as the algorithm expects T[n-1]=0 (where n is the size of its input data)
        //also increase the symbol value by 1, because the algorithm alphabet is [1,K] 
        //(0 is used as an EOF marker)
        std::vector<int32_t> T(data.size() + 1, 0);
        std::copy(data.cbegin(), data.cend(), T.begin());
        std::for_each(T.begin(), std::prev(T.end(), 1), [](int32_t & n){ n++; });
        SA.resize(data.size() + 1); //crashes if not one extra byte at the end
        SA_IS((unsigned char *)T.data(), SA.data(), data.size() + 1, 256, 4); //algorithm expects size including sentinel
        std::rotate(SA.begin(), std::next(SA.begin()), SA.end()); //rotate left by one to get same result as DC3
        SA.resize(data.size());
    }
    else
    {
        SA.push_back(0);
    }
    return SA;
}

void SuffixArray::toBWT(std::vector<int32_t> & SA)
{
    std::for_each(SA.begin(), SA.end(), [SA](int32_t & n){ n = ((n - 1) < 0) ? (n + SA.size() - 1) : (n - 1); });
}

Что я делаю неправильно?

ОБНОВЛЕНИЕ 1
При применении алгоритмов к небольшим объемам тестовых текстовых данных, таких как "yabbadabbado" / "это тест". / "abaaba" или большой текстовый файл (alice29.txt из корпуса Canterbury) они работают отлично. На самом деле функция toBWT() даже не нужна.
При применении алгоритмов к двоичным данным из файла, содержащего полный 8-битный байтовый алфавит (исполняемый файл и т. д.), кажется, что они работают некорректно. Сравнивая результаты алгоритмов с обычными индексами BWT, я замечаю ошибочные индексы (4 в моем случае) впереди. Количество индексов (кстати?) соответствует глубине рекурсии алгоритмов. Индексы указывают на то, где исходные исходные данные имели последние вхождения 0 (до того, как я преобразовал их в 1 при построении T)...

ОБНОВЛЕНИЕ 2
При двоичном сравнении обычного массива BWT и массива суффиксов различаются другие значения. Этого можно было ожидать, так как честная сортировка не обязательно должна быть такой же, как при стандартной сортировке, НО результирующие данные, преобразованные массивами, должны быть одинаковыми. Это не.

ОБНОВЛЕНИЕ 3
Я пытался изменить простую строку ввода до тех пор, пока оба алгоритма не «сработали». После изменения двух байтов строки «это тест». до 255 или 0 (от 74686973206973206120746573742Eh до, например, 746869732069732061FF74657374FFh, последний байт необходимо изменить!) индексы и преобразованная строка больше неверны. Также кажется достаточным изменить последний символ строки на символ, уже встречающийся в строке, например. "это тесты" 746869732069732061207465737473ч. Затем два индекса и два символа преобразованных строк будут заменены местами (сравнивая обычную сортировку BWT и BWT, использующую SA).

Я нахожу весь процесс преобразования данных в 32-битный формат немного неудобным. Если у кого-то есть лучшее решение (бумага, еще лучше, какой-нибудь исходный код) для генерации массива суффиксов НЕПОСРЕДСТВЕННО из строки с 256-символьным алфавитом, я был бы счастлив.