Алгоритм Хаффмана

Алгоритм LZW.

Основан на упаковке не только повторяющихся символов, но и повторяющихся последовательностей. Существует огромное количество различных реализаций алгоритма сжатия LZW (Lempel, Ziv, Welch). Наиболее распространенный формат, использующий такой алгоритм – GIF. Рассмотрим одну из реализаций:

1. Создаем таблицу на 4096 элементов, каждый элемент таблицы соответствует цепочке символов, первые 256 – последовательности, состоящие из одного соответствующего символа. Для кода очистки (ClearCode) и кода конца информации (CodeEndOfInformation) зарезервированы значения 256 и 257. соответственно под коды цепочек остаются значения 258…4095.

2. Берем очередной символ из входной последовательности и добавляем его в конец текущей цепочки (в начале цепочка пуста).

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

4. Если цепочки нет, то заносим ее в таблицу. В выходную последовательность заносим запомненный код, а текущая цепочку полагаем равной последнему считанному символу. Далее переходим к шагу 2. Если таблица закончилась – нужно записать в выходной поток код очистки и перейти к шагу 1.

Пусть мы сжимаем последовательность 0,1,1,2,1,1,1. Тогда, согласно изложенному выше алгоритму добавим к изначально пустой цепочке “0” и проверим, есть ли цепочка “0” в таблице. Поскольку мы при инициализации занесли в таблицу все цепочки из одного символа, то цепочка “0” есть в таблице. Далее мы читаем следующий символ “1” из входного потока и проверяем, есть ли цепочка “0,1” в таблице. Такой цепочки в таблице пока нет. Мы заносим в таблицу цепочку “0,1” (с первым свободным кодом 258) и записываем в поток код “0”. Можно коротко представить архивацию так:

· “0” — есть в таблице;

· “0,1” — нет. Добавляем в таблицу <258>“0,1”. В поток: <0>;

· “1,1” — нет. В таблицу: <259>“1,1”. В поток: <1>;

· “1,2” — нет. В таблицу: <260>“1,2”. В поток: <1>;

· “2,1” — нет. В таблицу: <261>“2,1”. В поток: <2>;

· “1,1” — есть в таблице;

· “1,1,1” — нет. В таблицу: “1,1,1” <262>. В поток: <259>;

Последовательность кодов для данного примера, попадающих в выходной поток: <0>, <1>, <1>, <2>, <259>.

Данный алгоритм можно улучшить, заметив, что в компрессированном файле не может появится значение 512, до того как появилось 511. Таким образом, числа можно записывать сначала как 9-ти битные, потом, после встречи числа 512 как 10 битные, и так далее.

Использует то, что некоторые символы во входной цепочке встречаются более часто, чем другие. Сжатие происходит за счет того, что символы кодируются разным кол-вом битов, тем, что встречаются чаще соответствует более короткий код, чем для тех, что встречаются реже. Например, есть цепочка в которой встречаются символы A,B,C,D. При обычной кодировке каждый из них можно закодировать 2 битами A=00,B=01,C=10,D=11. И цепочка из 1000 символов будет иметь длину 2000 бит. Если некоторые символы встречается более часто, чем другие (например, в цепочке 800 символов A, 100 символов B, 50 символов С и 50 символов D), то если сопоставить символам коды разной длины A=0, B=10, C=110,D=111, то общая закодированной длина цепочки составит 800*1+100*2+50*3+50*3=1300 бит. Правда еще придется хранить таблицу соответствия кодов, но она занимает сравнительно немного места при больших размерах цепочек. Обычно коэффициент сжатия составляет около 2-х. Этот алгоритм редко применяют самостоятельно, но вместе с алгоритмом RLE или LZW он дает неплохие результаты.