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

      На практике для хранения таблицы используется хэш-таблица. Таблица состоит из элементов в количестве не меньшем, чем 8192 (2¹³) . Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа.

      В качестве хэш-функции при этом используется:

      Таким образом, за считанное количество сравнений, мы получаем искомый код или сообщение, что такого кода в таблице нет.

      Лучший коэффициент, очевидно, будет получен для цепочки одинаковых байт большой длины (т.е. для 8-битного изображения, все точки которого имеют, для определенности, цвет 0). При этом в 258 строку таблицы мы запишем строку "0, 0", в 259 - "0, 0, 0", ... в 4095 - строку из 3809 (=4095-256) нулей. При этом в поток попадет 3810 кодов, включая код очистки. Следовательно, посчитав сумму арифметической прогрессии от 1 до 3809 (т.е. длину сжатой цепочки) и поделив ее на 3810*12/8 (в поток записываются 12-битные коды), мы получим лучший коэффициент компрессии.

      Худший коэффициент будет получен, если мы ни разу не встретим подстроку, которая уже есть в таблице (в ней не должно встретиться ни одной одинаковой пары символов).

      LZW реализован в форматах GIF и TIFF.
 

Упражнение.
1. Получите лучший коэффициент компрессии.