Теория информации


Подстановочные или словарно-ориентированные алгоритмы сжатия информации - часть 2


Просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет "ПРО", в словаре она расположена со смещением 0 и имеет длину 3 символа, а следующим символом в буфере является "Д". Таким образом, выходным кодом будет тройка <0,3,'Д'>. После этого алгоритм сдвигает влево все содержимое окна на длину совпадающей подстроки и одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку "РАММНЫЕ ПРОД", в буфере - "УКТЫ ФИР". В данной ситуации совпадающей подстроки обнаружить не удаться и алгоритм выдаст код <0,0,'У'>, после чего сдвинет окно на один символ. Затем словарь будет содержать "АММНЫЕ ПРОДУ", а буфер - "КТЫ ФИРМ". И т.д.

Декодирование кодов LZ77 проще их получения, т.к. не нужно осуществлять поиск в словаре.

Недостатки LZ77:

  • с ростом размеров словаря скорость работы алгоритма-кодера пропорционально замедляется;
  • кодирование одиночных символов очень неэффективно.

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

Пример. Закодировать по алгоритму LZ77 строку "КРАСНАЯ КРАСКА".

В последней строчке, буква "А" берется не из словаря, т.к. она последняя.

Длина кода вычисляется следующим образом: длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря . Следовательно, длина двоичного кода смещения будет округленным в большую сторону размер словаря, а длина двоичного кода для длины подстроки будет округленным в большую сторону размер буфера. А символ кодируется 8 битами (например, ASCII+).

В последнем примере длина полученного кода равна

бит, против бит исходной длины строки.

В 1982 г. Сторером (Storer) и Шиманским (Szimanski) на базе LZ77 был разработан алгоритм LZSS, который отличается от LZ77 производимыми кодами.




- Начало -  - Назад -  - Вперед -