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

Я успешно реализовал этап 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 из Кентерберийского корпуса) они работают нормально. На самом деле функция toBWT () даже не нужна.
При применении алгоритмов к двоичным данным из файла, содержащего полный 8-битный алфавит байтов (исполняемый файл и т. Д.), Они, похоже, работают неправильно. Сравнивая результаты алгоритмов с результатами обычных индексов BWT, я замечаю ошибочные индексы (4 в моем случае) спереди. Количество индексов (кстати?) Соответствует глубине рекурсии алгоритмов. Индексы указывают, где исходные исходные данные имели последние вхождения 0 с (до того, как я преобразовал их в 1 с при построении T) …

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

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

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