Опрос

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

Новички

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

Пути улучшения сжатия для методов LZ

Улучшать сжатие алгоритмов семейства Зивц - Лемпела можно двумя путями:

1) уменьшением количества указателей при неизменной или большей общей длине закодированных фраз за счет более эффективного раз­биения входной последовательности на фразы словаря;

2) увеличением эффективности кодирования индексов фраз словаря и литералов, т. е. уменьшением количества битов, в среднем требуемых для кодирования индекса или литерала.

Идея приемов, относящихся к первому пути, была продемонстрирована на примере ленивого сравнения при описании Deflate. Действительно, для одного и того же словаря мы имеем огромное количество вариантов построения набора фраз для замещения им сжимаемой последовательности. Естественным являет­ся так называемый "жадный" разбор (greedy parsing), при котором на каждом шаге кодер выбирает самую длинную фразу. Заметим, что такой способ раз­биения данных используют все рассмотренные нами классические алгоритмы LZ. Если поиск ведется по всему словарю, то жадный разбор обеспечивает наи­большую скорость, но и практически всегда наихудшее сжатие. Стратегии оп­тимального разбора позволяют значительно улучшить сжатие, до 10% и более, но серьезным образом замедляют работу компрессора. Алгоритмы оптимально­го разбора для алгоритмов семейства LZ77 рассмотрены, например, в [1, 10], а для семейства LZ78 - в [8].

Добиваться большей компактности представления индексов словаря можно за счет:

■ применения более сложных алгоритмов сжатия, например на базе кон­текстных методов моделирования;

■ минимизации объема словаря путем удаления излишних совпадающих фраз.

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

Идеи нескольких способов увеличения степени сжатия для методов Зи-ва - Лемпела достаточно подробно описаны ниже.

Стратегия разбора LFF

Как возможную технику улучшения качества разбора входной последо­вательности на фразы словаря LZ77 укажем метод кодирования самой длинной строки первой - Longest Fragment First, или LFF. Суть LFF заклю­чается в том, что рассматривается несколько вариантов разбиения буфера на фразы словаря и первой замещается строка, с которой совпала фраза макси­мальной длины, причем строка может начинаться в любой позиции буфера.

Пример

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

№ позиции

Совпадающая фраза максимальной длины

Длина фразы

I

аб

2

2

брак

4

3

рак

3

4

ака

3

5

кадаб

5

6

адаб

4

7

даб

3

Поиск прерван на 7-й позиции, поскольку уже никакое совпадение не может быть длиннее максимального встреченного 5. Так как способ коди­рования самой длинной строки "кадаб" определен, то теперь для оставшейся подстроки "абра" снова ищется самая длинная совпадающая фраза. Это бу­дет "бра". Оставшаяся слева строка "а" может быть закодирована как лите­рал. Тогда разбор буфера будет иметь вид:

"абракадаб..." -> <а> <бра> <кадаб>.

Эта последовательность из литерала и двух фраз кодируется; окно смещает­ся на 9 символов, а буфер приобретает вид "ра...".

Заметим, что в случае жадного разбора буфер был бы разбит таким образом:

"абракадаб..." -> <аб> <рак> <адаб>.

LFF позволяет улучшить сжатие на 0.5-1% по сравнению с жадным раз­бором.

Оптимальный разбор для методов LZ77

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

Для алгоритмов семейства LZ77 эта задача была рассмотрена в [10] и признана М'-полной, т. е. требующей полного перебора всех вариантов для нахождения оптимального решения. В диссертации [1] был изложен одно­проходной алгоритм, который, как утверждается, позволяет получить опти­мальное разбиение при затратах времени не больших, чем вносимых лени­вым сравнением.

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

В общем случае для каждой позиции t находим все совпадающие фразы длины от 2 до максимальной maxlen. На основании информации о кодах, используемых для сжатия фраз и литералов, мы можем оценить, сколько примерно битов потребуется для кодирования каждой фразы (литерала), или какова цена price ее кодирования. Тогда мы можем найти близкое к оп­тимальному решение за один проход следующим образом.

В массив offsets будем записывать ссылки на фразы, подходящие для за­мещения строки буфера, длины от 2 до max_len, где maxlen является дли­ной максимального совпадения для текущей позиции t. В поле offsflen] со­храняем смещение фразы с длиной len. Если имеется несколько вариантов фраз с одной и той же len, то выбираем фразу с наименьшей ценой price: offsets [t].offs[len] = offset_min_price (t, len). Размер обрабатываемого блока равен МАХ_Т. Для обеспечения эффективности разбора МАХТ должно быть достаточно большим - несколько сотен байт и более.

