Преобразование Барроуза-Уилера

Определение

Определение:

Преобразование Барроуза — Уилера (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 - это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования.

Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки $, который в преобразовании будет считаться последним символом, тогда сохранение номера исходной строки не требуется. При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной ("ABACABA$"). При этом при сортировке матрицы данный символ будет рассматриваться как самый последний после всех символов алфавита. Тогда результат можно записать так [math]BWT(s)=[/math]"$CBBAAAA". Он будет эквивалентен первому, так как также содержит все символы исходной строки.

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

Наивный алгоритм

Пусть нам дано: [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

Следует также заметить, что если нам было бы дано [math]BWT(s)=[/math]"$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки $ на конце: ABACABA$.

Как несложно посчитать сложность данного алгоритма [math]O(N^3logN) [/math], также он требует [math]O(N^2)[/math] памяти.

Оптимизация

Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. Мы приписывали новый столбец и сортировали имеющиеся данные. На каждом шагу мы к строке, которая находилась на [math] i [/math]-ом месте приписываем в начало [math] i [/math] -ый элемент столбца входных данных. Пусть изначально мы знаем каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из предыдущего шага какое место занимала наша строка без этого первого символа ([math] i [/math] -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером [math] i [/math] всегда будет перемещаться на позицию с номером [math] j [/math].

0	а		р	9
1	а		д	7
2	а		a	0
3	а		к	8
4	а		р	10
5	б		a	1
6	б		a	2
7	д		a	3
8	к		a	4
9	р		б	5
10	р		б	6

Здесь слева это отсортированный данный столбец, чтобы мы знали какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку мы в нашем алгоритме новый столбец приписываем в начало, то мы из состояния [math] i [/math] (левый столбец) переходим в состояние [math] j [/math] (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из [math] j [/math] в [math] i [/math] восстановить строку.

6 → 10 → 4 → 8 → 3 → 7 → 1 → 5 → 9 → 0 → 2 а б р а к а д а б р а Сложность оптимизированного алгоритма Данный алгоритм работает за [math]O(NlogN)[/math] действий и требует [math]O(N)[/math] памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за [math]O(N+M)[/math] действий и требует [math]O(N+M)[/math] памяти, где [math]M[/math] — размер алфавита. Псевдокод оптимизированного алгоритма Пусть [math] N [/math] — количество символов во входной строке, [math] M [/math] — количество символов в алфавите, [math] k [/math] — номер исходной строки в матрице перестановок, [math] s [/math] — входящая строка, [math] count [/math] — массив для сортировки подсчетом, [math] t [/math] — вектор обратного преобразования, [math] x [/math] — номер данной нам строки в таблице. // Cчитаем частоты символов for i = 0 .. M count[i] = 0 for i = 0 .. N count[s[i]]++ // Упорядочиваем символы, чтобы получить первый столбец исходной матрицы // count[i] указывает на первую позицию символа i в первом столбце sum = 0 for i = 0 .. M sum = sum + count[i] count[i] = sum - count[i] // Cоздаем вектор обратного преобразования for i = 0 .. N t[count[s[i]]] = i count[s[i]]++ // И восстанавливаем исходный текст j = t[x] for i = 0 .. N print(s[j]) j = t[j] Ссылки Преобразование Барроуза — Уилера (Википедия) Преобразование Барроуза — Уилера (cs.karelia.ru)