7
правок
Изменения
Новая страница: «== Определение == {{Определение |definition = '''Преобразование Барроуза — Уилера''' ('''Burrows-Wheeler transfo…»
== Определение ==
{{Определение
|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]
{{Определение
|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]
