Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Методы, используемые совместно с BWT

Как уже было сказано, само по себе преобразование Барроуза - Уилера не сжимает. Эту работу проделывают другие методы, призванные толково распо­рядиться теми свойствами, которыми обладают преобразованные данные.

Среди таких методов можно отметить следующие:

■ кодирование длин повторов (RLE);

■ метод перемещения стопки книг [35] (MTF);

■ кодирование расстояний (DC);

■ метод Хаффмана;

■ арифметическое кодирование.

Последовательность применения методов, используемых совместно с BWT:

Шаг

Используемый алгоритм

I

Кодирование длин повторов (необязательно)

2

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

Частичное сортирующее преобра­зование

3

Перемещение стопки книг

Кодирование расстояний

4

Кодирование длин повторов (необязательно)

5

Метод Хаффмана Арифметическое кодирование

ПЕРЕМЕЩЕНИЕ СТОПКИ КНИГ

Метод также известен под названием MTF (Move To Front). Суть его легко понять, если представить процесс перемещения книг в стопке, из ко­торой время от времени достают нужную книгу и кладут сверху. Таким об­разом, через некоторое время наиболее часто используемые книги оказыва­ются ближе к верхушке стопки.

Введем следующие обозначения:

N - число символов в алфавите;

М - упорядоченный список символов размером N; М[0] соответствует верхней книге стопки, M[JV-1] - нижней;

х - очередной символ.

int tmpl, tmp2, i=0;

trapl = Mfi];

M[i] = x;

while( tmpl != x ) {

i++;

tmp2 = tmpl;

tmpl = M[i];

M[i] = tmp2; }

Для примера произведем преобразование над последовательностью "рдакраааабб", полученной нами после BWT. Предположим, что мы имеем дело с алфавитом, содержащим только эти 5 символов и в упорядоченном списке символов они расположены в следующем порядке: М = {"а", "б", "д", "к","р"}.

Первый из символов последовательности, "р", находится в списке под номером 4. Это число мы и записываем в выходной блок. Затем мы изменя­ем список, перенося этот символ в вершину списка, при этом сдвигая все остальные элементы, находившиеся до этого выше.

Следующий символ, "д", после этого сдвига оказывается в списке под номером 3. И т. д. (рис. 5.11).

Символ ' ...Список _JJ0MeЈ.

р

абдкр

д

рабдк

а

драбк

к

адрбк

Р

кадрб

а

ркадб

а

аркдб

а

аркдб

а

аркдб

б

аркдб

б

баркд

Рис. 5.11. МТР'-преобразование строки "рдакраааабб"

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

Вспомним, что результат преобразования Барроуза - Уилера представ­ляет собой последовательность символов, среди которых часто попадаются идущие подряд одинаковые символы. Поэтому, чтобы эффективно сжать такую последовательность, статистическому кодеру необходимо вовремя отслеживать смену одного частого символа другим. MTF предназначен для того, чтобы облегчить задачу статистическому кодеру.

Рассмотрим последовательность "bbbbcccccdddddaaaaab", обладающую такими свойствами. Попробуем обойтись без MTF и закодировать ее по ме­тоду Хаффмана. Для упрощения будем исходить из предположения, что за­траты на хранение дерева, требуемого для обеспечения декодирования, бу­дут равны и с использованием MTF и без него.

Вероятности всех четырех символов в данном примере равны 1/4, т. е. для кодирования каждого из символов нам потребуется 2 бита. Легко по­считать, что в результате кодирования мы получим последовательность длиной 20-2 = 40 бит.

Теперь проделаем то же самое со строкой, подвергнутой MTF-преобразованию. Предположим, что начальный список символов выглядит как {"а", "Ь", "с", "d"} (рис. 5.12).

bbbbcccccdddddaaaaab исходная строка

10002000030000300003 строка после MTF

Символ Частота___ Вероятность КодХаффмана

