Изменения

'''Преобразование Барроуза — Уилера''' ('''Burrows-Wheeler transform, BWT''') — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. QQ }}bzip2 использует преобразование Барроуза-Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана.

== Описание алгоритма==

Преобразование выполняется в три этапа. На первом этапе составляется таблица всех циклических сдвигов входной строки. На втором этапе производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. На третьем этапе в качестве выходной строки выбирается последний столбец таблицы преобразованияи номер строки, соответствующей оригиналу. Следующий пример иллюстрирует описанный алгоритм:  == Пример работы алгоритма ==

Результат вкратце запишем можно записать так: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3), где 3 - это номер исходной строки в отсортированной матрице, так как он может понадобиться нужен для обратного преобразования.

Следует заметить, что иногда в исходной строке приводится , так называемый , символ конца строки ''$'', который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.  Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA$"''. {| border="1"!colspan="4"|Трансформация|-! Вход || Все<br />Перестановки || Сортировка<br />Строк || Выход|-| <font color="red">ABACABA$</font>| <font color="red">ABACABA$</font> BACABA$A ACABA$AB CABA$ABA ABA$ABAC BA$ABACA A$ABACAB $ABACABA | <font color="red">ABACABA$</font> ABA$ABAC ACABA$AB A$ABACAB BACABA$A BA$ABACA CABA$ABA $ABACABA| $CBBAAAA|}    При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной : (''"ABACABA$"''). При этом при сортировке матрицы данный символ будет рассматриваться как самый последний после всех символов алфавита. Тогда результат можно записать так : <tex>BWT(s)=</tex>''"$CBBAAAA"''. Он будет эквивалентен первому, так как также содержит все символы исходной строки.