7
правок
Изменения
Нет описания правки
== Определение == {{Определение|definition ='''Преобразование Барроуза — Уилера''' ('''Burrows-Wheeler transform, BWT''') — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. }}bzip2 использует преобразование Барроуза-Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана. ==Описание алгоритма= = Преобразование Барроузавыполняется в три этапа. На первом этапе составляется таблица всех циклических сдвигов входной строки. На втором этапе производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. На третьем этапе в качестве выходной строки выбирается последний столбец таблицы преобразования. Следующий пример иллюстрирует описанный алгоритм: Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA"''. {| border="1"!colspan="4"|Трансформация|-! Вход || Все<br />Перестановки || Сортировка<br />Строк || Выход|-| <font color="red">ABACABA</font>| <font color="red">ABACABA</font> BACABAA ACABAAB CABAABA ABAABAC BAABACA AABACAB| AABACAB ABAABAC <font color="red">ABACABA</font> ACABAAB BAABACA BACABAA CABAABA | BCABAAA|} Результат вкрадце запишем так: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3), где 3 -Уиллера это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования. == Обратное преобразование == Пусть нам дано: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3). Тогда выпишем в столбик нашу преобразованную последовательность символов ''"BCABAAA"''. Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем ''"BCABAAA"''. Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.Алгоритм обратного преобразования описан в таблице ниже: {| border="1"!colspan="8"| Обратное преобразование|-!colspan="8"| Вход|-|align="center" colspan="8"| BCABAAA|-! Добавление 1 || Сортировка 1 || Добавление 2 || Сортировка 2 || Добавление 3 || Сортировка 3 || Добавление 4 |-align="right"| B C A B A A A| A A A A B B C| BA CA AA BA AB AB AC| AA AB AB AC BA BA CA| BAA CAB AAB BAC ABA ABA ACA| AAB ABA ABA ACA BAA BAC CAB| BAAB CABA AABA BACA ABAA ABAC ACAB|-! Сортировка 4 || Добавление 5 || Сортировка 5 || Добавление 6 || Сортировка 6 || Добавление 7 || Сортировка 7 |-align="right"| AABA ABAA ABAC ACAB BAAB BACA CABA| BAABA CABAA AABAC BACAB ABAAB ABACA ACABA| AABAC ABAAB ABACA ACABA BAABA BACAB CABAA| BAABAC CABAAB AABACA BACABA ABAABA ABACAB ACABAA| AABACA ABAABA ABACAB ACABAA BAABAC BACABA CABAAB| BAABACA CABAABA AABACAB BACABAA ABAABAC ABACABA ACABAAB| AABACAB ABAABAC <font color="red">ABACABA</font> ACABAAB BAABACA BACABAA CABAABA|- !colspan="8"| Результат|-|align="center" colspan="8"| <font color="red">ABACABA</font>|} == Ссылки ==*[http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0 Преобразование Барроуза — Уилера - Википедия] *[http://www.cs.karelia.ru/~aborod/inf/2010/schedule.php.ru Преобразование Барроуза — Уилера - cs.karelia.ru]
