[an error occurred while processing the directive]BWT-кодинг[an error occurred while processing the directive]
<html>
<title>404 Not Found</title>
<style>html{color-scheme:light dark;}</style>
</head>
<body>
<center><h1>404 Not Found</h1></center>
<hr><center>Angie</center>
</body>
</html>

[an error occurred while processing the directive]

<h1 align=center>BWT-кодинг</h1>

<b>Автор:</b> <a href="http://forum.sources.ru/index.php?showuser=10169"><i>Мяут</i></a>

<h2>Преобразование Бэрроуза-Уиллера</h2>
<p>Преобразование Бэрроуза-Уиллера (Burrows-Wheeler Transform, далее BWT) появилось достаточно недавно (статья "A Block-sorting Lossless Data Compression Algorithm" была опубликована в 1994 году), хотя, как принято считать, у одного из авторов - Майкла Уиллера - идеи использовать сортировку в алгоритмах компрессии появились еще в 80-х, однако тогда методу не было найдено применения.</p>
<p>Сам по себе, BWT не является алгоритмом сжатия, однако выходная последовательность гораздо удобнее для сжатия, нежели исходная. Для лучших результатов, поверх кодированной последовательности применяется Move-to-Front, а затем алгоритм сжатия Хаффмана или арифметическое кодирование. В частности, связка BWT+Huff используется в популярном формате архивов BZIP2. По степени компрессии он уступает лишь PPM (который, кстати, медленнее работает) Давайте обратимся к самому алгоритму, рассмотрим его поведение на примере слова "математика".</p>
<p>Алгоритм действует блочно, профессионалы в области сжатия рекомендуют использовать размер буфера 1-2 KB. Затем полученный блок подвергают циклическим перестановкам, записывая результаты в список:</p>
<pre class="code">
	char* trans_matrix = (char*) malloc(size*size); //наш список
    for(int I=0; I&lt;size; I++) {
        memcpy(trans_matrix+I*size, src+I, size-I); //Циклическая перестановка на I позиций
        memcpy(trans_matrix+I*size+size-I, src, I);
    }
</pre>

<p>В итоге получается следующее:</p>
<pre>
математика
 атематикам
  тематикама
   ематикамат
    матикамате
     атикаматем
      тикаматема
       икаматемат
        каматемати
         аматематик
</pre>

<p>Заметим, что два слова, начинающиеся на "а", заканчиваются на "м". Еще два слова - аналогичная пара: "т"-"а". Сблизим эти строчки. Для этого применим сортировку в лексикографическом порядке (я использовал сортировку методом Шелла, хотя подойдет любой другой метод, даже быстрая сортировка из стандартной библиотеки C, хотя по скорости она проигрывает):</p>
<pre class="code">
	tmsort(trans_matrix, size, size, size);
</pre>

<p>Мы получили следующий список:</p>
<pre>
аматематик
атематикам
атикаматем
ематикамат
икаматемат
каматемати
математика <-- 6
матикамате
тематикама
тикаматема
</pre>

<p>Выберем из этого списка исходную строку, а также сохраним все заключительные буквы:</p>
<pre class="code">
	for(int I=0; I&lt;size; I++) {
        dst[I] = *(trans_matrix+I*size+size-1);

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

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

<h2>Обратное преобразование.</h2>
<p>Давайте запишем оставшиеся у нас данные:</p>
<pre>
.........к
.........м
.........м
.........т
.........т
.........и
.........а
.........е
.........а
.........а
</pre>

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

а........к
а........м
а........м
е........т
и........т
к........и
м........а
м........е
т........а
т........а
</pre> 

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

ам.......к
ат.......м
ат.......м
ем.......т
ик.......т
ка.......и
ма.......а
ма.......е
те.......а
ти.......а 
</pre>

<p>И так далее. В конечном итоге мы получаем оригинальную последовательность.</p>
<p>К сожалению сам по себе алгоритм не очень проворен, однако он был серьезно ускорен Джулианом Сэвардом (разработчиком архивного формата BZIP2). Как это сделать вы можете прочитать в следующих документах:</p>
<br>
<div class="info">
Julian Seward "On the Performance of BWT Sorting Algorithms"<br>
Julian Seward "Space-time Tradeoffs in the Inverse B-W Transform"<br>
</div>

<hr>
Скачать исходник: <a href="./bwt/bwt_source.rar">bwt_source.rar</a> (1 кБ)

[an error occurred while processing the directive]