Арифметическое кодирование
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия . Арифметическое кодирование – блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов, в отличие от кодов Хаффмана , которые являются неблочными, т.е. каждой букве входного алфавита ставится в соответствие определенный выходной код.
Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала
111
(26/27; 1 ] " 31/32 ®
110
(8/9; 26/27 ] " 15/16 ®
10
(2/3; 8/9 ]
101
(22/27; 8/9 ] " 7/8 ®
100
(2/3; 22/27 ] " 3/4 ®
0
(0 ; 2/3 ]
01
(4/9; 2/3 ]
101
(16/27; 2/3 ] " 5/8 ®
100
(4/9; 16/27 ] " 1/2 ®
00
(0; 4/9 ]
001
(8/27; 4/9 ] " 3/8 ®
000
(0; 8/27 ] " 1/4 ®
Средняя длина кода на единицу сообщения
Приведем процедуру арифметического кодирования для последовательности произвольной длины:
While there are still input symbols do
get an input symbol
code_range = high - low.
high = low + code_range*high_range(symbol)
low = low + code_range*low_range(symbol)
Декодеру , как и кодеру, известна таблица распределения отрезков, выделенных символам алфавита источника. Декодирование арифметического кода сообщения происходит по следующему алгоритму:
Шаг 1 По таблице отрезков символов алфавита определяется интервал, содержащий текущий код сообщения – и по этому интервалу из той же таблицы однозначно определяется символ исходного сообщения. Если это маркер конца сообщения, то конец, иначе – переход к шагу 2 .
Шаг 2 Из текущего кода вычитается нижняя граница содержащего его интервала. Полученная разность делится на длину этого интервала. Полученное значение считается новым текущим кодом. Переход к шагу 1 .
Рассмотрим пример декодирования сообщения, сжатого по алгоритму арифметического кодирования.
Пример 3 Длина исходного сообщения 10 символов. Двоичный арифметический кодсообщения 000101000001100001011111 2 =1316259 10 .
Вещественное
число, принадлежащее интервалу, однозначно определяющему закодированное
сообщение, 
. Это число и будет текущим
кодом
сообщения.
По исходной таблице значений д.с.в. и назначенных им интервалов (таблица 2.7 ) определяется отрезок, которому принадлежит это число, - Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно
Лекция 13 Приемы и методы работы со сжатыми данными Лектор Ст. преподаватель Купо А.Н. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики кафедра ТОРС Задание и методические
УДК 519.6 Особенности кодирования текста с помощью алгоритма Хаффмана Кизянов Антон Олегович Приамурский государственный университет имени Шолом-Алейхема Студент Кузьмина Богдана Сергеевна Приамурский
ЛАБОРАТОРНАЯ РАБОТА Способы задания и основные характеристики сверточных кодов Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными
УДК 004.8 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМ ШКОЛЬНОГО РАСПИСАНИЯ Гущина О. А. Генетический алгоритм (ГА) адаптивный поисковый алгоритм, основанный на эволюционных факторах
Дискретная математика Часть 2 Кочетов Юрий Андреевич http://www.math.nsc.ru/lbrt/k5/dm.html Лекция 1 Алгоритмы, сортировки, AVL деревья 1 Алгоритмы и их сложность Компьютеры выполняют (пока) лишь корректно
Метод Хаффмана является простым, но
эффективным только в том случае, когда вероятности появления символов равны
числам , где - любое целое
положительное число. Это связано с тем, что код Хаффмана присваивает каждому
символу алфавита код с целым числом бит. Вместе с тем в теории информации
известно, что, например, при вероятности появления символа равной 0,4, ему в
идеале следует поставить код длиной 
бит. Понятно, что при построении кодов
Хаффмана нельзя задать длину кода в 1,32 бита, а только лишь в 1 или 2 бита,
что приведет в результате к ухудшению сжатия данных. Арифметическое кодирование
решает эту проблему путем присвоения кода всему, обычно, большому передаваемому
файлу вместо кодирования отдельных символов.
Идею арифметического кодирования
лучше всего рассмотреть на простом примере. Предположим, что необходимо
закодировать три символа входного потока, для определенности – это строка SWISS_MISS с заданными частотами появления символов: S – 0,5, W – 0,1, I –
0,2, M – 0,1 и _ - 0,1. В арифметическом
кодере каждый символ представляется интервалом в диапазоне чисел }