struct Node {

int max_len; int Offs[MAX_LEN+1]; } offsets[MAX_T+1];

В ячейках path [ t ] массива path будем хранить информацию о том, как добраться до позиции t, "заплатив" минимальную цену.

struct {

/*цена самого "дешевого" пути до t (из пока известных путей)

*/

int price;

//с какой позиции мы попадаем в t

int prev_t;

/♦если мы попадем в fc, кодируя фразу, то здесь

хранится смещение этой фразы в словаре */

int offs; } path[MAX_T+l];

Основной цикл разбора:

path[0].price = 0;

for (t - 1; t < MAX_T; t++){

//установим недостижимо большую цену для всех t pathft].price = INFINITY; } for (t = 0; t < MAX_T; t++){

/♦найдем все совпадающие фразы для строки,

начинающейся в позиции t */

findjnatches (offsets[t]) ; for (len = 1; len <= offsets[t].max_len; len++){

/♦определяем цену рассматриваемого перехода на len

символов вперед */ if (len == 1)

// найдем цену кодирования литерала price = get_literal_price (t); else

// найдем цену кодирования фразы длины len price = get_match_price (len,

offsets[t].offs[len]); // вычислим цену пути до t + len new_price = path[t].price + price; if (new_price < path[t+len].price){

/♦рассматриваемый путь до t + len выгоднее

хранящегося в path[t+len] ♦/

path[t+len].price = newjorice; path[t+len].prev_t = t; if (len > 1)

path[t+len].offs = offsets[t].offs[len];

} )

}

В результате работы алгоритма получаем почти оптимальное решение, записанное в виде односвязного списка. Если предположить, что длина maxlen ограничивается в функции findmatches так, чтобы мы не "пере­прыгнули" позицию МАХ_Т, то головой списка является элемент path[MAX T]. Путь записан в обратном порядке, т. е. фраза со смещением path[MAX_T].offs и длиной МАХ_Т- path[MAX_T].prev_t (или литерал в позиции МАХ Т-1) должна кодироваться самой последней.

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

Упражнение. Придумайте алгоритм кодирования найденной последовательно­сти фраз и литералов.

Алгоритм Бендера-Вулфа

Очевидно, что классические алгоритмы семейства LZ77 обладают большой избыточностью словаря. Так, например, в словаре может быть несколько оди­наковых фраз длины от match Jen и менее, совпадающих со строкой в начале буфере. Но классический LZ77 никак не использует такую информацию и фак­тически отводит каждой фразе одинаковый объем кодового пространства, счи­тает их равновероятными. В 1991 г. Бендер (Bender) и Вулф (Wolf) описали прием, позволяющий до некоторой степени компенсировать данную "врож­денную" избыточность алгоритмов LZ со скользящим окном [2]. В этом алго­ритме (LZBW) после нахождения фразы S, имеющей самое длинное совпаде­ние с буфером, производится поиск самой длинной совпадающей фразы S? сре­ди добавленных в словарь позже S и полностью находящихся в словаре (не вторгающихся в область буфера). Длина S передается декодеру как разница между длиной S и длиной 5". Например, если 5= "абсд" и 5" = "аб", то длина S передается с помощью разностной длины 2.

Пример

Модифицируем LZSS с помощью техники Бендера - Вулфа. Рассмотрим процесс кодирования строки "кололкотломомколесо" начиная с первого появления символа "м". В отличие от рассмотренного выше примера LZSS словарное кодирование будем применять при длине совпадения 1 и более (табл. 3.11).

Таблица 3.11

Шаг

Скользящее окно

Совпа­дающая фраза

Закодированные данные

Словарь

Буфер

f

;'

J

s

к

колол кот ло

мом кол

-

0

-

-

"м"

к+]

колол кот лом

ом_коле

ом

1

2

2

-

к+2

колол кот ломом

_колесо

1

6

1

-

к+3

колол кот ломом

колесо

кол

1

16

1

-

к+А

...л кот ломом кол

есо

-

0

-

-

"е"

На шаге к мы встретили символ "м", отсутствующий в словаре, поэтому передаем его в явном виде. Сдвигаем окно на одну позицию.

