Добавлен: 04.04.2023
Просмотров: 348
Скачиваний: 3
Для применения метода адаптивного кодирования требуется определение вероятностных оценок до того, как количество переходов будет достаточно большим. Кроме того, вышеприведенные значения оценок вероятностей не определены для первого нахождения в состоянии A и дают вероятности перехода 0% и 100% в течение следующих нескольких попаданий в это состояние. Необходимо следить, чтобы переход в алгоритме Гуаццо в следующее состояние не осуществлялся с вероятностью 0% для любого бита, т.к. генерируемая кодировка может иметь бесконечную длину. Существует много способов корректировки вероятностных формул для учета этой проблемы. Один из вариантов – это незначительно варьировать значение оценок. Тогда получим скорректированные оценки: в состоянии A при переходе к цифре «0» оценка вероятности не превосходит значение , а в состоянии A при переходе к цифре «1» - . Здесь - некоторая положительная константа. Использование малых значений для делает вероятностные оценки, основанные на малых размерах выборки, более надежными в практической реализации алгоритма, тогда как большие значения делают их оценки менее точными. С другой стороны, адаптивный алгоритм быстрее распознает характеристики исходного файла, если используются небольшие значения для , но чаще делает плохие прогнозы. Однако, при сжатии большого объема данных, выбор константы становится в неуместным.
3.2 Построение графа состояний перехода
Рассмотрим частично построенную модель, которая включает в себя состояния A, B, ... , E (рис. 2a). На рисунке показаны переходы от A и B к C, а также переходы от C к D и E. Теперь, когда модель переходит в состояние C, некоторая контекстуальная информация теряется. По сути, теряется информация достигли ли мы состояния C из A или из B. Но вполне возможно, что выбор следующего состояния, D или E, совпадает с предыдущим состоянием, A или B. Самый простой способ узнать, существует ли такая корреляция, - это дублировать состояние C, создавая новое состояние C'. Для определенности, назовем этот процесс «клонированием». Это создает новую Марковскую модель (рис. 2b). После этого изменения модели, количество переходов от состояния C к состояниям D или E будет обновляться только когда в состояние C переходим из состояния A, в то время как количество переходов из C в D или Е будет обновляться когда C' переходит из состояния B. Таким образом, теперь модель хранит информацию о корреляции между состояниями A, B и D, E.
Рис. 2 (a) Часть марковской модели; (b) Марковская модель после процесса «клонирования»
Если вышеупомянутый процесс «клонирования» выполняется, когда на самом деле нет корреляции между предыдущим состоянием и следующим состоянием, то можно считать количество потерянных данных достаточно малым. Таким образом, модель стала содержать больше состояний и оценки вероятностей стали более восприимчивыми к статистическим колебаниям (т.к. каждое состояние посещается реже). Если такие корреляции существуют, улучшения в вероятностных оценках могут быть не удовлетворительными. В модели (рис. 2b), вполне возможно, что выбор следующего состояния D или E не может быть соотнесен с предыдущим состоянием A или B, но коррелирует с состоянием, находящимся непосредственно перед состоянием A или В. Если это так, то «клонирование» состояний A, B, и C' и пересмотр состояния C позволит модели обнаружить совпадения. Как правило, чем больше процессов «клонирования» выполняется, тем больше диапазон совпадений, которые могут быть обнаружены и использованы в целях прогнозирования.
Возможность «клонирования» конкретного состояния зависит от того, заходил ли алгоритм в это состояние не большое количество раз от каждого из двух (или более) различных состояний-предшественников. Ссылаясь на рис. 2(а), опять-таки, предположим, что текущее состояние-это и переход будет сделан, чтобы государство С. Далее предположим (рис. 2a), что текущим состоянием является состояние A и переход осуществляется в состояние B. Необходимость «клонирования» состояния C зависит от того, являются ли значения переходов AC и BC достаточно большими. Если, количество переходов BC равно нулю или мало по сравнению с количеством переходов AC, то вероятности, связанные с переходами, выходящими из C, будут отражать корреляцию с предшественником, являющимся A. «Клонирование» состояния C позволит выявить корреляции с состоянием B, однако, будет бесполезным, если переход BC используется редко.
3.3. Запуск и остановка построения модели
Начинать построение цепной марковской модели необходимо с любой минимальной модели, содержащей только одно состояние, способной генерировать любую последовательность сообщений. Оба перехода из этого состояния (для цифр 0 и 1) возвращаются в это состояние. Пример такой модели изображен на рисунке. 3a. После работы алгоритма «клонирования» эта модель с исходным состоянием быстро переходит в сложную модель с довольно большим количеством состояний.
На практике, некоторые преимущества можно получить, начав с менее тривиальной начальной модели. Так как, почти все компьютерные данные выровнены по байтам или словам, то корреляции, как правило, происходят между соседними байтами чаще, чем между соседними битами. Если начать с модели, которая соответствует структуре байтов, то процесс изучения характеристик исходного сообщения происходит быстрее, что приводит к лучшему сжатию данных. Простая модель байтовой структуры имеет 255 состояний, расположенных в виде двоичного дерева, с переходами от каждого конечного узла к корню дерева. Общая форма этого дерева, но с меньшим количеством узлов, изображенная на рис. 3b.
Рис. 3 (a) Исходное состояние Марковской цепи. (b) Первоначальная модель цепи Маркова для 4-битных символов.
Хотя древовидный начальный граф работает стабильно, его можно сделать еще лучше. Когда счетчики переходов достигают достаточных значений, они могут отображать корреляции между отдельными битами байта. Например, если третий бит в байте, являющийся нулем, подразумевает, что седьмой бит всегда является единицей, то древовидная модель сможет описать эту корреляцию. В общем случае состояние на k-ом уровне дерева () представляет собой корреляции с предыдущими k-1 битами. Объем левого контекста, который коррелирует с текущим состоянием, увеличивается от 0 бит до 7 бит, а затем корреляция отбрасывается при переходе к вершине (корню) дерева. Более удовлетворительной является модель, которая сохраняет постоянный объем левого контекста. Помимо эстетической привлекательности, такая модель имеет возможность изучать корреляции между последними несколькими битами одного байта и первыми битами следующего байта. Модель, которая сохраняет объем левого контекста постоянным, к сожалению, трудно показать на диаграмме. Проще всего ее изобразить на поверхности тора.
Если процесс «клонирования» не остановлен, то память ЭВМ будет использоваться неограниченно. С другой стороны, если алгоритм полностью остановлен, то теряется способность алгоритма «адаптироваться», в случае если некоторые характеристики исходного сообщения изменяются. Одним из возможных решений является установление ограничения на количество состояний. Когда предел достигнут, текущая Марковская модель отбрасывается, и алгоритм начинается с начальной модели. На практике это радикальное решение более эффективно, чем может показаться [17]. Однако менее радикальный вариант подхода легче реализовать. Можно сохранить последние k байт исходного сообщения, которые были прочитаны в буфер. При достижении предельного числа состояний модель отбрасывается, как и раньше. Затем, создается новая модель путем обработки k байтов в буфере, без добавления к закодированному сообщению. Это приведет к созданию новой модели с относительно небольшим числом состояний, соответствующих характеристикам последних k байтов сообщения. Несмотря на некоторую потерю производительности сжатия данных при этих рекламациях хранилища, потеря не очень велика и алгоритм сжатия сохраняет свою «адаптивность».
3.4 Практическое использование алгоритма Гуаццо
Кодирование Гуаццо ранее обсуждалось без особого учета проблем, связанных с практической реализацией. Есть две основные проблемные области, которые необходимо решить. Первая проблема заключается в том, что нижняя и верхняя границы интервала являются рациональными числами, которые по мере выполнения алгоритма должны вычисляться с еще большей точностью. Решение, принятое Гуаццо, заключается в ослаблении требования о том, чтобы эти границы были точно рассчитаны.
На каждом шаге алгоритма кодирования, интервал делится на две части. Если деление не выполняется точно в тех же пропорциях, что и отношение вероятностей того, что следующая цифра источника равна нулю или единице, то больших потерь нет. Метод кодирования продолжает работать, в том смысле, что декодирование может быть выполнено единственным образом. Все, что теряется, это небольшая эффективность кодирования. Поэтому Гуаццо предложил использовать критерий для определения того, насколько точно должна быть рассчитана точка деления между двумя поддиапазонами. Чем жестче этот критерий, тем лучше кодировка сообщения, но за счет вычислений приходится искать точку деления более точно.
Для реализации алгоритма выбирается более практичный подход - сохранение в вычислении точки деления столько значащих битов, сколько удобно поместить в одном компьютерном слове. И, как только биты сообщения генерируются (когда обе границы интервала имеют одну или более идентичных ведущих цифр), они удаляются из обеих переменных, которые записывают границы интервала. Они могут быть удалены логическими операциями сдвига влево. Таким образом, такая реализация поддерживает постоянную степень точности (около 30 значащих битов). При этом декодер не создает избыточный выходной бит. Алгоритм также должен гарантировать, что декодер сможет воспроизвести все исходное сообщение, не потеряв ни одного из последних битов. Таким образом, в конце алгоритма должен быть выведен только самый правый бит алгоритма. Максимизация количества битов, выводимых кодировщиком, устраняет неоднозначность любых ожидающих выбора интервальных разделов в декодере. Алгоритм декодирования точно отражает алгоритм кодирования. Действительно, за исключением некоторых задержек, когда он не может сразу решить, выбрать верхнюю или нижнюю половину раздела диапазона, его расчеты идут почти одинаково с расчетами кодировщика.
Заключение
Словарные коды класса Лив-Земпеля широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.
Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, описанные методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.
При декодировании по принятому коду определяется закодированное слово. В случае получения специального символа, сигнализирующего о передаче нового слова, принятое слово запоминается, и ему присваивается такой же, как и при кодировании, код. Таким образом, декодирование является однозначным, т. к. каждому слову соответствует свой собственный код.
Динамическое марковское сжатие (Dinamic Markov Compression, сокращенно DMC) - это общий алгоритм сжатия данных, который достигает лучших результатов сжатия, описанных в литературе. Например, текстовые файлы сжимаются до такой степени, что для каждого символа требуется в среднем чуть больше двух битов. В работе [17] приводятся результаты сравнения различных алгоритмов сжатия данных. Метод Зив-Лемпеля является самым быстрым алгоритмом, тогда как метод Клири-Виттена – самым медленным. С точки зрения требований к хранению, адаптивный алгоритм Хаффмана использует наименьший объем памяти, а метод Клири-Виттена обычно использует больше всех остальных алгоритмов. Однако это наблюдение должно быть квалифицировано фактом, что хранилище, используемое алгоритмами Зив-Лемпеля и Клири-Виттена, увеличивается безгранично, поскольку обрабатывается исходное сообщение. В качестве практического требования, объем хранилища, доступный для использования методов Зив-Лемпеля и Клири-Виттена, должен быть искусственно ограничен.
Хотя DMC составляет сильную конкуренцию методам Зив-Лемпеля и Клири-Виттена, алгоритм DMC является более общим подходом, который имеет несколько преимуществ. Оба метода Зив-Лемпеля и Клири-Виттена для практических целей ориентированы на байты. Действительно, можно реализовать бит-ориентированные версии Зив-Лемпеля и Клири-Виттена, но в случае Зив-Лемпеля результаты являются неудовлетворительными потому, что период обучения для метода Зив-Лемпеля становится намного дольше, чем для достижения сжатия типичных файлов. Бит-ориентированная версия Клири-Виттена непрактична по другой причине: если требуется достичь того же эффекта, что и Марковская модель четвертого порядка для байтов, необходимо использовать Марковскую модель 32-го порядка для битов. Объем памяти, необходимый для хранения таблиц расчетов, будет слишком большим.