Классические алгоритмы Зива - Лемпела

Алгоритмы словарного сжатия Зива-Лемпела появились во второй поло­вине 70-х гг. Это были так называемые алгоритмы LZ77 и LZ78, разрабо­танные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем перво­начальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчетное количество модификаций.

LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже обработанной части входного пото­ка, т. е. адаптивно. Принципиальным отличием является лишь способ фор­мирования фраз. В модификациях первоначальных алгоритмов это свойство сохраняется. Поэтому словарные алгоритмы Зива - Лемпела разделяют на два семейства - алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда так­же говорят о словарных методах LZ1 и LZ2.

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

С тех пор методы данного семейства неизменно являются самыми попу­лярными среди всех методов сжатия данных, хотя в последнее время ситуа­ция начала меняться в пользу BWT и РРМ, как обеспечивающих лучшее сжатие. Кроме того, практически все реально используемые словарные ал­горитмы относятся к семейству Зива - Лемпела.

Необходимо сказать несколько слов о наименованиях алгоритмов и ме­тодов. При обозначении семейства общепринятой является аббревиатура LZ, но расшифровываться она должна как Ziv - Lempel, поэтому и алгорит­мы Зива - Лемпела, а не Лемпела - Зива. Согласно общепринятому объяс­нению этого курьеза, Якоб Зив внес больший вклад в открытие соответст­вующих словарных схем и исследование их свойств и, таким образом, за­служил, чтобы первым стояла его фамилия, что мы и видим в заголовках статей [12, 13]. Но случайно была допущена ошибка, и прикрепилось со­кращение LZ (буквы упорядочены в алфавитном порядке). Иногда, кстати, встречается и обозначение ZL (порядок букв соответствует порядку фами­лий авторов в публикациях [12, 13]). В дальнейшем, если некий исследова­тель существенно изменял какой-то алгоритм, относимый к семейству LZ, то в названии полученной модификации к строчке LZ обычно дописывалась первая буква его фамилии, например: алгоритм LZB, автор Белл (Bell).

Подчеркнем также наличие большой путаницы с классификацией алго­ритмов. Обычно она проявляется в нежелании признавать существование двух самостоятельных семейств LZ, а также в неправильном отнесении ал­горитмов к конкретному семейству. Беспорядку часто способствуют сами разработчики: многим невыгодно раскрывать, на основе какого алгоритма создана данная модификация из-за коммерческих, патентных или иных меркантильных соображений. Например, в случае коммерческого про­граммного обеспечения общепринятой является практика классификации используемого алгоритма сжатия как "модификации LZ77". И в этом нет ничего удивительного, ведь алгоритм LZ77 не запатентован.

Алгоритм LZ77

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г. [12], но сам алгоритм разработан не позднее 1975 г.

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

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-n уже закодированных символов, ко­торая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра (looka-head), длины и; обычно и на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали t символов 5/, S2, ...,S,. Тогда словарем будут являться Wпредшествующих символов Sцкл), ■S'^w-d+i» •••> $t- Соответственно, в буфере находятся ожидающие кодирова­ния символы S,+i, S/+2,..., S,₊„. Очевидно, что если W> t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения меж­ду строкой буфера, начинающейся с символа Sm, и всеми фразами словаря. Эти фразы могут начинаться с любого символа S^-d» S^y-iyt-i> •••> S, и вы­ходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с SVi> поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза S,^.i), S ныун, ..., St4- i)+{M) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, /;

2) длины соответствия, или совпадения (match length),/

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

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обрабо­танной строке буфера, и одного символа s (литерала). Затем окно смещается на/И символов вправо и осуществляется переход к новому циклу кодиро­вания. Величина сдвига объясняется тем, что мы реально закодировали именно у+1 символов: у с помощью указателя на фразу в словаре и 1 с по­мощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных симво­лов, но существенно увеличивает размер сжатого блока.

Пример

Попробуем сжать строку "кот_ломом_колол_слона" длиной 21 символ. Пусть длина буфера равна семи символам, а размер словаря больше длины сжимаемой строки. Условимся также, что:

