1.3. Декодирование

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

1. Множество префиксных кодов один раз выбрано и используется всеми кодерами и декодерами. Такой метод используется в факсимильной связи (см. § 1.6). Создатели стандарта сжатия для факс-машин выбрали восемь «эталонных» документов, проанализировали их статистические свойства и взяли их за основу при отборе подходящего префиксного кода, представленного в табл. 1.20. Говоря техническим языком, эталонные документы были выбраны для обучения и тренировки алгоритма. Обучение алгоритма является простейшим подходом к статистическому сжатию, и его качество сильно зависит от того, насколько реальные сжимаемые файлы походят на выбранные для тренировки и обучения образцы.

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

3. Адаптивное сжатие применяется как кодером, так и декодером. Кодер начинает работать, не зная статистических свойств объекта сжатия. Поэтому первая часть данных сжимается не оптимальным образом, однако, по мере сжатия и сбора статистики, кодер улучшает используемый префиксный код, что приводит к улучшению компрессии. Алгоритм должен быть разработан таким образом, чтобы декодер мог повторить каждый шаг кодера, собрать ту же статистику и улучшить префиксный код в точности тем же способом. Пример адаптивного сжатия рассмотрен в § 1.5.