LZ77

LZ77 и LZ78 — алгоритмы сжатия без потерь, опубликованные в статьях израильских математиков Авраама Лемпеля (англ.) и Яакова Зива в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы.

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

LZ77

Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в RLE. Для понимания данного алгоритма необходимо разобраться с двумя его составляющими: принципом скользящего окна и механизмом кодирования совпадений.

Принцип скользящего окна

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

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть меньше или равен размеру окна декодировщика, но не наоборот.

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

Механизм кодирования совпадений

Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие совпадения (от англ. match). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.

В стандартном алгоритме LZ77 совпадения кодируются парой:

• длина совпадения (match length)
• смещение (offset) или дистанция (distance)

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

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

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ ещё отсутствует в буфере на момент декодирования текущей пары длина-смещение. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму RLE.

Недостатки

• невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря
• длина подстроки, которую можно закодировать, ограничена размером буфера
• малая эффективность при кодировании незначительного объёма данных

Пример «abracadabra»

              Поз.  Длина    Симв.
 abracadabra    0      0      a
a bracadabra    0      0      b
ab racadabra    0      0      r
abr acadabra    3      1      ac
abrac adabra    2      1      ad	
abracad abra    7      4      abra

Выделенные символы отсутствуют в кодирующей последовательности.

LZ78