"<Г~.. "...... 15 ~ "з"/4..................... 0"..........

3 3 3/20 10

1 1 1/20 ПО

.2................... J________ ..... 1/20........................... Щ__

Рис. 5.12. Кодирование методом Хаффмана строки после MTF-преобразования

В результате кодирования получаем последовательность длиной 15*1 + + 3*2+1*3 +1*3 = 27 бит.

Упражнение. Произведите преобразование методом стопки книг последова­тельности "bbbbbccccdddcceaaaaa" и определите, будет ли использование MTF давать преимущество при кодировании методом Хаффмана. Начальный упо­рядоченный список символов установить {"а", "Ь", "с", "d", "e"}. Исходите из предположения, что алфавит состоит только из указанных пяти символов.

Кодирование длин повторов

Этот метод также называется Run Length Encoding (RLE). Это один из наиболее старых методов сжатия. Суть этого метода заключается в замене идущих подряд одинаковых символов числом, характеризующим их коли­чество. Конечно, также мы должны и указать признак "включения" меха­низма кодирования длин повторов, который можем распознать при декоди­ровании.

Один из возможных вариантов - включать кодирование, когда число по­вторяющихся символов превысит некоторый порог. Например, если мы ус­ловимся, что порог равняется трем символам, то последовательность "aaaaabbbccccdd" в результате кодирования будет выглядеть как "aaa2bbb0cccldd". Если мы выберем в качестве порога 4 символа, то полу­чим "aaaalbbbccccOdd".

c*L Упражнение. Что получится, если закодировать повторы в данной строке, ис­пользуя порог, равный двум символам?

Главное назначение кодирования длин повторов в связке с BWT - увели­чить скорость сжатия и разжатия.

RLE можно применить дважды - до преобразования и после. До преоб­разования данный метод может пригодиться, если мы имеем дело с пото­ком, содержащим много повторов одинаковых символов. Сортировка строк матрицы перестановок- наиболее длительная из процедур, необходимых для сжатия при помощи BWT. В случае высокоизбыточных данных время выполнения этой процедуры может существенно (в разы) возрастать. Сей­час разработаны методы сортировки, устойчивые к такого рода избыточно­сти данных, но ранее метод кодирования длин повторов широко использо­вался на этом этапе ценой небольшого ухудшения сжатия. RLE следует применять, если указанных повторов уж слишком много.

Не является обязательным и другое применение RLE- кодирование длин повторов после преобразования Барроуза - Уилера. Оно довольно эф­фективно реализовано в szip [33] и ВА, но известны архиваторы, в которых RLE не требуется, например такие, которые используют кодирование рас­стояний (DC, YBS). Ряд архиваторов использует некую разновидность ко­дирования длин повторов - 1-2 кодирование, описанное ниже. В любом случае, если не воспользоваться каким-нибудь из перечисленных методов сокращения количества выходных символов, скорость работы будет остав­лять желать лучшего, особенно в случае архиваторов, в которых использу­ется арифметическое кодирование.

Усовершенствование метода перемещения стопки книг

MTF является вполне самостоятельным преобразованием и, помимо ис­пользования вкупе с BWT, применяется и в других областях. Но сейчас мы рассмотрим модификации метода перемещения стопки книг, которые помо­гают улучшить сжатие данных, полученных именно после преобразования Барроуза - Уилера.

Когда мы выписываем символы последнего столбца матрицы перестано­вок, относящиеся к весьма близким контекстам, мы можем с достаточно большой долей уверенности утверждать, что для многих типов данных эти символы будут одинаковы. В частности, к таким типам данных относятся файлы, содержащие текст на естественном языке.

Однако возможны небольшие нарушения такой закономерности - за счет ошибок, за счет наличия больших букв в начале предложения, переносов слов и т. д. Эти нарушения на выходе BWT часто выглядят как небольшие вкрапления посторонних символов среди длинной цепочки одинаковых. Очевидно, вкрапления из одного редкого символа будут встречаться чаще двойных, тройных и более длинных.

