Преобразование Барроуза – Уилера.
Само по себе преобразование Барроуза – Уилера (Burrows Wheeler Transform - BWT) не сжимает данных, размер выходного блока соответствует размеру входного блока, однако оно предназначено для того, чтобы сделать дальнейшее сжатие входного потока более эффективным. Посредством перестановки элементов данное преобразование превращает входной блок данных со сложными зависимостями в блок, структуру которого гораздо проще моделировать, при этом преобразование происходит без потери информации.
Этот метод появился сравнительно недавно. Впервые он был опубликован 10.05.1994 в статье «A Block-sorting Lossless Data Compression Algorithm». Авторами метода являются Дэвид Уилер и Майк Барроуз. Причем, первый из них придумал этот метод еще в 1983 году, но, видимо, либо тогда не придал значения своему открытию, либо посчитал чрезмерными требования к вычислительным ресурсам. Метод был объявлен компромиссным между быстрыми словарными методами и статистическими методами, малоприменимыми в то время на практике.
Авторами предложена следующая последовательность применения алгоритмов:
-
преобразование Барроуза – Уилера;
-
преобразование Move To Front (MTF);
-
статистический кодер.
Необходимо отметить, что данный метод, в отличие от, например метода LZW оперирует блоками данных, поэтому применение его в определенных областях может быть затруднено.
В настоящее время работу алгоритма BWT принято демонстрировать на примере слова «абракадабра»
-
Из исходного слова необходимо составить матрицу всех возможных его циклических перестановок:
абракадабра
бракадабраа
ракадабрааб
акадабраабр
кадабраабра
адабраабрак
дабраабрака
абраабракад
браабракада
раабракадаб
аабракадабр
-
Пометим в этой матрице строку и отсортируем ее по алфавиту:
аабракадабр
абраабракад
Абракадабра
адабраабрак
акадабраабр
браабракада
бракадабраа
дабраабрака
кадабраабра
раабракадаб
ракадабрааб
-
Выписывем символы последнего столбца и номер исходной строки – это и есть результат преобразования.
Рдакраааабб, 2
Доказано, также, что данное преобразование является обратимым, к тому же объем памяти, требуемый для его реализации линейно зависит от размера блока данных. Кратко, суть преобразования состоит в том, что оно собирает вместе все устойчивые взаимосвязи (сочетания) блока данных. Таким образом, чем больше таких сочетаний в исходном блоке данных – тем выше степень сжатия можно получить после BWT.
В качестве методов, наиболее удачно использующих преобразование Барроуза – Уилера, наиболее удачными выглядят следующие:
-
Метод Хаффмана
-
Арифметическое кодирование
-
Метод перемещения стопки книг (MTF)
-
Кодирование длин повторов (RLE)
Метод перемещения стопки книг
Это преобразование также само по себе не сжимает данные, но его реализация в ряде случаев дает ощутимый выигрыш при использовании статистических алгоритмов, в частности, например, преобразования Хаффмана.
Преобразование также известно под названием Move To Front (MTF). Суть его легко понять, если представить себе процесс перемещения книг в стопке, из которой время от времени берут нужную книгу и кладут наверх. Таким образом, наиболее часто используемые книги оказываются ближе к верхушке стопки.
Для примера произведем преобразование над примером, полученным в предыдущей главе после метода BWT. Пусть мы имеем алфавит из пяти букв, в упорядоченном виде они расположены в следующем порядке:
(а, б, д, к, р).
Первый символ из последовательности «р» находится в списке под номером 4, это число мы и записываем в выходной блок. Затем мы изменяем список таким образом, перенося символ «р» в вершину и сдвигая все элементы, находившиеся до него:
(р, а, б, д, к)
Следующий символ «д» оказывается в списке под номером 3. И так далее.
|
Символ |
Список |
Номер |
|
р |
А б д к р |
4 |
|
д |
Р а б д к |
3 |
|
а |
Д р а б к |
2 |
|
к |
А д р б к |
4 |
|
р |
К а д р б |
3 |
|
а |
Р к а д б |
2 |
|
а |
А р к д б |
0 |
|
а |
А р к д б |
0 |
|
а |
А р к д б |
0 |
|
б |
А р к д б |
4 |
|
б |
Б а р к д |
0 |
Таким образом мы получили последовательность:
4 3 2 4 3 2 0 0 0 4 0
К слову, вспомним, что результат преобразования Барроуза – Уилера, как раз и представляет собой последовательность, в которой встречаются часто повторяющиеся символы. Такое преобразование увеличивает эффективность дальнейшего применения статистического кодера. Для сравнения возьмем последовательность с повторяющимися символами:
б б б б в в в в в г г г г г а а а а а б
Попробуем закодировать ее методом Хаффмана. Вероятности всех четырех символов в данной последовательности равны 0.25. Таким образом для кодирования каждого символа нам потребуется по 2 бита. Нетрудно посчитать, что длина выходного кода будет равна:
20 * 2 = 40 бит.
Теперь проделаем то же самое со строкой, подвергнутой MTF преобразованию:
б б б б в в в в в г г г г г а а а а а б
1 0 0 0 2 0 0 0 0 3 0 0 0 0 3 0 0 0 0 3
|
Символ |
Частота |
Вероятность |
Код Хаффмана |
|
0 |
15 |
3/4 |
0 |
|
3 |
3 |
3/20 |
10 |
|
1 |
1 |
1/20 |
110 |
|
2 |
1 |
1/20 |
111 |
В результате кодирования получаем последовательность:
15 * 1 + 3 * 2 + 1 * 3 + 1 * 3 = 27 бит
Таким образом наглядно показан возможный выигрыш при использовании метода MTF для преобразования сжимаемых данных, и, в частности, при использовании совместно с преобразованием Барроуза – Уиллера.
В настоящее время, в различных модификациях и сочетаниях, два алгоритма – метод Хаффмана (или арифметическое кодирование) и метод Лемпеля-Зива – составляют основу всех коммерческих алгоритмов и программ.