Алгоритм сжатия LZ77
Алгоритм сжатия LZ77 опубликован в 1977 г.,
авторы Лимпель, Зив. На этом алгоритме
основан алгоритм Deflate, который используется,
в архиваторах zip и gzip, в формате видео
*.png и др. Алгоритм Deflate комбинирует LZ77 и
коды Хаффмана.
Иногда алгоритм LZ77 называют алгоритмом скользящего
окна. В качестве окна используется часть прочитанных
данных ограниченной длины, которая играет роль словаря.
Это байтовый алгоритм, он читает и кодирует поток
байтов (минимальная единица чтения -- это байт).
Байт -- 8 двоичных разрядов, которые трактуются как
двоичная запись числа в диапазоне 0..255.
Общее описание алгоритма
Пусть мы уже прочитали и закодировали какую-то часть
входного потока
|
V первый необработаный символ
ababubvuyuyuykkfacluyugjhgjhjkjjhkjh...
===============__________
Window Look-ahead buffer
Мы храним часть уже обработанных байтов,
а именно конец обработанной последовательности
длины, не превышающей некоторой константы, являющейся
параметром алгоритма. Эта часть называется скользящим
окном. Типичные размеры окна -- 2048, 4096, 32768
(в последнем случае такое большое окно используется в
алгориме Deflate). В буфере прочитанных, но еще
не обработанных символов мы ищем фразу максимальной
длины, которая начинается с первого необработанного
символа, уже встречалась раньше и входит в скользящее
окно (sliding window). В нашем примере фраза "uyu" из
буфера предварительного просмотра уже встречалась раньше
и входит в скользящее окно. Среди всех таких фраз
мы ищем самую длинную. Если нашли, то выдаем тройку
(смещение влево к этой фразе в окне,
длина фразы,
символ, который стоит в буфере предварительного
просмотра вслед за этой фразой)
смещение -- offset или distance,
длина -- length,
символ -- char
Таким образом, выходной поток, кодирующий сообщение,
состоит из троек, которые мы будем обозначать
(o, l, c)
В нашем примере
|
V первый необработаный символ
ababubvuyuyuykkfacluyugjhgjhjkjjhkjh...
===============__________
Window Look-ahead buffer
фраза uyu длины 3 встречается в окне на
расстоянии 10 слева от первого необработанного
символа, за этой фразой идет символ g:
|
V
ababubvuyuyuykkfacluyugjhgjhjkjjhkjh...
=== ---
Значит, мы выдаем тройку (10, 3, g) в выходной поток.
После этого 4 символа uyug мы пропускаем и,
если окно уже достигло максимального размера, то
его мы тоже сдвигаем вправо (на те же 4 позиции,
если оно максимального размера), и продолжаем
этот процесс.
Давайте проиллюстрируем его на примере, который мы
разбирали предыдущий раз.
Исходная последовательность
BABAABAAA
Будем отмечать позицию первого необработанного символа
квадратными скобками:
[B]ABAABAAA
В выходную последовательность выдаем тройку
(0, 0, B)
и передвигаем курсор на 1 позицию вправо.
B[A]BAABAAA
В окне нет последовательностей длины
> 1, поэтому выдаем вторую тройку (0, 0, A)
(0, 0, B), (0, 0, A)
BA[B]AABAAA
Теперь настал интересный момент: необработанная часть
начинается с BA, которая уже содержится в скользящем
окне на расстоянии 2, поэтому выдаем тройку (2, 2, A)
и пропускаем 3 символа:
(0, 0, B), (0, 0, A), (2, 2, A)
BABAA[B]AAA
На следующем шаге фраза BAA из начала переднего
буфера уже встречалась раньше и входит в окно
на расстоянии 3. Вслед за BAA во переднем буфере
идет символ A, поэтому выдаем тройку (3, 3, A)
и передвигаем курсор вперед на 4 позиции:
(0, 0, B), (0, 0, A), (2, 2, A), (3, 3, A)
BABAABAAA[]
Необработанных символов не осталось, поэтому
алгоритм завершает работу.
Результат кодирования:
[(0, 0, B), (0, 0, A), (2, 2, A), (3, 3, A)]
состоит из 4-х троек, при том, что длина исходной
последовательности 9.
Декодирование
В любой момент уже построена часть декодированной
последовательности. Обрабатывая очередную тройку
(offset, length, C)
мы в уже построенном массиве смещаемся
на offset символов назад (влево), читаем
фразу длины length и записываем её в конец,
а потом записываем также символ C. Окно в случае
его максимального размера смещается на
length+1 позиций вправо.
Работа алгоритма декодирования в нашем
примере:
Шаг 1
(0, 0, B), (0, 0, A), (2, 2, A), (3, 3, A)
Выдаем B, получаем
B
Шаг 2
(0, 0, A), (2, 2, A), (3, 3, A)
Выдаем A, получаем
BA
Шаг 3
(2, 2, A), (3, 3, A)
Выдаем BAA, получаем
BABAA
Шаг 4
(3, 3, A)
Выдаем BAAA, получаем
BABAABAAA
На этом алгоритм заканчивается.
Реализуем этот алгоритм на Python3.
На вход кодировщику поступает массив байтов, которые
мы только читаем, типа bytes.
На выходе кодировщика мы получаем список троек
(tuples) типа (o, l, c), где числа o и l
обозначают:
o -- смещение вправо к началу фразы
в скользящем окне,
l -- длина фразы,
c -- символ вслед за фразой.
Вот исходный код алгоритма:
def encodeLZ77(x):
n = len(x)
maxWindow = 4096
maxLookAhead = 256
pos = 0
windowSize = 0
windowPos = 0
y = []
while pos < n:
phraseLen = 0
phraseOffset = 0
pLen = 2
maxPLen = maxLookAhead
if pos + maxPLen > n - 1:
maxPLen = (n - 1) - pos
while pLen <= maxPLen:
phrase = x[pos:pos+pLen]
offset = 1
while offset <= windowSize:
if (
x[pos - offset:pos - offset + pLen]
== phrase
):
# phrase is found in the dictionary!
phraseLen = pLen
phraseOffset = offset
break
else:
offset += 1
if phraseLen == 0:
break
pLen += 1
# Search is finished, emit the triple
y.append(
(phraseOffset, phraseLen, x[pos + phraseLen])
)
pos += phraseLen + 1
# Increment or shift the sliding window
windowSize += phraseLen + 1
if windowSize > maxWindow:
windowSize = maxWindow
windowPos = pos - windowSize
return y
Декодер для алгоритма сжатия LZ77 совсем простой,
ниже приведен его код на языке Python3. На вход
декодеру подается последовательность троек
(offset, length, C), построенная кодировщиком.
В случае, когда offset равен 0 (в этом случае
также и length = 0), то декодер просто записывает
байт C в выходно поток. Если offset отличен от нуля,
то декодер смещается в на offset байтов назад от
текущей позиции в конце выходного массива
(или в конце скользящего окна, если оно хранится
отдельно) и последовательно переписывает length байтов
закодированной фразы, начало которой находится
по данному смещению, в конец выходного потока
(а также в конец скользящего окна, если оно хранится
отдельно от выходного потока). При этом длина
закодированной фразы может быть больше смещения,
в этом случае алгоритм тоже работает корректно,
поскольку по мере считывания фразы и последовательного
копирования ее байтов в выходной поток (и при
необходимости и в конец скользящего окна) выходной
поток (или окно) растет и происходит повторное
копирование уже добавленных в конец потока байтов.
Вот код декодера на языке Python3:
def decodeLZ77(y):
maxWindow = 4096
pos = 0
windowSize = 0
windowPos = 0
x = bytearray()
for (offset, length, c) in y:
if offset == 0:
x.append(c)
else:
pos = len(x)
phrasePos = pos - offset
assert phrasePos >= windowPos
for i in range(length):
x.append(x[phrasePos + i])
x.append(c)
windowSize += length + 1
if windowSize > maxWindow:
windowSize = maxWindow
windowPos = len(x) - windowSize
return x
Примеры использования
кодировщика и декодировщика
Сначала проверим результат, который мы ранее
вычислили вручную, для исходной последовательности
"BABAABAAA":
>>> s = "BABAABAAA"
>>> x = bytes(s, "ascii")
>>> x
b'BABAABAAA'
>>> y = encodeLZ77(x)
>>> y
[(0, 0, 66), (0, 0, 65), (2, 2, 65), (3, 3, 65)]
>>> xx = decodeLZ77(y)
>>> xx
bytearray(b'BABAABAAA')
>>> x == xx
True
Мы видим, что раскодированная последовательность
байтов xx совпала с исходной последовательностью x.
Закодированная последовательность y такая же, какую
мы получили вручную, ее длина 4 (тройки), тогда
как длина исходной последовательности байтов 9.
Рассмотрим еще один пример:
входная последовательность -- английская скороговорка
The rain in Spain always stays in the plain.
Вот результат применени алгритмов кодировщика и
декодировщика:
>>> s = "The rain in Spain always stays in the plain."
>>> x = bytes(s, "ascii")
>>> x
b'The rain in Spain always stays in the plain.'
>>> y = encodeLZ77(x)
>>> y
[(0, 0, 84), (0, 0, 104), (0, 0, 101), (0, 0, 32),
(0, 0, 114), (0, 0, 97), (0, 0, 105), (0, 0, 110),
(0, 0, 32), (3, 3, 83), (0, 0, 112), (9, 4, 97),
(0, 0, 108), (0, 0, 119), (0, 0, 97), (0, 0, 121),
(0, 0, 115), (0, 0, 32), (0, 0, 115), (0, 0, 116),
(6, 4, 105), (16, 2, 116), (34, 3, 112), (0, 0, 108),
(26, 3, 46)]
>>> xx = decodeLZ77(y)
>>> xx
bytearray(b'The rain in Spain always stays in the plain.')
>>> x == xx
True
>>> len(x)
44
>>> len(y)
25
Мы видим, что длина исходного потока 44 байта
сокращаяется до длины выходного потока 25 троек.
Получаем сжатие почти в 2 раза. Можно возразить, что
длина тройки в битах больше, чем длина байта 8.
Однако эта проблема решается путем применения кодов
Хаффмана к выходному потоку троек, за счет чего
длина выходного потока в битах резко сокращается.
Такой подход применяется в алгоритме Deflate,
который используется в таких популярных и эффективных
архиваторах файлов, как ZIP, GZIP и др. Мы коротко
рассмотрим устройство алгоритма Deflate на следующей
лекции.