Арифметическое кодирование

Сжатие данных

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется. Несмотря на то, что результаты исследований Шеннона были понастоящему востребованы лишь десятилетия спустя, трудно переоценить их значение. Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитивному кодированию символов. Словарные алгоритмы позволяли кодировать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании.

История появления

История разработки и исследования одного из наиболее популярных и эффективных методов сжатия данных — арифметического кодирования — восходит к классическому коду Шеннона. Э.Н.Гильберт и Э. Ф. Мур предложили блочный код, подобный коду Шеннона, но не требующий предварительного упорядочивания блоков из n букв по вероятностям. А именно, пусть X — стационарный источник в алфавите А. Все наборы из n букв алфавита А упорядочим лексикографически. П.Элайесом была предложена процедура последовательного вычисления границ полуинтервала [Q(хⁿ),Q(хⁿ) + Р(хⁿ))по мере поступления букв блока хn. Она естественно вытекает из того, что соответствующий слову х ∈ А* полуинтервал по определению раз­деляется на полуинтервалы, соответствующие словам xa₁,xa₂... xa_k. Однако в таком виде арифметическое кодирование невозможно использо­вать на практике при больших n, поскольку требуемая точность вычис­лений быстро возрастает при увеличении длины блока, Й. Риссанен предложил алгоритм округленного вычисления границ полуинтер­вала, использующий арифметические операции с числами ограниченной длины. Этот алгоритм позволяет кодировать слова хⁿ ∈ Аⁿ с любой наперед заданной избыточностью при n → ∞. Кроме того, в методе Й.Риссанена кодовое слово f(хⁿ) можно вычислять и передавать по­разрядно по мере поступления букв слова хⁿ. Это усовершенствование оказалось решающим на пути практического использования арифмети­ческого кодирования. Существует несколько версий арифметического кодирования Й. Риссанена, наиболее известная из них разработана И.Уиттеном с соавторами. Оценки эффективности этого алгоритма для источников без памяти содержатся в работе Б. Я. Рябко и А. Н. Фионова. Отличные от метода И. Риссанена варианты арифметического коди­рования предложены Ю. М. Штарьковым и Б. Я. Рябко.

Пример арифметического кодирования

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дро- би, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дро- би на интервале [0, 1) (0 - включается, 1 - нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов. Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ	Частота	Вероятность	Диапазон
О	3	0.3	[0.0; 0.3)
К	2	0.2	[О.З; 0.5)
В	2	0.2	[0.5; 0.7)
Р	1	0.1	[0.7; 0.8)
А	1	0.1	[0.8; 0.9)
"."	1	0.1	[0.9; 1.0)

Будем считать, что эта таблица известна в компрессоре и декомпрессоре.Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон,соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д. Используя исходную таблицу диапазонов, кодируем текст "КОВ.КОРОВА": Исходный рабочий интервал[0, 1). Символ "К" [0.3; 0.5) получаем [0.3000; 0.5000). Символ "О" [0.0; 0.3) получаем [0.3000; 0.3600). Символ "В" [0.5; 0.7) получаем [0.3300; 0.3420). Символ "." [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 1.2.

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [li, hi). Для последовательности "КОВ.", состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки. Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только "К", поскольку только его диапазон включает это число. В качестве интервала берется диапазон "К" - [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для "О", включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.

Характеристики арифметического алгоритма

Характеристики арифметического алгоритма: Лучшая и худшая степень сжатия: лучшая > 8 (возможно кодирование менее бита на символ), худшая - 1. Плюсы алгоритма: обеспечивает лучшую степень сжатия, чем алгоритм Хаффмана (на типичных данных на 1-10%). Характерные особенности: обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H — информационная энтропия источника. В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит 010101…0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.

Курсовой проект

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

Описание программы

Описанный выше процесс кодирования невозможно реализовать на практике, т.к. в нем предполагается, что в переменных l и h хранятся числа с неограниченной точностью. По существу, результат кодирования – это вещественное число с очень большой точностью. Например, файл объемом 1Мб будет сжиматься, скажем, до 500 КБ, в котором будет записано одно число. Арифметические операции с такими числами реализовать сложно и долго. В данном курсовом проекте, практическая реализация метода арифметического кодирования основана на кодировании блоками по 16 символов.

Результаты тестирования

Для тестирования программы были выбраны три тестовых файла размером 10 байт, 528 байт и 3 кбайта. В результате тестирования были получены следующие результаты: файл размером 10 байт сжат до 8 байт, остальные сжаты на 50%

Ссылки

• http://ru.wikipedia.org/wiki/Сжатие_без_потерь
• http://ru.wikipedia.org/wiki/Арифметическое_кодирование
• http://www.compression.ru/arctest/descript/comp-hist.htm
• http://www.sernam.ru/cod_3.php