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

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

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

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

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

Итак, начнем разбор:

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

Таким образом, получается сжатие за счет вставки более короткой ссылки по сравнению с теми данными, которые будут сжаты этой ссылкой.

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

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

Разберем по шагам:

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

Обычно есть 2 типа блоков при компрессии, блок 0 – это несжатые данные, и блок 1 – ссылка на данные и ее длина

Например, если идет блок несжатых данных, то указывается бит 0, и далее длина, которая обычно не превышает некоторого значения. Потом обязательно идет ссылка, после нее тоже может идти ссылка и так далее. Это определяется типом блока.

Приведу пример.

Допустим, закодировали строку A FOX HAS FOX TAIL. Первые 9 символов – это несжатые данные:

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