В отличие от LZ77, работающего с уже полученными данными, LZ78, предложенный в 1978 году, ориентируется на данные, которые только будут получены (LZ78 не использует «скользящее» окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу.

Ссылки

• Jacob Ziv, Abraham Lempel. [www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf A Universal Algorithm for Sequential Data Compression] IEEE Transactions on Information Theory, 23(3), pp. 337—343, May 1977.
• [www.binaryessence.com/dct/en000138.htm Пример работы алгоритма LZ77 (см. example «abracadabra»)]
• Владимир Лидовский, [www.intuit.ru/studies/courses/2256/140/lecture/3914 Лекция 7: Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива] ([www.intuit.ru/studies/courses/2256/140/lecture/3914?page=2 LZ78]) в курсе лекций «Основы теории информации и криптографии» // Интуит.ру, 11.04.2007

Отрывок, характеризующий LZ77

Vive ce roi vaillanti –
[Да здравствует Генрих Четвертый!
Да здравствует сей храбрый король!
и т. д. (французская песня) ]
пропел Морель, подмигивая глазом.
Сe diable a quatre…
– Виварика! Виф серувару! сидябляка… – повторил солдат, взмахнув рукой и действительно уловив напев.
– Вишь, ловко! Го го го го го!.. – поднялся с разных сторон грубый, радостный хохот. Морель, сморщившись, смеялся тоже.
– Ну, валяй еще, еще!
Qui eut le triple talent,
De boire, de battre,
Et d'etre un vert galant…
[Имевший тройной талант,
пить, драться
и быть любезником…]
– A ведь тоже складно. Ну, ну, Залетаев!..
– Кю… – с усилием выговорил Залетаев. – Кью ю ю… – вытянул он, старательно оттопырив губы, – летриптала, де бу де ба и детравагала, – пропел он.
– Ай, важно! Вот так хранцуз! ой… го го го го! – Что ж, еще есть хочешь?
– Дай ему каши то; ведь не скоро наестся с голоду то.
Опять ему дали каши; и Морель, посмеиваясь, принялся за третий котелок. Радостные улыбки стояли на всех лицах молодых солдат, смотревших на Мореля. Старые солдаты, считавшие неприличным заниматься такими пустяками, лежали с другой стороны костра, но изредка, приподнимаясь на локте, с улыбкой взглядывали на Мореля.
– Тоже люди, – сказал один из них, уворачиваясь в шинель. – И полынь на своем кореню растет.
– Оо! Господи, господи! Как звездно, страсть! К морозу… – И все затихло.
Звезды, как будто зная, что теперь никто не увидит их, разыгрались в черном небе. То вспыхивая, то потухая, то вздрагивая, они хлопотливо о чем то радостном, но таинственном перешептывались между собой.

Х
Войска французские равномерно таяли в математически правильной прогрессии. И тот переход через Березину, про который так много было писано, была только одна из промежуточных ступеней уничтожения французской армии, а вовсе не решительный эпизод кампании. Ежели про Березину так много писали и пишут, то со стороны французов это произошло только потому, что на Березинском прорванном мосту бедствия, претерпеваемые французской армией прежде равномерно, здесь вдруг сгруппировались в один момент и в одно трагическое зрелище, которое у всех осталось в памяти. Со стороны же русских так много говорили и писали про Березину только потому, что вдали от театра войны, в Петербурге, был составлен план (Пфулем же) поимки в стратегическую западню Наполеона на реке Березине. Все уверились, что все будет на деле точно так, как в плане, и потому настаивали на том, что именно Березинская переправа погубила французов. В сущности же, результаты Березинской переправы были гораздо менее гибельны для французов потерей орудий и пленных, чем Красное, как то показывают цифры.
Единственное значение Березинской переправы заключается в том, что эта переправа очевидно и несомненно доказала ложность всех планов отрезыванья и справедливость единственно возможного, требуемого и Кутузовым и всеми войсками (массой) образа действий, – только следования за неприятелем. Толпа французов бежала с постоянно усиливающейся силой быстроты, со всею энергией, направленной на достижение цели. Она бежала, как раненый зверь, и нельзя ей было стать на дороге. Это доказало не столько устройство переправы, сколько движение на мостах. Когда мосты были прорваны, безоружные солдаты, московские жители, женщины с детьми, бывшие в обозе французов, – все под влиянием силы инерции не сдавалось, а бежало вперед в лодки, в мерзлую воду.
Стремление это было разумно. Положение и бегущих и преследующих было одинаково дурно. Оставаясь со своими, каждый в бедствии надеялся на помощь товарища, на определенное, занимаемое им место между своими. Отдавшись же русским, он был в том же положении бедствия, но становился на низшую ступень в разделе удовлетворения потребностей жизни. Французам не нужно было иметь верных сведений о том, что половина пленных, с которыми не знали, что делать, несмотря на все желание русских спасти их, – гибли от холода и голода; они чувствовали, что это не могло быть иначе. Самые жалостливые русские начальники и охотники до французов, французы в русской службе не могли ничего сделать для пленных. Французов губило бедствие, в котором находилось русское войско. Нельзя было отнять хлеб и платье у голодных, нужных солдат, чтобы отдать не вредным, не ненавидимым, не виноватым, но просто ненужным французам. Некоторые и делали это; но это было только исключение.
Назади была верная погибель; впереди была надежда. Корабли были сожжены; не было другого спасения, кроме совокупного бегства, и на это совокупное бегство были устремлены все силы французов.
Чем дальше бежали французы, чем жальче были их остатки, в особенности после Березины, на которую, вследствие петербургского плана, возлагались особенные надежды, тем сильнее разгорались страсти русских начальников, обвинявших друг друга и в особенности Кутузова. Полагая, что неудача Березинского петербургского плана будет отнесена к нему, недовольство им, презрение к нему и подтрунивание над ним выражались сильнее и сильнее. Подтрунивание и презрение, само собой разумеется, выражалось в почтительной форме, в той форме, в которой Кутузов не мог и спросить, в чем и за что его обвиняют. С ним не говорили серьезно; докладывая ему и спрашивая его разрешения, делали вид исполнения печального обряда, а за спиной его подмигивали и на каждом шагу старались его обманывать.
Всеми этими людьми, именно потому, что они не могли понимать его, было признано, что со стариком говорить нечего; что он никогда не поймет всего глубокомыслия их планов; что он будет отвечать свои фразы (им казалось, что это только фразы) о золотом мосте, о том, что за границу нельзя прийти с толпой бродяг, и т. п. Это всё они уже слышали от него. И все, что он говорил: например, то, что надо подождать провиант, что люди без сапог, все это было так просто, а все, что они предлагали, было так сложно и умно, что очевидно было для них, что он был глуп и стар, а они были не властные, гениальные полководцы.
В особенности после соединения армий блестящего адмирала и героя Петербурга Витгенштейна это настроение и штабная сплетня дошли до высших пределов. Кутузов видел это и, вздыхая, пожимал только плечами. Только один раз, после Березины, он рассердился и написал Бенигсену, доносившему отдельно государю, следующее письмо:
«По причине болезненных ваших припадков, извольте, ваше высокопревосходительство, с получения сего, отправиться в Калугу, где и ожидайте дальнейшего повеления и назначения от его императорского величества».