Можно заметить, что при MTF-преобразовании такие одиночные симво­лы приводят к двойному появлению единичных кодов, что ухудшает нам статистику. Способ преодоления такой неприятности довольно прост. Сле­дует отложить продвижение символа на верхушку списка в том случае, если этот символ не находится в позиции, соответствующей коду 1. На рис. 5.13 представлено, как будет выглядеть преобразование последовательности "рдакраааабб" в этом случае.

Символ Список Выход

р абдкр 4

д арбдк 3

а адрбк О

к адрбк 4

р акдрб 3

а аркдб О

а аркдб О

а аркдб О

а аркдб О

б аркдб 4

б .?бр_кд 1

Рис. 5.13. Модифицированное MTF-преобразование строки "рдакраааабб"

Преимущество такой модификации видно на примере MTF-преобразо-вания типичной для английских текстов последовательности "ttttTtttwtt", полученной из части последнего столбца матрицы перестановок:

he_

he

he"

he_

Т

he_

he

he"

hen_

w

hen_

hen_

hen_

Предположив, что упорядоченный список содержит символы в порядке {"t", "w", "T"...}, в результате применения метода перемещения стопки книг получаем следующие результаты:

ttttTtttwtt

00002100210

Обычный MTF

00002000200

Модифицированный MTF

Как видно из примера, на типах данных, обладающих описанными свой­ствами, усовершенствованный метод перемещения стопки книг дает рас­пределение кодов MTF, которое лучше поддается сжатию за счет большего количества нулевых кодов.

Но в случае появления двойных редких символов, этот метод дает ре­зультаты хуже классического MTF. Например, если нам попалась последо­вательность "ttttTTtttwwtt":

ttttTTtttwwtt

0000201002010

Обычный MTF

0000211002110

Модифицированный MTF

Но, как уже было замечено, вероятность появления двух идущих подряд редких символов меньше, чем вероятность появления одного.

Картину также может испортить ситуация, когда мы имеем дело с сим­волами, соответствующими не устойчивым контекстам, а участку смены одного контекста другим. В этом случае задержка в перемещении символа к вершине списка может сослужить плохую службу при отслеживании появ­ления нового устойчивого контекста. Справедливости ради стоит отметить, что и в этом случае модифицированное MTF-преобразование все же обычно реагирует достаточно быстро.

Резюмируя, можно сказать, что описанный вариант метода перемещения стопки книг на текстовых данных оказывается лучше классического, а од­нозначно поручиться за сохранение такого преимущества при обработке данных другого типа нельзя. Возможно, более правильным выбором будет предварительный анализ данных или подсчет числа отложенных перемеще­ний на вершину списка для принятия решения, какой из вариантов исполь­зовать.

Упражнение. Какой из методов MTF-преобразования будет эффективнее для последовательности символов "aaacbaaa"? Предположим, что начальный упо­рядоченный список символов выглядит как {"а", "Ь", "с"}.

Преимущество модифицированного алгоритма для текстовых данных можно оценить на примере файла bookl из набора файлов CalgCC, часто используемого для оценки архиваторов. На рис. 5.14 приводятся частоты рангов для обоих методов перемещения стопки книг.

Ранги

MTF обычный, %

MTF модифицированный, %

0

49.77

51.43

1

15.36

14.93

2

7.91

7.45

3

5.28

4.96

4

3.79

3.67

5

2.91

2.81

6

2.35

2.29

7

1.98

1.94

8

1.68

1.63

9

1.45

1.44

10

1.26

1.23

11

1.06

1.05

12

0.91

0.90

13...255

4.33

4.31

Рис. 5.14. Статистика рангов MTF-преобразования для файла bookl

1-2-КОДИРОВАНИЕ

При кодировании длин повторов символов применительно к преобразо­ванию Барроуза - Уилера стоят две задачи:

