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

Я успешно реализовал этап 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 символов, я был бы счастлив.

6

Решение

Теперь я понял это. Мое решение было двояким. Некоторые люди предложили использовать библиотеку, что я и сделал SAIS облегченный Юта Мори.
Реальным решением было дублировать и объединить входную строку и запустить SA-генерацию для этой строки. При сохранении выходной строки необходимо отфильтровать все индексы SA выше исходного размера данных. Это не идеальное решение, потому что вам нужно выделить вдвое больше памяти, дважды скопировать и выполнить преобразование для двойного объема данных, но это все еще на 50-70% быстрее, чем std :: sort. Если у вас есть лучшее решение, я хотел бы услышать это.
Вы можете найти обновленный код Вот.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]