■ нулевое смещение зарезервировали для обозначения конца кодирования;

■ символ s, соответствует единичному смещению относительно символа 5,+|, с которого начинается буфер;

■ если имеется несколько фраз с одинаковой длиной совпадения, то выби­раем ближайшую к буферу;

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

Таблица 3.1

Шаг	Скользящее окно		Совпадаю­щая фраза	Закодированные данные
	Словарь	Буфер		i	J	s
1	-	кот лом	-	1	0	"к"
2	к	от ломо	-	1	0	"о"
3	ко	т ломом	-	1	0	|»тм
4	кот	ломом	-	1	0	и м
5	кот	ломом к	-	1	0	"л"
б	кот л	омом ко	о	4	1	"м"
7	кот лом	ом коло	ом	2	2	И II
8	кот ломом	колол с	ко	10	2	"л"
9	кот ломом кол	ол слон	6л	2	2	II II
10	... ломом колол	слона	-	1	0	"с"
11	...ломом колол с	лона	ло	5	2	"н"
12	...ом колол слон	а	-	1	0	"а"

Для кодирования i нам достаточно 5 бит, дляу нужно 3 бита, и пусть симво­лы требуют 1 байта для своего представления. Тогда всего мы потратим 12-(5+3+8) = 192 бита. Исходно строка занимала 21-8 = 168 бит, т. е. LZ77 коди­рует нашу строку еще более расточительным образом. Не следует также забы­вать, что мы опустили шаг кодирования конца последовательности, который потребовал бы еще как минимум 5 бит (размер поля i = 5 битам).

Процесс кодирования можно описать следующим образом.