■ обеспечить кодирование чисел любой величины;

■ адаптироваться к изменению величины избыточности данных.

Данные задачи успешно решает алгоритм, нашедший применение в ряде архиваторов (bzip2, IMP, BWC) и названный 1-2-кодированием. Суть его заключается в том, что число, соответствующее количеству повторов, коди­руется посредством двухсимвольного алфавита.

При использовании 1-2 кодирования в связке с MTF мы отводим под нулевой ранг не один, а два символа (назовем их Zj и z2), увеличивая таким образом алфавит до 257 символов. Символ, отличный от Z\ и Z2, является признаком окончания записи числа повторов.

Число повторов кодируется так, как это представлено на рис. 5.15.

Число повторов

Код

1

Z|

2

■г-г

3

z,z,

4

z,z2

5

Z2Z|

6

z2z2

7

zlzlZl

8

Z1Z1Z2

9

Z|Z2Zj

10

Z|Z2Z2

11

Z2ZiZ|

12

Z2ZiZ2

13

Z2Z2Z|

14

Z2Z2Z2

15

ZjZiZjZi

Рис. 5.15. 1-2-кодирование чисел

Упражнение. Закодируйте посредством описанного алгоритма число 30. Како­му числу соответствует последовательность z2z2ZiZiZ2?

Как можно видеть, данный способ обеспечивает кодирование чисел в любом диапазоне. Этот метод соответствует и второму из предъявляемых требований. Увеличение избыточности данных, приводящее к возрастанию концентрации нулевых рангов MTF, приводит к увеличению частот симво­лов zi и z2. Причем если преобладают короткие последовательности MTF-0, то частота символа zj превосходит частоту символа z2.

Предвидя возможное замечание о том, что, например, число 7 приводит к большему возрастанию частоты символа zj, чем число 1, отметим сле­дующее. Как правило, распределение частот чисел повторов в среднем убы­вает с ростом числа, а частоты появлений близких по значению чисел близ­ки. Причем обычно с ростом чисел различие частот уменьшается. Поэтому: ■ частота числа 7 больше частоты числа 1 только в редких, скорее вырож­денных случаях; • увеличение частоты числа 7 за счет преобладания над частотами чисел 8, 9 и 10 приводит к более интенсивному использованию символа zu так как число символов Zi в коде, соответствующем числу 7, максимально

среди всех трехсимвольных кодов.

В целом преобладание частоты символа z, над частотой символа z2 оп­ределяется преобладанием частоты одной группы символов над другой (рис. 5.16).

Группа, приводящая

К росту ДОЛИ Z|

Группа, приводящая к росту доли z2

1 3 5 7

2 4 6 8

ЗА 7,8 11,12

5,6

9,10

13,14

7...10 15...18

П..14

19...22

Рис. 5.16. Свойства 1-2-кодирования

После двух преобразований строка "абракадабра" выглядела как {4,3,2,4,3,2,0,0,0,4,0}. Подвергнем ее 1-2-кодированию. Воспользовавшись рис. 5.16, получим {4,3,2,4,3,2,zbZi,4,Z|}.

Упражнение. Как будет выглядеть исходная строка в результате указанных двух преобразований и 1-2-кодирования, если вместо обычного применить мо­дифицированный MTF? Для справки: после BWT и модифицированного MTF была получена последовательность {4,3,0,4,2,0,0,0,0,4,1}.

Реализация 1-2-кодирования

// Функция 1-2-кодирования.

// Выводит последовательность символов zl и

// z2, соответствующую числу count.

void zlz2( int count ) {

// длина последовательности int len=0;

// число 0 не кодируется iff !count ) return;

// находим длину последовательности { int. t = count+1; do { len++;

t »= 1;

) while{ t > 1 );

}

// кодирование последовательности do { len—;

putc( (count S (l«len))? z2:zl, output ); } while( len ); }

