Преобразование Берроуза-Уилера (BWT) - сохраненные данные

Question

После использования BWT, какой набор данных нам нужен в закодированных данных? Нужно ли кодировать (или экспортировать) суффиксный массив?

Входные данные:

stackru

BWT выход:

wtavrcfkle$soo

Суффиксный массив:

13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12

Answer 1

Суффиксный массив необходим только для вычисления bwt-преобразования, после завершения преобразования его можно удалить.

BWT("stackru")="wtavrcfkle$soo"

UNBWT("wtavrcfkle$soo")="stackru"

Вы также можете восстановить массив суффиксов из преобразованного вывода, если хотите:)

Answer 2

Все, что вам нужно, чтобы инвертировать преобразование, это строка вывода (wtavrcfkle$soo в твоем примере).

Answer 3

Чтобы полностью изменить BWT, вам нужен только индекс исходного последнего символа, а не весь массив суффиксов. Если у вас нет этого индекса, я думаю, что выбор произвольного индекса приведет к повороту версии вашей исходной строки.

Обратите внимание, что если вы включите код конца строки (как в вашем примере), оригинальный последний символ очевиден, поэтому указатель не нужно указывать отдельно...

Answer 4

Вам нужно только передать выход BWT.

Удивительная вещь в этом преобразовании состоит в том, что исходная строка может быть восстановлена ​​только из переставленной выходной строки.

Статья в Википедии содержит пример кода для выполнения этого обратного.

Обратите внимание, что нормальным режимом работы является использование кодирования длины серии для кодирования BWT-вывода перед передачей (или вы не достигли какого-либо сжатия).

Хорошая вещь о преобразовании состоит в том, что он имеет тенденцию производить длинные серии похожих символов (если в исходном материале есть структура), и поэтому кодирование длины серий работает хорошо.

Answer 5

Чтобы было понятно, массив суффиксов и вывод BWT - это одно и то же. Если вы посмотрите на массив суффиксов в вашем примере, он содержит индексы букв в выводе BWT, взятые из входа BWT (начиная с 1): 13 -> w, 2 -> t, 3 -> a и т. Д... Использование суффиксного массива - это всего лишь механизм для расчета выходных данных BWT за линейное время. Передача суффиксного массива или вывода BWT означает передачу одной и той же информации.