while ( ! DataFile.EOFO ){

/*найдем максимальное совпадение; в match_pos получим

смещение i, в match_len - длину j, в unmatched_sym -первый несовпавший символ s_ttl+.j; считаем также, что в

функции find_match учитывается ограничение на длину

совпадения */

find_match (&match_pos, &match_len, &unmatched_sym); /♦запишем в файл сжатых данных описание найденной фразы, при этом длина битового представления i задается константой OFFS_LN, длина представления

j - константой LEN_LN, размер символа s принимаем

равным 8 битам */

CompressedFile.WriteBits (match_pos, OFFS_LN); CompressedFile.WriteBits (match_len, LEN_Ltl); CompressedFile.WriteBits (unmatched_sym, 8; ; for (i = 0; i <- match_len; i++){

// прочтем очередной символ

с = DataFile.ReadSymbol();

//удалим из словаря одну самую старую фразу

DeletePhrase ();

/*добавим в словарь одну фразу, начинающуюся с первого символа буфера

*/

AddPhrase О;

/♦сдвинем окно на 1 позицию, добавим в конец буфера символ с

*/

MoveWindow(с); } } CompressedFile.WriteBits (0, OFFS_LN);

Пример подтвердил, что способ формирования кодов в LZ77 неэффекти­вен и позволяет сжимать только сравнительно длинные последовательно­сти. До некоторой степени сжатие небольших файлов можно улучшить, ис­пользуя коды переменной длины для смещения /. Действительно, даже если мы используем словарь в 32 Кб, но закодировали еще только 3 Кб, то сме­щение реально требует не IS, a 12 бит. Кроме того, происходит существен­ный проигрыш из-за использования кодов одинаковой длины при указании длин совпадения/ Например, для уже упоминавшейся электронной версии романа "Бесы" были получены следующие частоты использования длин совпадения:

J	Количество раз, когда максимальная длина совпадения была равна/
0	136
1	1593
2	4675
3	11165
4	20047
5	26939
6	28653
7	24725
8	19702
9	14767
10	10820
11	27903

Из таблицы следует, что в целях минимизации закодированного пред­ставления для j = 6 следует использовать код наименьшей длины, так как эта длина совпадения встречается чаще всего.

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

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

Алгоритм декодирования может иметь следующий вид:

for (;;) {

// читаем смещение

match_pos = CompressedFile.ReadBits (OFFS_LN);

if (!match_pos)

// обнаружен признак конца файла, выходим из цикла

break; // читаем длину совпадения

match_len = CompressedFile.ReadBits (LEN_LN); for (i - 0; i < match_len; i++) {

/♦находим в словаре очередной символ совпавшей фразы

*/

с - Diet (match_pos + i);

/♦сдвигаем словарь на одну позицию, добавляем в его начало с

*/

MoveDict (с)

/♦записываем очередной раскодированный символ в выходной файл

*/

DataFile.WriteSymbol (с);

}

/♦читаем несовпавший символ, добавляем его в словарь и записываем в выходной файл

*/

с = CompressedFile.ReadBits (8);

MoveDict (с)

DataFile.WriteSymbol (с); }

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

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

Алгоритм LZSS

Алгоритм LZSS позволяет достаточно гибко сочетать в выходной после­довательности символы и указатели (коды фраз), что до некоторой степени устраняет присущую LZ77 расточительность, проявляющуюся в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 г. Сторером (Storer) и Жимански (Szymanski) [10].

Идея алгоритма заключается в добавление к каждому указателю и сим­волу 1-битового префикса/ позволяющего различать эти объекты. Иначе говоря, 1-битовый флаг/указывает тип и, соответственно, длину непосред­ственно следующих за ним данных. Такая техника позволяет:

■ записывать символы в явном виде, когда соответствующий им код имеет большую длину и, следовательно, словарное кодирование только вредит;

■ обрабатывать ни разу не встреченные до текущего момента символы.

Пример

Закодируем строку "кот_ломом_колол_слона" из предыдущего примера и сравним коэффициент сжатия для LZ77 и LZSS.

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

Таблица 3.2

Шаг	Скользящее окно		Совпадающая фраза	Закодированные данные
	Словарь	Буфер		f	i	j		s
1	-	кот_лом	-	0	-			"к"
2	к	от ломо	-	0	-			"о"
3	ко	т ломом	-	0	-			"т"
4	кот	ломом	-	0	-			tt fl
5	кот	ломом к	-	0	-			"л"
6	кот л	омом ко	о	0	-			"о"
7	кот ло	мом кол	-	0	-			"м"
8	кот лом	ом_коло	ом	1	2	2		-
9	кот ломом	колол		0	-	-		и и
10	кот ломом	колол с	ко	1	10	2		-
11	кот ломом ко	лолсло	ло	1	8	2		-
12	...от ломом коло	л_слона	л	0	-	•		"л"
13	...т ломом колол	слона		0	-	-		II II
14	... ломом колол	слона	-	0	-	-		"с"
15	...ломом колол с	лона	ло	1	5	2		-
16	...мом колол ело	на	-	0	-	-		V
17	...ом колол слон	а	-	0	-	-		"а"

Таким образом, для кодирования строки по алгоритму LZSS нам потре­бовалось 17 шагов: 13 раз символы были переданы в явном виде и 4 раза мы применили указатели. Заметим, что при работе по алгоритму LZ77 нам по­требовалось всего лишь 12 шагов. С другой стороны, если задаться теми же длинами для i и у", то размер закодированных по LZSS данных равен 13-(1+8) + 4(1+5+3) = 153 битам. Это означает, что строка действительно была сжа­та, так как ее исходный размер 168 бит.

Рассмотрим алгоритм сжатия подробнее.

const int

// порог для включения словарного кодирования

THRESHOLD = 2,

// размер представления смещения, в битах

OFFS_LN = 14,

// размер представления длины совпадения, в битах

LEN_LN = 4; const int

WIN_SIZE = (1 « OFFS_LN), // размер окна

BUF_SIZE = (] « LEN_LN) - 1; // размер буфера //функция вычисления реального положения символа в окне

inline int MOD (int i) { return i & (WIN_SIZE-1); };

//собственно алгоритм сжатия

int buf_sz = BUF_SIZE;

/* инициализация: заполнение буфера, поиск совпадения

для первого шага */