// кодирование // использует функцию zlz2() void encode( void ) { unsigned char c;

int count - 0; // число повторов

while( !feof( input ) ) { с = getc ( input );

if ( с == 0 ) count++; // считаем MTF-0 else (

// вводим число MTF-0 zlz2( count ); count = 0;

// выводим символ, отличный от MTF_0 putc( с, output ); } )

zlz2 ( count ); }

// декодирование void decode( void ) {

unsigned char c;

int count =0; // число повторов

while( !feof( input ) ) { с = getc( input );

// чтение последовательности zlz2 if ( с == zl ) {

count += count + 1; ) else if( с == z2 ) {

count += count + 2;

) else {

// вывод MTF-0, заданные числом count while( count— ) putc ( 0, output );

putc( in[i], output );

)

i++; } while ( count-- ) putc( 0, output );

Кодирование расстояний

В течение нескольких лет метод перемещения стопки книг был непре­менным атрибутом архиватора, построенного на основе преобразования Барроуза - Уилера. В силу того, что этот алгоритм недостаточно точно учи­тывал соотношение частот символов, соответствующих разным рангам, раз­работчики постоянно стремились найти достойную замену.

Одним из наиболее распространенных был подход, при котором отдель­но строилась модель для наиболее часто используемых символов. Для таких символов вероятности просчитывались отдельно. Впервые этот подход был описан Петером Фенвиком [18], но автору не удалось превзойти результаты модели, использующей традиционный подход. Более удачным было приме­нение кеширования наиболее частых символов в архиваторе szip, разрабо­танном Шиндлером [33].

Самым поздним из методов, пришедших на смену MTF, является метод кодирования расстояний (Distance Coding). Первый же из архиваторов, ис­пользующих этот метод, сумел превзойти своих конкурентов по степени сжатия большинства типовых данных. Теперь, помимо архиватора DC, ко­дирование расстояний используют YBS и SBC.

Были публикации, посвященные родственному методу, названному Inversion Frequencies авторами одной из работ [5,1]. Помимо метода кодиро­вания расстояний, ниже мы рассмотрим и его.

Возьмем для примера ту же строку "рдакраааабб", полученную в резуль­тате преобразования Барроуза - Уилера.

В качестве первого, подготовительного этапа нам следует определить первые вхождения символов в данную строку. Для этого в начало строки припишем все символы алфавита в произвольном, например в лексикогра­фическом, порядке. Поскольку при декодировании мы можем проделать то же самое, данная операция является обратимой.

Для удобства добавим в конец строки символ, означающий конец блока. При ссылке на этот символ мы можем распознать окончание цепочки символов, от которых эта ссылка сделана. Обозначим символ конца блока как "$".

Итак, после этих приготовлений наша строка выглядит как "абдкррда-краааабб$". Причем при декодировании нам на этом подготовительном эта­пе известны первые символы строки, "абдкр", и последний, "$".

строка:

абдкррдакраааабб$

известные символы:

абдкр............ $

Теперь займемся собственно кодированием расстояний. Для этого берем первый символ, "а", и ищем ближайший такой же. Расстояние до него равно шести - это число иных символов между "а". Но из этих шести символов нам уже известны 4 и при декодировании мы заранее знаем, что очередной символ "а" никак не может попасть в эти позиции. Наша задача - закодиро­вать номер той вакантной позиции, на которую выпадает этот символ. Это номер 6-4 = 2.

строка:

абдкррдакраааабб$

известные символы:

расстояние:

2

Аналогично кодируем еще несколько символов по очереди, подсчитывая число точек, символизирующих незанятые позиции, в строке известных символов.

строка:

абдкррдакраааабб$

известные символы:

расстояние:

28

известные символы:

абдкр.да..... б.$

расстояние:

281

известные символы:

абдкр. дак... б. $

расстояние:

2811

известные символы:

расстояние:

2811-