На шаге к+l совпадающая фраза равна "ом", и в словаре нет никаких других фраз, добавленных позже "ом". Поэтому положим длину 5" равной нулю, тогда передаваемая разностьу есть 2. Сдвигаем окно на 2 символа.

На шаге к+2 совпадающая фраза состоит из одного символа "_", послед­ний раз встреченного 6 символов назад. Здесь, как и на шаге к+\, разностная длина совпадающей фразы равна ее длине, т. е. единице. Сдвигаем окно на 1 символ.

На шаге к+3 совпадающая фраза максимальной длины есть "кол", но среди фраз, добавленных в словарь после "кол", имеется фраза "ко", поэто­му длина "кол" кодируется как разница 3 и 2. Если бы в части словаря, ог­раниченной фразой "кол" слева и началом буфера справа, не нашлось бы фразы "ко" с длиной совпадения 2, а была бы обнаружена, например, только фраза "к" с длиной совпадения 1, то длина "кол" была бы представлена как 3-1=2.

При декодировании необходимо поддерживать словарь в таком же виде, что и при кодировании. После получения смещения match_pos декодер про­изводит сравнение фразы, начинающейся с найденной позиции t-(match_pos-\) (t+\ - позиция начала буфера), со всеми более "новыми" фра­зами словаря, т. е. лежащими в области Hmatcn_pos-l), • ••,'• Длина фразы восстанавливается как сумма максимального совпадения и полученной от кодера разностной длиныу. Так, например, процедура декодирования для шага к+3 будет выглядеть следующим образом. Декодер читает смещение / = 16, разностную длину у = 1 и начинает сравнивать фразу "колол_...", на­чало которой определяется данным смещением i, со всеми фразами словаря, начало которых имеет смещение от 15 до 1. Максимальное совпадение име­ет фраза "ко", расположенная по смещению 10. Поэтому длина закодиро­ванной фразы равна 2 +j = 2 + 1 = 3, т. е. кодер передал указатель на фразу "кол".

Использование техники Бендера - Вулфа позволяет улучшить сжатие для алгоритмов типа LZH примерно на 1%. При этом декодирование сильно замедляется (в разы!), поскольку мы вынуждены выполнять такой же до­полнительный поиск для определения длины, что и при сжатии.

Алгоритм Файэлэ - Грини

Еще один способ борьбы с избыточностью словаря LZ77 предложен Файэлэ (Fiala) и Грини (Greene) [4]. В разработанном ими алгоритме LZFG для просмотра словаря используется дерево цифрового поиска, и любая фраза кодируется не парой <длина, смещение>, а индексом узла, соответст­вующего этой фразе. Иначе говоря, всем одинаковым фразам соответствует один и тот же индекс. Устранение повторяющихся фраз из словаря позволя­ет уменьшить среднюю длину кодов фраз. Обычно коэффициент сжатия LZFG лучше коэффициента сжатия LZSS примерно на 10%.

Контекстно-зависимые словари

Объем словаря и, соответственно, средняя длина закодированного ин­декса могут быть уменьшены за счет использования приемов контекстного моделирования. Было установлено, что применение контекстно-зависимых словарей улучшает сжатие для алгоритмов семейства LZ77 и, в особен­ности, семейства LZ78 [5]. Идея подхода состоит в следующем. Пусть мы только что закодировали последовательность символов S небольшой длины L, тогда на текущем шаге в качестве словаря используются только строки, встреченные в уже обработанной части потока непосредственно после строк, равных S. Эти строки образуют контекстно-зависимый словарь по­рядка L для S. Если в словаре порядка L совпадение обнаружить не удалось, то происходит уход к словарю порядка 1-1. В конечном итоге если не было найдено совпадающих фраз ни в одном из доступных словарей, то текущий символ передается в явном виде.

Например, при использовании техники контекстно-зависимых словарей порядка в сочетании с LZ77 после обработки последовательности "абрака­дабра" получаем следующий состав словарей порядков 2, 1 и 0 для текуще­го контекста:

Порядок L

Состав контекстно-зависимого словаря порядка L (фразы словаря могут начинаться только в первой позиции указан­ных последовательностей)

2 (контекст "ра")

кадабра

1

(контекст "а")

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

112


Раздел 1. Методы сжатия без потерь

0

абракадабра

(пустой контекст)

бракадабра

ракадзбра

акадабра

кадабра

адабра

дабра

абра

бра

ра

а

(обычный словарь LZ77)

