Давайте посмотрим на алгоритм сжатия, лежащий в основе compress и сжатия файлов .gif в Unix.

Алгоритм Lempel Ziv Welch [LZW] - это жадный алгоритм сжатия без потерь, который работает путем замены повторяющихся шаблонов более короткими кодами для экономии места.

Без потерь - это форма сжатия, при которой данные не теряются.

Мы рассмотрим алгоритм и рассмотрим его реализацию на Python.

Для простоты мы ограничим обсуждение кодировкой символов ASCII.

Кодировка

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

LZW использует словарь, который отображает фразу в уникальный код. Первые 256 записей в словаре - это отдельные символы ASCII, сопоставленные с их числовым кодом.

Например, вначале словарь может выглядеть примерно так:

{
  "A": "65",
  "B": "66",
  ....
  "a": "97",
  "b": "98"
}

Теперь мы пройдемся по остальному тексту - символ за символом, - выстраивая последовательность фраз / символов. Если включение нового символа создает фразу, которой в настоящее время не существует в нашем словаре, мы проигнорируем этот прерывающий символ и выведем код, который соответствует предыдущему состоянию нашей последовательности символов.

Затем мы добавим эту новую фразу с этим знаком разбиения в наш словарь и присвоим ей новый код.

Например, предположим, что наш вводимый текст:

... app [cursor] appl ....

Наш словарь может выглядеть примерно так:

{
  ...
  "app": 324,
  ....
}

Следующая встречающаяся порция текста - это «приложение», которого в настоящее время нет в нашем словаре.

Итак, мы выведем код для существующего фразового соответствия слова «приложение», а затем добавим в словарь «приложение» с новым кодом.

Результат после этой итерации может выглядеть примерно так:

Dictionary: { … “app”: 324, “appl”: 325 …}
Output: … 324 …

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

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

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

Чтобы полностью понять, откуда происходит сжатие, давайте рассмотрим более крупный пример:

34832 : 'Harry'
34833 : 'Potter'
34834 : 'Hogwarts'
34835 : 'magic'

Если мы сохраним код 34833 как короткое беззнаковое сокращение, например, это будет стоить 16 bits. Однако это позволит нам представить 6 characters * 8 bits = 48 bits полезную информацию. Вообще говоря, чем выше поднимаются коды, тем большее сжатие мы получаем.

Расшифровка

Процесс декодирования на самом деле прямо противоположен процессу кодирования. Единственное изменение состоит в том, что нам нужно воссоздать словарь с 256 кодами ASCII в качестве предварительного шага перед тем, как можно будет начать остальную декомпрессию.

Затем мы читаем сжатые данные и с помощью нашего словаря кодов переводим коды обратно в исходный текст.

Кодирование переменной длины

В большинстве реализаций этого алгоритма используется идея кода переменной ширины.

Это определяет верхнюю границу максимальной длины кода, тем самым предотвращая утечку памяти для этого алгоритма. Например, если мы выбрали 8-битный код в качестве ширины, максимальное количество кодов будет 256 (2⁸).

Если мы выберем 12-битный код в качестве ширины, у нас может быть до 4096 кодов и так далее.

Если наш словарь вырос и включил все 4096 кодов, остальная часть документа кодируется с использованием существующего словаря, но новые коды не добавляются.

Код

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

Следующая реализация при запуске в Повести о двух городах приводит к получению сжатого файла размером 532 КБ, что на 32% меньше, чем исходный размер 777 КБ.

Следующая реализация является адаптированной версией этого кода:

Подведение итогов

Этот алгоритм, хотя и достаточно простой для понимания и реализации, не всегда является правильным выбором. Плохо работает, когда текст короткий и уникальный; алгоритм отдает предпочтение избыточным данным.

Если вам нравится это техническое погружение в современные алгоритмы, подпишитесь на меня на Medium, Twitter или посетите мой личный сайт, чтобы увидеть больше сообщений.