Обсуждение участника:Сергей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''== Преобразование Барроуза-Уиллера =='''»)
 
 
Строка 1: Строка 1:
−
'''== Преобразование Барроуза-Уиллера =='''
+
== Определение ==
 +
 
 +
{{Определение
 +
|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]

Текущая версия на 01:19, 29 октября 2010

Определение

Определение:
Преобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных.

bzip2 использует преобразование Барроуза-Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана.

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

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

Пусть нам дана исходная строка [math]s = [/math]"ABACABA".

Трансформация
Вход Все
Перестановки 		Сортировка
Строк 		Выход 
ABACABA

ABACABA
BACABAA
ACABAAB
CABAABA
ABAABAC
BAABACA
AABACAB

AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA 

BCABAAA

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


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

Пусть нам дано: [math]BWT(s)=[/math]("BCABAAA", 3). Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:

Обратное преобразование
Вход 
BCABAAA
Добавление 1 Сортировка 1 Добавление 2 Сортировка 2 Добавление 3 Сортировка 3 Добавление 4 
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 
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
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA
Результат 
ABACABA


Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение_участника:Сергей&oldid=4516»