Эксперименты показали, что наилучшие результаты достигаются при L = =1 или 2, т. е. в качестве контекста достаточно использовать один или два предыдущих символа. Применение контекстно-зависимых словарей позво­ляет улучшить сжатие LZSS на 1-2%, LZFG - на 5%, LZW - примерно на 10%. Потери в скорости в случае модификации LZFG составляют порядка 20-30%. Соответствующие версии алгоритмов известны как LZ77-PM, LZFG-PM, LZW-PM [5].

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

Буферизация смещений

Если была закодирована фраза со смещением i, то увеличивается веро­ятность того, что вскоре нам может потребоваться закодировать фразы с приблизительно таким же смещением i ± 8, где 8 - небольшое число. Это особенно часто проявляется при обработке двоичных данных (исполнимых файлов, файлов ресурсов), поскольку для них характерно наличие сравни­тельно длинных последовательностей, отличающихся лишь в нескольких позициях.

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

В буфере запоминается т последних использованных баз смещений, различающихся между собой. Буфер обновляется по принципу списка LRU, т. е. самая последняя использованная база имеет индекс 0, самая "старая" - индекс т-\. Если база В смещения текущей фразы совпадает с одной из со­держащихся в буфере баз #,, то вместо В кодируется индекс i буфера. Затем В/ перемещается в начало списка LRU, т. е. получает индекс 0, а все 2?0*

В\..... Bt.\ сдвигаются на одну позицию к концу списка. Иначе кодируется

собственно база В, после чего она добавляется в начало буфер как Во, а все буферизованные базы смещаются на одну позицию к концу списка LRU,

при этом 5m.i удаляется из буфера. -jL '"

■ ••• i,j,c

Пример .,„ ,п .

Примем т равным двум. Если база не совпадает ни с одной содержащей­ся в буфере, то кодируемое значение базы равно абсолютному значению плюс т. Пусть также содержимое буфера равно {0, 1}, тогда пошаговое преобразование последовательности баз смещений 15, 14, 14, 2, 3, 2,... бу­дет выглядеть следующим образом:

Номер шага

Абсолютное значение базы

Содержимое буфера в начале шага

Кодируемое значение базы

So

е,

1

15

0

1

17

2

14

15

0

16

3

14

14

15

0

4

2

14

15

4

5

3

2

14

5

6

2

3

2

1

7

?

2

3

?

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

Как показывают эксперименты, оптимальное значение т лежит в преде­лах 4-8.

Стоимость кодирования индекса буфера обычно ниже стоимости коди­рования базы смещения непосредственно. Поэтому имеет смысл принуди­тельно увеличивать частоту использования буферизованных смещений за счет подбора фраз с "нужным" расположением в словаре.

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


Буферизация смещений используется практически во всех современных архиваторах, реализующих алгоритмы семейства LZ77, например: 7-Zip, CABARC, WinRAR.

Совместное кодирование длин и смещений

Между величиной смещения и длиной совпадения имеется незначитель­ная корреляция, величина которой возрастает в случае применения буфери­зации смещений. Это свойство можно использовать, объединив в один ме­тасимвол длину совпадения match_len и базу смещения of fsetbase, и, таким образом, кодировать метасимвол на основании статистики совмест­ного появления определенных длины и смещения. Как и в случае смещения, в метасимвол лучше включать не полностью длину, а ее квантованное зна­чение.

Так, например, в формате LZX (используется в компрессоре CABARC) длины совпадения от 2 до 8 входят в состав метасимвола непосредственно, а все длины matchlen > 8 отображаются в одно значение. В последнем слу­чае длина совпадения доопределяется путем отдельной передачи величины match_len-9. Метасимволы длина/смещение и литералы входят в один алфавит, поэтому в упрощенном виде алгоритм кодирования таков:

if (match_len >= 2) { // закодируем фразу if ( match_len <= 8 )

raetasymbol = (offset_base«3) II (match_len-2) ; else

metasymbol = (offset_base«3) | I 7; /♦закодируем метасимвол, указав, что это не литерал,

для правильного отображения значения метасимвола в

алфавит длин/смещений и литералов

*/

encode_syrabol (metasymbol, NON_LITERAL);

if (match_len > 8)

// доопределим длину совпадения

encode_length_footer (match_len - 9); // закодируем младшие биты смещения encode_offset_footer (...);

}else{

// закодируем литерал в текущей позиции t+1 encode_symbol (window[t+1], LITERAL)

Упражнение. Напишите упрощенный алгоритм декодирования.