§ Задача сжатия

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

§ Алгоритм RLE

Существует один из простейших алгоритмов сжатия - оно называется RLE. Работает оно очень просто. Входящая строка разбивается на фрагменты одинаковых, идущих один за другим байтов и пишется сначала их количество, а потом сам повторяющийся фрагмент.
Рассмотрим фрагмент AAAAAAAAAAABBBBBBB. Здесь видно, что сначала идут одиннадцать букв A, а потом идут 7 букв B. Если это переписать в виде RLE-кодирования, то тогда будет выглядеть так 11A7B. Очевидно, что такая запись более короткая по сравнению с входящими данными. Но этот алгоритм совершенно неэффективен, если таких повторов немного. Существуют разные модификации метода сжатия RLE, но так или иначе, он неэффективен на обычных данных.

§ Метод скользящего окна

Он заключается в том, чтобы находить совпадения текста, которые отстоят на определенном расстоянии до текущего символа. Объясню сразу на примере. Есть строка "A FOX HAS FOX TAIL". Как можно заметить, тут есть одинаковые подстроки " FOX " (включая пробел).

A FOX HAS FOX TAIL
 ^^^^^   ^^^^^

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

"A" - ранее в словаре ничего не было, добавляем ее просто в вывод
" " - ранее не было, в вывод
"F" - аналогично
"O" - пропуск
"X" - пропуск
" " - было ранее, надо отступить назад на 4 символа и взять 1, но это неэффективно, пропуск
"H" - пропуск
"A" - было 7 символов назад, но 1 символ лишь, пропуск
"S" - пропуск
" FOX " - а вот тут как раз и найдено, 8 символов назад, 5 символов длина

Поскольку найдено совпадение более чем 2 символа, то это значит, что можно вместо " FOX " просто вставить ссылку, которая будет указывать на то, что 8 символов назад длиной 5 символов есть слово " FOX ". И поскольку это так, то начинается побайтовое копирование из ранее встреченного места.
Таким образом, получается сжатие за счет вставки более короткой ссылки по сравнению с теми данными, которые будут сжаты этой ссылкой.

§ Особенности метода сжатия

Компрессия методом скользящего окна может предусмотреть копирование и 20 символов, начиная с позиции всего лишь 1 символ назад. Представим ситуацию, когда получена такая строка:

"ABABABABABABABAB"

Казалось бы, как тут закодировать оптимально? Все очень просто. Сначала выдаем 2 символа "AB", после чего ставим ссылку на 2 символа назад и копируем 14 символов!
Разберем по шагам:

"A" пишем в поток
"B" пишем в поток
--> А тут находится ссылка -2 символа назад и 14 символов длиной. Там буква "A"
    Пишем в поток, получаем "ABA"
Сдвигаемся +1 вперед, пишем "B", получаем "ABAB"
Сдвигаемся +1 вперед, а там уже записана "A", копируем ее, получаем "ABABA"
Сдвигаемся +1 вперед, а там уже записана "B", копируем ее, получаем "ABABAB"
И так далее

В итоге получается исходная строка. Элегантно!

§ Блоки

Обычно есть 2 типа блоков при компрессии, блок 0 - это несжатые данные, и блок 1 - ссылка на данные и ее длина
Например, если идет блок несжатых данных, то указывается бит 0, и далее длина, которая обычно не превышает некоторого значения. Потом обязательно идет ссылка, после нее тоже может идти ссылка и так далее. Это определяется типом блока.
Приведу пример.
Допустим, закодировали строку "A FOX HAS FOX TAIL". Первые 9 символов - это несжатые данные:

Т L Строка
0 9 A FOX HAS
1 8 5
0 4 TAIL

• T = 0, бит в самом начале блока, который означает, что это несжатые данные;
• L = 9, длина данных, эти данные будут просто выданы в поток без всякого изменения
• Далее идет T=1, L=8, и 5. Это значит, что начиная с текущей позиции в потоке минус 8, будут копироваться байт за байтом 5 символов " FOX "
• Далее идет T=0, L=4, просто выдает в поток "TAIL"

Таким образом, декомпрессия прошла успешно.