Преобразование Бэрроуза - Уилера
(Burrows - Wheeler Transformation)

В середине 90-х Бэрроузом и Уилером была опубликована статья о новом алгоритме сжатия информации (здесь и далее будет подразумеваться сжатие без потерь), основанного на сортировке блоков данных.

Стоит отметить, что алгоритм был открыт еще в 80-е годы (Bell Labs), но ему не придали значения, считая арифметическое кодирование и алгоритмы сжатия по словарю решением проблемы исчерпывающей "упаковки" данных (к тому же практическая реализация была затруднена отсутствием эффективных сортировок структур с большой длиной элементов).

С математической точки зрения поведение алгоритма Бэрроуза - Уилера (BWT) толком еще не изучено, но статистические исследования показывают, что длина обрабатываемого блока должна быть не менее 1-2 килобайт (чем больше - тем лучше, но при условии его однородности).

Работу алгоритма рассмотрим на примере преобразования слова "ЛОГОВО" :-)

-- Строим матрицу циклических сдвигов исходного блока (на 0 символов влево в первой строке, на 1 символ влево во второй и т.д.)
1. ЛОГОВО
2. ОГОВОЛ
3. ГОВОЛО
4. ОВОЛОГ
5. ВОЛОГО
6. ОЛОГОВ
-- Отсортируем строки в лексикографическом порядке
5. ВОЛОГО
3. ГОВОЛО
1. ЛОГОВО
4. ОВОЛОГ
2. ОГОВОЛ
6. ОЛОГОВ
-- Запомним номер строки, в которой стоит рассматриваемый блок (слово "ЛОГОВО"). В нашем случае - это третья строка ("Save" = 3)
1. ВОЛОГО
2. ГОВОЛО
3. ЛОГОВО
4. ОВОЛОГ
5. ОГОВОЛ
6. ОЛОГОВ
-- Склеивая значение "Save" и последний столбец отсортированной матрицы ("ОООГЛВ"), получаем результат работы BWT: "3ОООГЛВ".

Не стоит пугаться увеличения размера блока, в реальной ситуации (блок в 1-2 Кб) добавление одного символа несущественно по сравнению с выигрышем, получаемым от применения BWT.

Как мы видим, одинаковые символы сгруппировались - не подумайте, что это случайность :-) Доказательство лежит тут.

Получившаяся последовательность символов хорошо сжимается ... нет, не алгоритмом RLE как многие, наверное, подумали :-) а применением арифметического кодера (модель Шеннона или Хаффмана) после несложного преобразования, именуемого в народе MTF (move-to-front).

MTF используется для повышения вероятности (веса) повторяющихся символов. Так, после BWT преобразования, мы будем иметь строку с большим числом групп из идущих друг за другом одинаковых символов, например "...aaabbbaaaccc...". MTF преобразует это слово в "...1--2--1--3--..." (догадайтесь, по какому принципу действует MTF :) Цифры "1", "2" и "3" - это порядковые номера символов, стоящих на данном месте в исходной строке, в условном алфавите (в нашем случае, таким алфавитом является "a,b,c"). Чем больше таких групп, тем выше вероятность символа "-" в преобразованной строке - как следствие меньшее число бит, выделяемых арифметическим кодером под этот символ, что влечет меньший размер сжатой строки.

Проблематика алгоритма BWT

Главной проблемой в реализации BWT является выбор быстрого алгоритма сортировки данных с большой длиной ключа. Отметим, что прямые методы в данной ситуации проблему не решают: алгоритм поразрядной сортировки, имеющий линейную сложность k·O(n), вырождается в O(n2) - не трудно представить, сколько времени у него уйдет на сортировку хотя бы 65 тысяч элементов. Сортировка Хоара (быстрая) во-первых: действует не самым оптимальным способом, выбирая каждый раз в качестве разделителя средний элемент, а во-вторых: ведет себя очень "задумчиво" (как и любая другая сравнительная сортировка) на мало отличающихся ключах (много времени уходит на процесс сравнения ключей) - возможен вариант вырождения в O(n2·log(n)). Михаэлем Шиндлером был предложен другой вариант преобразования (ST - Schindler Transformation), не обремененный проблемой выбора эффективного алгоритма сортировки.

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

