Добавлен: 04.04.2023
Просмотров: 340
Скачиваний: 3
Для того чтобы показать, что кодирование Гуаццо достигает почти оптимальных кодов, сравним его работу с довольно популярным кодированием Хаффмана [6].
Рассмотрим пример кодирования Хаффмана сообщений, генерируемых цепной моделью Маркова, приведенной на рисунке 1.
Рис. 1 Пример модели цепи Маркова.
Кодирование Хаффмана не может быть непосредственно применено к двоичному исходному алфавиту. Необходимость предоставления отдельных кодов для нулевого бита и одного бита означает, что сжатие невозможно. Обычным способом решения этой проблемы является создание довольно большого исходного алфавита. Это легко сделать, сгруппировав символы сообщения вместе. Например, мы можем выбрать работу с группами из трех битов, получая алфавит размером 8. Посредством анализа модели Маркова на рис. 1, включающей вычисление вероятностей состояния равновесия, мы вычислили вероятность возникновения для каждого символа в новом исходном алфавите. Эти вероятности могут быть использованы для получения кодов Хаффмана.
Если кодирование тройками Хаффмана используется для кодирования длинного сообщения, генерируемого моделью цепи Маркова, тогда достигается умеренная степень сжатия. Фактически, длинное сообщение будет в среднем сжато примерно до 90,3% от его первоначального размера. Однако это число значительно больше, чем теоретико-информационная нижняя граница. Простой расчет энтропии в источнике информации показывает, что сжатие до 81,9% от исходного размера может быть достижимым.
Есть две причины, по которым кодирование Хаффмана не достигает конкретной нижней границы. Первая причина заключается в том, что кодирование Хаффмана может быть свободно от избыточности, только если частоты появления символов в исходном алфавите имеет целочисленные степени 2. Вторая причина заключается в том, что кодирование Хаффмана использует совпадение только между битами, которые были сгруппированы вместе. Однако этот факт игнорирует совпадение между последним битом первой группы и первым битом второй группы. Таким образом, вторая группа кодируется неоптимальным образом.
Эти две проблемы со схемой Хаффмана улучшаются только путем выбора больших групп битов для построения исходного алфавита. Если выбираются группы большего размера, эффективность кодирования приближается к нижней границе, но размер алфавита растет в геометрической прогрессии. Размер таблиц, необходимых для хранения кодировок Хаффмана, также растет в геометрической прогрессии, в то время как вычислительные затраты на создание этих таблиц становятся неосуществимыми.
Альтернативой неосторожному расширению размера алфавита является использование нескольких наборов кодирования Хаффмана. Выбор набора кодирования для использования в следующем символе сообщения определяется предыдущими символами. Такой подход может быть реализован для достижения компромисса между производительностью сжатия данных и используемым объемом памяти, необходимых для хранения таблиц кодов Хаффмана [12].
2.2. Кодирование Гуаццо, примененное к модели Маркова
У метода Гуаццо нет недостатков, отмеченных ранее для кодирования Хаффмана. Для достаточно длинных сообщений метод может генерировать кодировки, сколь угодно близкие к теоретико-информационной нижней границе. Первым шагом в обосновании работы двоичной версии метода Гуаццо является рассмотрение выходной кодировки в виде двоичной дроби. Например, если кодирование вывода начинается с цифр «0 1 1 0 1 ...», то это двоичное число рассматривается как число, начинающееся с цифр «0.01101...». Это число имеет значение, близкое к выраженному в десятичной дроби. Задача алгоритма кодирования состоит в выборе дробного числа в диапазоне от нуля до единицы, которое кодирует все исходное сообщение.
Учитывая, что алгоритм Гуаццо имеет доступ к цепной модели Маркова, например, в виде, изображенном на рис. 1, можно проследить, как алгоритм кодирования будет выбирать из достаточно длинного источника сообщение, начинающееся с заданной последовательности цифр «0 1 1 1 0 0 1 ...». Изначально алгоритм кодирования Гуаццо выбирает двоичные дроби, лежащие в диапазоне от «0.000...» до «0.111...» включительно, произвольно. Алгоритм Гуаццо определяет по цепной модели Маркова, что первая цифра исходного сообщения с одинаковой вероятностью равна нулю или единице. Поэтому эта цифра делит пространство двоичных дробей на две половины: если дробь начинается с «0», то она находится в замкнутом интервале [0.000..., 0.0111...], если же начинается с «1», то она находится в замкнутом интервале [0.1000..., 0.111...]. В приведенном примере, исходное сообщение начинается с нуля, поэтому алгоритм выберет интервал [0.000..., 0.0111...].
Первая цифра источника данных приводит к состоянию, обозначенному на рисунке 1 через «B». В этом состоянии вероятность того, что следующая цифра будет нулем, в два раза больше, чем если бы она была единицей. Вследствие этого, алгоритм Гуаццо определяет диапазон доступных двоичных дробей и делит их на две части в соотношении 2:1. Далее алгоритм получает два интервала: подинтервал [0.000... , 0.010101...], который представляет собой исходные сообщения, начинающиеся с «0.00...», и подинтервал [0.010101... , 0.0111... ], представляющий собой сообщения, начинающиеся с «0.01». Первый из этих подинтервалов имеет вдвое больший диапазон, чем второй. Т.к. вторая цифра исходного сообщения равна единице, то ограничиваемся вторым подинтервалом. Поскольку эта цифра исходных данных приводит нас к состоянию C в цепной модели Маркова (рис. 1), то доступный диапазон кодировок сообщений в дальнейшем делится в соотношении 3:2.
В конечном итоге, алгоритм Гуаццо определит, что наше исходное сообщение, начинающееся с «0111001», должно быть представлено некоторой двоичной дробью в интервале [0.011100110101... , 0.01110100101111...]. Поскольку нижняя и верхняя границы интервала начинаются с одних и тех же пяти цифр, алгоритм кодирования определит последовательность символов передаваемого сообщения, как «0 1 1 1 0».
Если рассматривать требования к практической компьютерной реализации, то очевидно, что интервальные границы не должны вычисляться как дроби, содержащие неограниченное количество цифр. Необходимо, чтобы только нужное количество битов было сохранено в вычислениях интервальных границ. Способ, которым доступное пространство двоичных кодировок разделяется на каждом шаге алгоритма, распределяет закодированные сообщения максимально равномерно по всему исходному пространству. Важно распределить кодировки равномерно, иначе некоторые кодировки будут излишне близки друг к другу, как следствие, два значения, которые почти одинаковы, потребуют больше битов, чтобы различать их, чем два значения, которые находятся дальше друг от друга.
Описанный процесс кодирования легко обратим. Алгоритм декодирования имеет доступ к той же марковской цепной модели источника информации, которая использовалась в процессе кодирования. Он начинается с построения того же интервала [0.000..., 0.111...] возможных кодировок и разделяет его таким же образом, как при кодировании. Затем, проверка ведущего бита в закодированном сообщении определяет, какой из двух разделов должен был использоваться и, следовательно, какой должна быть первая исходная цифра. Как только эта первая цифра известна, алгоритм декодирования может выбрать соответствующий подинтервал и повторить дальнейшее деление на две части. Затем определяется вторая цифра закодированного сообщения и так далее.
2.3 Адаптивное кодирование
Сжатие данных обычно реализовывается в виде двухэтапного метода. Начальный этап выполняется для обнаружения характеристик исходного сообщения. Затем, используя эти характеристики, реализуется второй этап для выполнения сжатия. Например, если мы используем кодировку Хаффмана, то на первом этапе будем считать частоты появления каждого символа. Данные, полученные с использованием кодирования Хаффмана, могут быть построены до того, как второй этап выполнит кодирование. Чтобы обеспечить возможность декодирования сжатых данных, необходимо использовать фиксированную схему кодирования или включить сведения о схеме сжатия в сжатые данные. Хотя двухэтапную реализацию метода сжатия данных несложно разработать, на практике обычно применяют одноэтапный алгоритм адаптивной реализации сжатия данных. Также одноэтапные реализации предпочтительны, поскольку они не требуют сохранения всего сообщения в оперативной памяти компьютера перед кодированием.
Существует одноэтапный метод сжатия данных, который на практике обеспечивает сжатие, очень близкое к полученному с помощью двухэтапного методов. Основная идея этого метода заключается в том, что схема кодирования динамически изменяется во время кодирования сообщения. Схема кодирования, используемая для k-го символа сообщения (), основана на характеристиках предыдущих k-1 символов в сообщении. Этот метод известен как адаптивное кодирование. На практике адаптивное кодирование Хаффмана обеспечивает сжатие данных, которое незначительно отличается от обычного двухэтапного кодирования Хаффмана, но затрачивает большее количество ресурсов ЭВМ [13, 14].
Методы Зив-Лемпеля и Клири-Виттена также являются адаптивными методами кодирования. Основная идея кодирования метода Зив-Лемпеля состоит в том, что группа символов в сообщении может быть заменена указателем на более раннее появление этой группы символов в сообщении [17]. После короткого периода обучения эти указатели будут последовательно занимать меньше битов, чем группы символов, которые они заменяют. Программно этот алгоритм может быть реализован таким образом, чтобы быть намного быстрее, чем адаптивное кодирование Хаффмана, при этом достигается гораздо лучшее сжатие данных. Тем не менее, алгоритм Зив-Лемпеля использует только совпадение между исходными символами, которые группируются вместе: весь контекст отбрасывается между такими группами. Таким образом, схема страдает тем же дефектом, что и описанная в разделе 2.1; потеря контекста улучшается только за счет использования более длинных групп с соответствующим потреблением ресурсов памяти.
Метод Клири и Виттена использует предыдущие k символов в сообщении для предсказания вероятностей появления текущего символа сообщения и использует эти вероятности для управления арифметической схемой кодирования [15]. С этой целью сохраняется таблица всех предыдущих вхождений строк длины k, а также количество символов, следующих за строкой. Однако, если определенная комбинация из k символов не появилась ранее в сообщении, мы не сможем оценить вероятности появления символа. В этом случае метод Клири и Виттена пропускает предыдущие k-1 символов, которые смогут лишь оценить вероятности. Если комбинация предшествующих k-l символов также ранее не определялась алгоритмом, произойдет другой пропуск кода и оценивание вероятностей и так далее. Каждый набо k строк может рассматриваться как представление достаточно большой модели марковской цепи k-го порядка. Вероятности, используемые в цепных Марковских моделях, изучаются по мере обработки сообщения. А так как декодер может быть запрограммирован так же, как и кодировщик, то легко построить адаптивный алгоритм сжатия.
Алгоритм кодирования Гуаццо в высшей степени подходит для использования в адаптивных схемах кодирования. Единственным аспектом алгоритма, который нуждается в динамическом изменении, является источник вероятностных оценок для символов сообщения. На каждом этапе процесса кодирования алгоритм требует оценки вероятности каждого из возможных символов последующего сообщения. Для алгоритма кодирования Гуаццо не имеет значения, получены ли эти оценки вероятности из статической марковской модели или из динамически изменяющейся. В такой динамической модели, как набор состояний, так и вероятности перехода могут измениться, на основе символов сообщения, видимых до текущего шага алгоритма.
Декодирование сообщения, полученного с помощью адаптивной реализации кодирования алгоритма Гуаццо, также достаточно просто реализуется на практике. Все, что нужно сделать алгоритму декодирования, это воссоздать ту же последовательность изменений в динамически изменяющейся марковской модели, что и алгоритм кодирования. Поскольку алгоритм декодирования видит точно такую же последовательность незакодированных цифр, как и алгоритм кодирования, особых в реализации трудностей не возникает.
3. Динамическое построение предиктивных марковских цепей
3.1. Выбор вероятностей
Модель Марковской цепи можно охарактеризовать как ориентированный граф с вероятностями, прикрепленными к ребрам графа. Можно выделить два различных аспекта проблемы автоматического создания такой цепной марковской модели. Одна часть - это определение подходящих вероятностей для размещения на ребрах графа. Другая часть - это определение структуры самого графа.
Предположим, что существуют корреляции между символом сообщения и непосредственно предшествующими символами. Если бы считывать двоичные цифры из исходного сообщения, то можно отследить соответствующие переходы в модели и подсчитать, сколько раз каждый переход был принят в модели. Эти подсчеты дают адекватные оценки вероятностей для переходов, которые были сделаны много раз. Точнее, если переход из состояния A к цифре «0» был выполнен раз, а переход к цифре «1» был выполнен раз, то справедливы следующие оценки вероятностей: в состоянии A при переходе к цифре «0» оценка вероятности не превосходит значение , а в состоянии A при переходе к цифре «1» - [16]. При это, чем чаще осуществлялся переход в состояние A, тем точнее вероятностные оценки.