архиваторах
В разделе 2 мы познакомились с методами кодирования при известной
статистике источника. Было показано, что, применяя арифметическое
кодирование, можно получить скорость кодирования сколь угодно близкую к
нижнему пределу – к скорости создания информации источником. Далее в
разделе 3 мы получили такой же оптимистический результат и для случая, когда
статистические характеристики источника неизвестны. Понятно, что методы
раздела 3 можно применять к последовательностям букв (вместо отдельных
букв) и тем самым добиться скорости кодирования сколь угодно близкой к
энтропии на сообщение. Другой очевидный способ развития этих методов –
аппроксимация модели источника цепью Маркова достаточно высокого
порядка. Оба пути оказываются непрактичными. Во-первых, их сложность
быстро растет с увеличением длины блока или порядка аппроксимирующей
цепи Маркова. Во-вторых, при кодировании последовательностей конечной
длины, в частности, при кодировании типичных файлов пользователей
персональных компьютеров, асимптотически оптимальные методы не всегда
дают наилучший результат. Точнее говоря, различные способы кодирования,
имея асимптотически эквивалентные характеристики, могут существенно
различаться по эффективности при использовании в реальных условиях.
В данном разделе мы опишем наиболее эффективные способы
универсального кодирования источников. Наиболее известные и широко
применяемые – методы Зива-Лемпела (подразделы 4.3 и 4.4). Их описанию
предшествует описание так называемых «монотонных» кодов. Эти коды входят
как составная часть в один из алгоритмов Зива-Лемпела. В подразделе 4.2
описаны метод интервального кодирования и метод «стопка книг». Эти способы
кодирования тоже полезны для понимания алгоритмов Зива-Лемпела. Кроме
того, они имеют самостоятельное значение, в частности, они часто
используются при кодировании видеоинформации. Метод «стопка книг»
применяется также в рамках алгоритма Барроуза-Уилера. Далее мы приводим
описание алгоритмов-рекордсменов по сжатию – алгоритма предсказания по
частичному совпадению (PPM) и алгоритма Барроуза-Уилера. В завершение
раздела мы обсудим критерии сравнения эффективности архиваторов и
приведем характеристики лучших из них.
Точный математический анализ практических алгоритмов кодирования
сложен и выходит за рамки данного курса. Однако, как мы увидим из описания
алгоритмов, они являются естественным развитием асимптотически
эффективных теоретико-информационных методов, описанных в предыдущих
разделах.
4.1. Монотонные коды
Все рассмотренные в разделе 3 универсальные