При кодировании первого из символов "р" вместо ссылки на следующий символ поставлен прочерк, потому что сразу после символа "р" находится вакантная позиция, и это означает, что никакой другой символ не сможет на эту позицию сослаться. Значит, нам нет необходимости выполнять кодиро­вание этой ссылки. В данном случае мы наблюдаем специфический эффект, присущий методу кодирования расстояний, который позволяет избежать применения RLE.

строка:

абдкррдакраааабб$

известные символы:

абдкррдакр....б.$

расстояние:

2811-0

Поскольку очередной символ "р" занимает ближайшую вакантную пози­цию, мы кодируем его числом 0. Благодаря такому свойству метода кодиро­вания расстояний, в нем достаточно легко решается проблема случайной смены контекста, ради которой требовалось специально совершенствовать метод перемещения стопки книг.

строка:

абдкррдакраааабб$

известные символы:

абдкррдакр.... б.$

расстояние:

2811-05

Кодируя символ "д", мы сделали ссылку на конец строки. При декодиро­вании такая ссылка позволит понять, что символы "д" закончились (рис. 5.17).

строка:____________________ абдкррдакраааабб$

известные символы:

абдкррдакра...б.$

расстояние:

2811-050

известные символы:

абдкррдакра...6.$

расстояние:

2811-0504

известные символы:

абдкррдакра... б.$

расстояние:

2811-05044

известные символы:

абдкррдакрааааб.$

расстояние:

2811-05044—

известные символы:

Абдкррдакрааааб.$

расстояние:

2811-05044 —-1

известные символы:

Абдкррдакраааабб$

расстояние:

2811-05044—-1-

Рис. 5.17. Кодирование расстояний

В итоге получаем последовательность { 2,8,1,1,0,5,0,4,4,1 }. с§ч Упражнение. Вычислите расстояния для строки "брраааакаакдрр".

Обратные частоты

Есть еще один метод, похожий на описанный выше. В нем также коди­руются расстояния между одинаковыми символами. Отличие только в том, что символы, для которых определяются расстояния, берутся не в порядке поступления, а исходя из некоторого фиксированного порядка. Например, по алфавиту.

Авторы данного алгоритма, названного Inversion Frequencies (IF), исхо­дили из того, что расстояние между одинаковыми символами характеризует частоту использования этих символов на данном отрезке символьной по­следовательности. Чем расстояние меньше, тем выше частота. Поясним работу алгоритма на примере.

Предположим, нам нужно определить IF для строки "рдакраааабб", а расчет расстояний будем проводить в соответствии с положением символов в алфавите "абдкр".

Сначала запишем для символа "а" положение первого из таких символов в исходной строке и их количество.

Символ

Первая позиция

Число символов

а

2

5

Следующим шагом - для каждого из символов "а" в качестве расстояния

запишем число иных символов до следующего "а".

исходная строка:

рдакраааабб

расстояния:

2 000

После того как все позиции символа "а" определены, мы можем удалить их из исходной строки и продолжить обработку строки, как будто их и не было (рис. 5.18).

Символ

Первая позиция

Число символов

Строка

Расстояния

а б Д к

2 4 1

1

5 2

1

1

рдакраааабб

рдкрбб

рдкр

ркр

2,0,0,0 0

Рис. 5.18. Вычисление обратных частот

В кодировании символа "р" нет необходимости, так как заведомо из­вестно, что он занимает оставшиеся позиции в строке. Таким образом, мы получили такую последовательность: {{2,5,2,0,0,0}, {4,2,0}, {1,1}, {1,1}}.

Легко заметить, что способ и эффективность кодирования зависят от то­го порядка, в котором мы будем обрабатывать символы. Еще одно важное отличие данного метода от кодирования расстояний заключается в том, что он не освобождает от необходимости кодирования длинных последователь­ностей нулевых значений обратных частот.

Упражнение. Определите обратные частоты для строки "брраааакаакдрр".