while ( buf_sz ) {

if ( match_len > buf_size) match_len = buf_size; if ( match_len <= THRESHOLD ) {

/*если длина совпадения меньше порога (2 в примере), то запишем в файл сжатых данных флаг и символ; pos определяет позицию начала буфера */

CompressedFile.WriteBit (0); CompressedFile.WriteBits (window [pos], 8); // это понадобится при обновлении словаря match_len = 1; }else{

/♦иначе запишем флаг и указатель, состоящий из

смещения и длины совпадения ♦/

CompressedFile.WriteBit (1);

CompressedFile.WriteBits (match_offs, OFFS_LN); CompressedFile.WriteBits (match_len, LENLN); } for (int i = 0; i < match_len; i++) {

/♦удалим из словаря фразу, начинающуюся в позиции

MOD (pos+buf_sz) */

DeletePhrase ( MOD (pos+buf_sz) ) ; if ( (c = DataFile.Readsymbol ()) == EOF) // мы в конце файла, надо сократить буфер buf_sz--; else

/♦иначе надо добавить в конец буфера новый

символ */

window [MOD (pos+buf_sz)] = с; pos = MOD (pos+1); // сдвиг окна на 1 символ if (buf_sz)

/♦если буфер не пуст, то добавим в

словарь новую фразу, начинающуюся в позиции pos; считаем, что в функции AddPhrase одновременно
выполняется поиск максимального совпадения

между буфером и фразами словаря */ AddPhrase (pos, &match_offs, &match_len)

} } CompressedFile.WriteBit (1);

CompressedFile.WriteBits (0, 0FFS_LN); // знак конца файла

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

Алгоритм декодирования может быть реализован следующим образом:

for (;;) {

if ( ICompressedFile.ReadBit () ){

/*это символ, просто выведем его в файл и запишем в

конец словаря (символ будет соответствовать смещению

i = 1) */

с = CompressedFile.ReadBits (8); DataFile.WriteSymbol (с); window [pos] = с; pos = MOD (pos+1); }else{

// это указатель, прочитаем его

match_pos = CompressedFile.ReadBits (OFFS_LN);

if (!match_pos)

break; // конец файла match_pos = MOD(pos - match_pos); match_len = CompressedFile.ReadBits (LEN_LN); // цикл копирования совпавшей фразы словаря в файл for (int i = 0; i < match_len; i++) {

//выдаем очередной совпавший символ с

с = window [MOD (match_pos+i)] ;

DataFile.WriteSymbol (с);

window [pos] = с;

pos = MOD (pos + 1) ; } }

Упражнение. Из-за наличия порога THRESHOLD часть допустимых значений длины реально не используется, поэтому размер буфера BUF_SIZE может быть увеличен при неизменном LENJ.N. Проделайте соответствующие моди­фикации фрагментов программ кодирования и декодирования.

Алгоритм LZ78

Алгоритм LZ78 был опубликован в 1978 г. [13] и впоследствии стал "от­цом" семейства словарных методов LZ78.

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

Кодер порождает только последовательность кодов фраз. Каждый код состоит из номера (индекса) л "родительской" фразы S, или префикса, и символа s.

В начале обработки словарь пуст. Далее, теоретически, словарь может расти бесконечно, т. е. на его рост сам алгоритм не налагает ограничений. На практике при достижении определенного объема занимаемой памяти словарь должен очищаться полностью или частично.

Пример

И еще раз закодируем строку "кот_ломом_колол_слона" длиной 21 сим­вол. Для LZ78 буфер в принципе не требуется, поскольку достаточно легко так реализовать поиск совпадающей фразы максимальной длины, что по­следовательность незакодированных символов будет просматриваться толь­ко один раз. Поэтому буфер показан только с целью большей доходчивости примера. Фразу с номером 0 зарезервируем для обозначения конца сжатой строки, номером 1 будем задавать пустую фразу словаря.

Таблица 3.3

Шаг	Добавляемая в словарь фраза		Буфер	Совпадающая фраза S	Закодированные данные
	Сама фраза	Ее номер			п	s
