BWT-кодинг

Преобразование Бэрроуза-Уиллера

Преобразование Бэрроуза-Уиллера (Burrows-Wheeler Transform, далее BWT) появилось достаточно недавно (статья "A Block-sorting Lossless Data Compression Algorithm" была опубликована в 1994 году), хотя, как принято считать, у одного из авторов - Майкла Уиллера - идеи использовать сортировку в алгоритмах компрессии появились еще в 80-х, однако тогда методу не было найдено применения.

Сам по себе, BWT не является алгоритмом сжатия, однако выходная последовательность гораздо удобнее для сжатия, нежели исходная. Для лучших результатов, поверх кодированной последовательности применяется Move-to-Front, а затем алгоритм сжатия Хаффмана или арифметическое кодирование. В частности, связка BWT+Huff используется в популярном формате архивов BZIP2. По степени компрессии он уступает лишь PPM (который, кстати, медленнее работает) Давайте обратимся к самому алгоритму, рассмотрим его поведение на примере слова "математика".

Алгоритм действует блочно, профессионалы в области сжатия рекомендуют использовать размер буфера 1-2 KB. Затем полученный блок подвергают циклическим перестановкам, записывая результаты в список:

	char* trans_matrix = (char*) malloc(size*size); //наш список
    for(int I=0; I<size; I++) {
        memcpy(trans_matrix+I*size, src+I, size-I); //Циклическая перестановка на I позиций
        memcpy(trans_matrix+I*size+size-I, src, I);
    }

В итоге получается следующее:

математика
 атематикам
  тематикама
   ематикамат
    матикамате
     атикаматем
      тикаматема
       икаматемат
        каматемати
         аматематик

Заметим, что два слова, начинающиеся на "а", заканчиваются на "м". Еще два слова - аналогичная пара: "т"-"а". Сблизим эти строчки. Для этого применим сортировку в лексикографическом порядке (я использовал сортировку методом Шелла, хотя подойдет любой другой метод, даже быстрая сортировка из стандартной библиотеки C, хотя по скорости она проигрывает):

	tmsort(trans_matrix, size, size, size);

Мы получили следующий список:

аматематик
атематикам
атикаматем
ематикамат
икаматемат
каматемати
математика <-- 6
матикамате
тематикама
тикаматема

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

	for(int I=0; I<size; I++) {
        dst[I] = *(trans_matrix+I*size+size-1);

        if(memcmp(trans_matrix+I*size, origin, size)==0)
            str_no = I;
    }

В итоге мы получили: 6кммттиаеаа.

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

Обратное преобразование.

Давайте запишем оставшиеся у нас данные:

.........к
.........м
.........м
.........т
.........т
.........и
.........а
.........е
.........а
.........а

Так как происходили циклические преобразования, то у нас остались буквы в том же количестве, в котором они ыли в слове. Также мы знаем, что оригинальная матрица была лексикографически отсортирована, значит, если мы отсортируем оставшиеся у нас буквы, то получим верную последовательность:

кммттиаеаа -> аааеикммтт

а........к
а........м
а........м
е........т
и........т
к........и
м........а
м........е
т........а
т........а

Далее составляются последовательности, состоящие из последней буквы и начала строки, сортируются, и вбираются соответствующие буквы

ка, ма, ма, те, ти, ик, ам, ем, ат, ат
ам, ат, ат, ем, ик, ка, ма, ма, те, ти

ам.......к
ат.......м
ат.......м
ем.......т
ик.......т
ка.......и
ма.......а
ма.......е
те.......а
ти.......а 

И так далее. В конечном итоге мы получаем оригинальную последовательность.

К сожалению сам по себе алгоритм не очень проворен, однако он был серьезно ускорен Джулианом Сэвардом (разработчиком архивного формата BZIP2). Как это сделать вы можете прочитать в следующих документах: