Введение

Алгоритм, используемый в методах сжатия данных. Преобразование Бэрроуза — Уилера (BWT, также называемое блочной сортировкой) переупорядочивает строку символов, группируя одинаковые символы вместе. Это полезно для сжатия, поскольку строки с последовательностями повторяющихся символов обычно легко сжимаются с помощью таких методов, как преобразование "перемещение в начало" и кодирование длин серий. Важно отметить, что преобразование обратимо и не требует хранения дополнительных данных, кроме позиции первого исходного символа. Таким образом, BWT является "бесплатным" способом повышения эффективности алгоритмов сжатия текста, требующим лишь дополнительных вычислительных затрат. Преобразование Бэрроуза — Уилера — это алгоритм, используемый для подготовки данных для использования с методами сжатия данных, такими как bzip2. Он был изобретен Майклом Бэрроузом и Дэвидом Уилером в 1994 году, когда Бэрроуз работал в исследовательском центре DEC Systems в Пало-Альто, Калифорния. Он основан на ранее неопубликованном преобразовании, открытом Уилером в 1983 году. Алгоритм может быть эффективно реализован с использованием суффиксного массива, что позволяет достичь линейной временной сложности.

Оптимизация

Ряд оптимизаций может повысить эффективность этих алгоритмов без изменения выходных данных. Нет необходимости представлять таблицу ни в кодировщике, ни в декодировщике. В кодировщике каждая строка таблицы может быть представлена одним указателем на строки, а сортировка может выполняться с использованием индексов. В декодировщике также нет необходимости хранить таблицу, и, фактически, сортировка вообще не требуется. Декодированная строка может быть сгенерирована по одному символу за раз справа налево за время, пропорциональное размеру алфавита и длине строки. "Символ" в алгоритме может быть байтом, битом или любым другим удобным размером. Также можно отметить, что математически закодированная строка может быть вычислена как простое изменение суффиксного массива, а суффиксные массивы могут быть вычислены за линейное время и с линейным использованием памяти. BWT может быть определена относительно суффиксного массива SA текста T (с использованием 1-й индексации) как:

Нет необходимости в фактическом символе 'EOF'. Вместо этого можно использовать указатель, который запоминает, где в строке находился бы 'EOF', если бы он существовал. В этом подходе выходные данные BWT должны включать как преобразованную строку, так и конечное значение указателя. Обратное преобразование затем восстанавливает исходный размер: ему передается строка и указатель, и он возвращает только строку. Полное описание алгоритмов можно найти в статье Берроуза и Уилера или в ряде онлайн-источников.

Динамическая трансформация BurrowsWheeler

Когда текст редактируется, его преобразование Бёрроуза — Уилера изменяется. Сальсон и др. предлагают алгоритм, который выводит преобразование Бёрроуза — Уилера отредактированного текста из преобразования исходного текста, выполняя ограниченное число локальных перестановок в исходном преобразовании Бёрроуза — Уилера, что может быть быстрее, чем непосредственное построение преобразования Бёрроуза — Уилера для отредактированного текста.

BWT для сжатия изображения

Трансформация Берроуза–Уиллера оказалась фундаментальной для приложений сжатия изображений. Например, была продемонстрирована схема сжатия, основанная на применении трансформации Берроуза–Уиллера, за которым следуют инверсия, кодирование длин серий и арифметическое кодирование. Схема, разработанная в этом случае, известна как трансформация Берроуза–Уиллера с инверсионным кодировщиком (BWIC). Результаты, полученные с помощью BWIC, превосходят производительность сжатия широко известных и используемых алгоритмов, таких как Lossless JPEG и JPEG 2000. Показано, что BWIC обеспечивает меньший размер сжатия рентгеновских медицинских изображений на 5,1% и 4,1% соответственно, по сравнению с этими алгоритмами. Улучшения достигаются за счет комбинирования BWIC и предварительного сканирования изображения перед BWIC в вертикальном змеевидном порядке. В последнее время другие работы, такие как, показали, что реализация трансформации Берроуза–Уиллера в сочетании с известной трансформацией "перемещение в начало" (MTF) позволяет достичь почти без потерь сжатия изображений.

BWT для сжатия геномных баз данных

Кокс и др. представили схему геномного сжатия, использующую BWT в качестве алгоритма, применяемого на первом этапе сжатия нескольких геномных наборов данных, включая информацию о геноме человека. В их работе было предложено, что сжатие BWT можно улучшить, добавив механизм сжатия второй ступени, называемый "такой же, как предыдущее кодирование" ("SAP"), который использует тот факт, что суффиксы из двух или более префиксных символов могут совпадать. Используя механизм сжатия BWT SAP, Кокс и др. показали, что в геномной базе данных ERA015743 размером 135,5 ГБ схема сжатия BWT SAP сжимает набор данных ERA015743 примерно на 94%, до 8,2 ГБ.

BWT для предсказания последовательности

BWT также доказал свою эффективность в задаче предсказания последовательностей, которая является распространенной областью исследований в машинном обучении и обработке естественного языка. В частности, Ktistakis и др. предложили схему предсказания последовательностей под названием SuBSeq, использующую возможность беспотеристого сжатия данных, обеспечиваемую преобразованием Бэрроуза-Уиллера. SuBSeq использует BWT, извлекая FM-индекс, а затем выполняя последовательность операций – backwardSearch, forwardSearch, neighbourExpansion и getConsequents – для поиска предсказаний на основе суффикса. Полученные предсказания затем классифицируются по весу и помещаются в массив, из которого выбирается элемент с максимальным весом в качестве предсказания, выдаваемого алгоритмом SuBSeq. Показано, что SuBSeq превосходит современные алгоритмы предсказания последовательностей как по времени обучения, так и по точности.