Если представить архивацию блока данных как Result = HUFFMAN ( MTF ( BWT(data) ) ), то при распаковке (последовательном применении unHUFFMAN и unMTF к Result) неизменно встанет вопрос о реализации обратного к BWT преобразования. Сходу может показаться, что между словами "3ОООГЛВ" и "ЛОГОВО" нет никакой связи - убедимся в обратном:

-- Восстановим исходную матрицу циклических сдвигов, имея в распоряжении только последний столбец
1. .....О
3. .....О
5. .....О
4. .....Г
2. .....Л
6. .....В
-- Отсортировав последний столбец по возрастанию, получим первый
1. В....О
2. Г....О
3. Л....О
4. О....Г
5. О....Л
6. О....В
-- Заметим, что "ОВ", "ОГ", "ОЛ", "ГО", "ЛО", "ВО" входят в наше исходное слово. Заполним второй столбец, подобрав пару к букве первого столбца - для этого отсортируем имеющиеся у нас пары в порядке возрастания
ОВ     ВО     ВО...О
ОГ     ГО     ГО...О
ОЛ  »  ЛО  »  ЛО...О
ГО  »  ОВ  »  ОВ...Г
ЛО     ОГ     ОГ...Л
ВО     ОЛ     ОЛ...В
-- Теперь мы уже располагаем тройками букв исходного слова: "ОВО", "ОГО", "ОЛО", "ГВО", "ЛГО", "ВЛО". Проведем с ними аналогичное преобразование, тем самым, заполнив третий столбец
ОВО     ВОЛ     ВОЛ..О
ОГО     ГОВ     ГОВ..О
ОЛО  »  ЛОГ  »  ЛОГ..О
ГОВ  »  ОВО  »  ОВО..Г
ЛОГ     ОГО     ОГО..Л
ВОЛ     ОЛО     ОЛО..В
-- И так далее до тех пор, пока не получим матрицу всех циклических сдвигов
1. ВОЛОГО
2. ГОВОЛО
3. ЛОГОВО
4. ОВОЛОГ
5. ОГОВОЛ
6. ОЛОГОВ
-- Если вы помните, мы в первую ячейку BWT блока ("3ОООГЛВ" ) занесли номер строки (в матрице циклических сдвигов) в которой содержится исходный блок ( номер "3" = "ЛОГОВО" ).

Представленный алгоритм крайне неоптимален (заметно медленнее самого BWT).

Быстрый алгоритм обратного к BWT преобразования

Следует сразу отметить, что алгоритм приводится без доказательства. Теоретическое обоснование вы без труда сможете построить сами, изучив курс теории графов.

-- Рассмотрим матрицу, полученную в результате работы первого этапа неоптимального алгоритма обратного преобразования
1. В....О
2. Г....О
3. Л....О
4. О....Г
5. О....Л
6. О....В
-- Пронумеруем элементы последнего столбца в соответствии с номерами равных им элементов первого столбца
1  В....О  4
2  Г....О  5
3  Л....О  6
4  О....Г  2
5  О....Л  3
6  О....В  1
-- Как уже было сказано ранее, все пары ("ОВ", "ОГ", "ОЛ", "ГО", "ЛО", "ВО") входят в исходное слово. Обозначим их парой соответствующих им чисел, имеем: (6,1), (4,2), (5,3), (2,5), (3,6), (1,4). Получили граф, одним из путей которого является слово "ЛОГОВО".
-- Ясно, что если начать с запомненного ранее числа "Save" и двигаться в разрешенных графом направлениях, то мы вернемся в узел 3, проделав путь: 3 -> (3,6) -> (6,1) -> (1,4) -> (4,2) -> (2,5) -> 3. Запишем узлы, в которых мы побывали: 3, 6, 1, 4, 2, 5 и возвратимся к буквенной нотации (1 = "В", 2 = "Г", 3 = "Л", 4 = "О", 5 = "О", 6 = "О") : "Л", "О", "В", "О", "Г", "О".
-- Сдвиги при построении матрицы производились влево, поэтому полученное, циклически замкнутое, слово нужно читать слева направо от начального узла "Л". Таким образом, мы получаем исходное слово "ЛОГОВО".

Наверх