источника
Рассмотренные в предыдущем разделе алгоритмы кодирования эффективны и
практичны. Однако их общим недостатком является то, что они эффективны только в том
случае, когда вероятностная модель источника совпадает или очень близка к модели, для
которой строился код. В данном разделе мы рассмотрим задачу кодирования источника в
условиях отсутствия информации или неполной информированности кодера и декодера о
характеристиках источника. Методы кодирования для такой постановки задачи называют
универсальными. Очевидная область применения универсального кодирования – создание
архиваторов для хранения файлов в памяти ЭВМ. Эта задача служит полигоном для
сопоставления эффективности различных подходов. В то же время имеются и другие
важные приложения. Универсальные методы кодирования источников без потери
качества являются важной составной частью современных кодеров аудио- и
видеоинформации.
Мы начнем данный раздел с логически простых схем кодирования, на примере
которых мы убедимся в том, что скорость кодирования при неизвестной статистике может
быть сделана сколь угодно близкой к скорости создания информации источником. Мы
оценим потери, связанные с отсутствием априорной информации. Практическая
значимость изучаемых методов проявится в следующем разделе, где мы рассмотрим
широко применяемые в известных архиваторах алгоритмы Зива-Лемпела, а также
алгоритмы, обеспечивающие рекордно высокое сжатие информации – это предсказание по
частичному совпадению и алгоритм Барроуза-Виллера.
3.1. Постановка задачи универсального кодирования источников
Универсальное кодирование предполагает, что входом кодера является
последовательность сообщений x = (x1,…, xn) некоторого источника X . Алфавит кодера,
длина последовательности n , алгоритм работы кодера известны декодеру. Статистичес-
кие свойства источника заранее неизвестны. Задача, как и прежде, состоит в том, чтобы
обеспечить эффективное кодирование, то есть найти представление последовательности
источника двоичной кодовой последовательностью наименьшей длины. Однако, решить
задачу в такой постановке нам не удастся. Не может существовать алгоритм кодирования,
который бы «сжимал» любые последовательности источника. Мы уже говорили (см. п.
2.2), что при неравномерном префиксном кодировании уменьшение длины одной кодовой
последовательности на 1 символ достигается увеличением длины двух других последова-
тельностей на 1 символ. Если считать все последовательности источника