1	к	2	кот лом	-	1	"к"
2	0	3	от ломо	-	1	"0"
3	т	4	т ломом	-	1	п_«
4		5	ломом	-	1	II II

Шаг	Добавляемая в словарь фраза		Буфер	Совпадающая фраза S	Закодированные данные
	Сама фраза	Ее номер			п	■ s !
5	л	6	ломом к	-	1	"л" ;
6	ом	7	омом ко	0	3	"м" !
7	ом	8	ом коло	ом	7	II И
8	ко	9	колол с	к	2	"о"
9	ло	10	лол_сло	л	6	"о" ■
10	л	11	л слона	л	6	II М
11	с	12	слона	-	1	"с"
12	лон	13	лона	ло	10	"н"
13	а	14	а	-	1	"а" 5

Строку удалось закодировать за 13 шагов. Так как на каждом шаге выда­вался один код, сжатая последовательность состоит из 13 кодов. Возможно использование 15 номеров фраз (от 0 до 14), поэтому для представления п посредством кодов фиксированной длины нам потребуется 4 бита. Тогда размер сжатой строки равен 13 (4+8) = 156 битам.

Ниже приведен пример реализации алгоритма сжатия LZ78.

п = 1;

while ( ! DataFile.EOF() ){

s = DataFile.ReadSymbol; // читаем очередной символ /'пытаемся найти в словаре фразу, представляющую

собой конкатенацию родительской фразы с номером л и символа s; функция возвращает номер искомой фразы в phrase_num; если же фразы нет, то phrase_num принимает значение 1, т. е. указывает на пустую фразу */

FindPhrase (&phrase_num, n, s); if (phrase_num != 1)

/*такая фраза имеется в словаре, продолжим поиск

совпадающей фразы максимальной длины */

n = phrase_num; else {

/*такой фразы нет, запишем в выходной файл код; INDEX_LN - это константа, определяющая длину битового представления номера л */

CompressedFile.WriteBits (n, INDEX_LN); CompressedFile.WriteBits (s, 8) ; AddPhrase (n, s); // добавим фразу в словарь n = 1; // подготовимся к следующему шагу }

}

// признак конца файла

CompressedFile.WriteBits (О, INDEX_LN);

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

for (;;) {

// читаем индекс родительской фразы

n = CompressedFile.ReadBits (INDEX_LN);

if (!n)

break; // конец файла // читаем несовпавший символ 5 s - CompressedFile.ReadBits (8) ; /♦находим в словаре позицию начала фразы с индексом п

и ее длину

*/

GetPhrase (Spos, &len, n)

/♦записываем фразу с индексом л в файл раскодированных данных

*/

for (i =0; i < len; i++)

DataFile.WriteSymbol (Dict[pos+i]);

// записываем в файл символ s

DataFile.WriteSymbol (s);

AddPhrase (n, s); // добавляем новую фразу в словарь }

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

Несмотря на относительную быстроту кодирования LZ78, при грамотной реализации алгоритма оно все же медленнее декодирования, соотношение скоростей равно обычно 3:2.

Интересное свойство LZ78 заключается в том, что если исходные дан­ные порождены источником с определенными характеристиками (он должен быть стационарным¹ и эргодическим²), то коэффициент сжатия при­ближается по мере кодирования к минимальному достижимому [13]. Иная» говоря, количество битов, затрачиваемых на кодирование каждого символа. в среднем равно так называемой энтропии источника. Но, к сожалению сходимость медленная и на данных реальной длины алгоритм ведет себя не лучшим образом. Так, например, коэффициент сжатия текстов в зависимо­сти от их размера обычно колеблется от 3.5 до 5 бит/символ. Кроме того нередки ситуации, когда обрабатываемые данные порождены источником ;. ярко выраженной нестационарностью. Поэтому при оценке реального пове­дения алгоритма следует относиться с большой осторожностью к теорети­ческим выкладкам, обращая внимание на выполнение соответствующих ус­ловий.

Доказано, что аналогичным свойством сходимости обладает и классиче­ский алгоритм LZ77, но скорость приближения к энтропии источника меньше, чем у алгоритма LZ78 [12].