Сайт о телевидении

Транскрипт

1 Арифметическое кодирование Иринёв Антон, Каширин Виктор Оглавление 1. Введение Описание алгоритма Анализ алгоритма Адаптивный алгоритм... 7 Литература... 9

2 1. Введение В наши дни информация является главным инструментом в развитии фундаментальных наук, технологий, методов работы и обучения. Посредством передачи информации люди обмениваются опытом, знаниями и полезными сведениями, что, несомненно, ведет к прогрессу во всех областях человеческой деятельности. Объёмы передаваемой электронной информации возрастают с огромной скоростью. Это связанно, прежде всего, с развитием Интернета и беспроводных технологий связи. Однако, несмотря на высокую пропускную способность современных каналов связи, передача больших объёмов информации всегда сопряжена со значительными временными затратами. Именно поэтому возникла такая область информационных технологий, как сжатие данных. Теория сжатия данных объединяет в себе несколько различных направлений. В рамках данной теории методы принято разделять на методы кодирования информации без потерь (lossless) и методы кодирования информации с потерями (lossy). Как следует из названий, методы первой группы не ведут к информационным потерям (т.е. первоначальная информация может быть в точности восстановлена из сжатого состояния), тогда как использование методов второй группы сопряжено с такими потерями. Применение сжатия без потерь особенно важно для текстовой информации, записанной на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. В свою очередь сжатие с потерями применяется к информации, содержащей отдельные несущественные составляющие, которые при определенных условиях могут быть частично или полностью удалены. Методы сжатия с потерями часто используются для сжатия звука и изображений. В этой статье мы рассмотрим один из методов сжатия информации без потерь, который носит название "Арифметическое кодирование". Основой арифметического кодирования является неопубликованный алгоритм П. Элайеса. Также существенный вклад в развитие данного метода в разное время внесли П. Говард, М. Гуаззо, Д. Клири, Г. Лэнгдон, Э. Моффат, Р. Нил, Р. Паско, Д. Риссанен, Ф. Рубин, Я. Уиттен и М. Шиндлер. 2. Описание алгоритма Метод арифметического кодирования основан на идее преобразования входного потока в число с плавающей точкой из интервала (n - число символов в нашем алфавите), делящих отрезок соответственно частотам вхождения символов в текст. 1 procedure encode_text(frequency); 2 begin 3 low = 0.0; 4 high = 1.0; 5 repeat 6 symbol = next_symbol(); 7 range = high - low; 8 high = low + range *frequency; 9 low = low + range *frequency; 10 until (symbol == EOF); 11 end; В строках 3-4 происходит инициализация стартового отрезка. В строках 5-10 алгоритм последовательно обрабатывает каждый символ текста. В строках 5 и 10 вызывается процедура next_symbol, возвращающая последующий символ декодируемого текста. Переменная symbol хранит в себе номер символа в алфавите. С учетом частоты вхождения конкретного символа изменяется рабочий интервал. По завершении обработки всех символов текста получаем искомый интервал - <= (value - low)/(high - low)) and ((value - low)/(high - low) < frequency); 9 range = high low; 10 high = low + range *cum_freq ; 11 low = low + range *cum_freq ; 12 print(symbol); 13 until (symbol == EOF); 14 end; В строках 3-4 происходит инициализация стартового отрезка. В цикле 5 13 мы декодируем символ за символом, пока не приходим к метке конца текста. В цикле 6 8 алгоритм, с помощью перебора алфавита, находит символ, попадающий в конкретный интервал. В строках 9 12 сужается интервал для следующего шага, выводится декодированный символ. 3. Анализ алгоритма В теории сжатия данных без потерь существуют два основных способа кодирования информации: статистический и словарный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные - метод Лемпеля-Зива. В статистическом сжатии 4

5 каждому символу присваивается код, основанный на вероятности его появления в тексте. Символы, вероятность появления которых высока, получают короткие коды, и наоборот. В основе словарных методов лежит идея, совершенно отличная от идеи статистического сжатия. Словарный кодировщик добивается сжатия с помощью замены групп последовательных символов индексами некоторого словаря. Словарь есть список таких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены таким образом, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Любая практическая схема словарного сжатия может быть сведена к соответствующей статистической схеме, и найден общий алгоритм преобразования словарного метода в статистический. Поэтому при поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Генерация систем кодов для статистических методов в свою очередь получается либо с использованием префиксного кодирования, либо с использованием арифметического кодирования. Префиксное кодирование является простейшим методом генерации кодов переменной длины. Коды, получаемые с использованием префиксного кодирования, имеют целую длину в единицах представления информации. Преимущество префиксного кодирования состоит в его простоте и высокой производительности, а недостаток в невозможности создавать коды нецелой длины, что, естественно, отрицательно сказывается на эффективности кодирования. В отличие от префиксного кодирования, арифметическое кодирование позволяет генерировать коды как целой, так и нецелой длины. Являясь теоретически оптимальным методом, арифметическое кодирование превосходит в эффективности префиксное кодирование. Оно также опережает префиксное кодирование в скорости построения системы кодов, однако из-за повышенной сложности нередко заметно уступает в скорости самого кодирования (имеется в виду процесс генерации кодовой последовательности). Несмотря на некоторые существенные преимущества арифметического кодирования, данный метод до последнего времени был недостаточно распространен на практике. На сегодняшний день в большинстве коммерческих приложений для построения системы кодов переменной длины используется кодирование Хаффмана, являющееся лучшей с точки зрения эффективности реализацией префиксного кодирования. Арифметическое кодирование применяется лишь в тех случаях, когда требуется добиться максимально возможного качества информационного представления и когда скорость работы не имеет решающего значения. Рассмотрим данный вопрос подробнее. Для этого сравним два наиболее популярных метода статистического кодирования информации алгоритм Хаффмана и Арифметическое кодирование. Вкратце поясним, в чем заключается алгоритм Хаффмана. На начальном этапе работы алгоритма каждому символу информационного алфавита ставится в соответствие вес, равный вероятности появления данного символа в тексте. Символы помещаются в список, который сортируется по убыванию весов. На каждом шаге алгоритма два последних элемента списка объединяются в новый элемент, который затем помещается в список вместо двух объединенных. Новому элементу списка ставится в соответствие вес, равный сумме весов замещаемых элементов. Каждая итерация заканчивается упорядочиванием полученного нового списка, который всегда содержит на один элемент меньше, чем старый список. Параллельно с работой указанной процедуры осуществляется последовательное построение кодового дерева. На каждом шаге алгоритма любому элементу списка соответствует корневой узел бинарного дерева, состоящего из вершин, соответствующих элементам, объединением которых был получен данный элемент. При объединении двух элементов списка происходит объединение соответствующих деревьев в одно новое бинарное дерево, в котором корневой узел соответствует новому элементу, помещаемому в список, а замещаемым элементам списка соответствуют дочерние узлы этого корневого узла. Алгоритм завершает работу, когда в списке остается один элемент, соответствующий корневому узлу построенного бинарного дерева. Это дерево называется деревом 5

6 Хаффмана. Система префиксных кодов может быть получена путем присваивания конкретных двоичных значений ребрам этого дерева. На следующем рисунке приведен пример работы алгоритма Хаффмана для текста abcbb с алфавитом {a, b, c}. Для элементов a, b и c их вероятности появления соответственно равны 0.2, 0.6 и шаг: b 0.6 a 0.2 c 0.2 b a c 2 шаг: b 0.6 ac 0.4 b ac a c 3 шаг: bac 1.0 (построено дерево Хаффмана) 0 bac 1 b ac 0 1 a c Согласно построенному дереву Хаффмана для кодирования исходного сообщения нам потребуется последовательность из 7 битов: (a 10, b 0, c 11). Для сравнения введем следующую величину: будем характеризовать метод кодирования числом ML(S), где S исходное сообщение. ML(S) равняется среднему числу бит, затраченных на кодирование каждого символа сообщения выбранным методом сжатия, т.е. выражается следующей формулой: ML(S) = L(S) / L(S) (2), где L(S) количество бит, требуемое для представления закодированного сообщения; L(S) количество бит, требуемое для представления исходного сообщения. Из теории, основы которой были заложены К. Шенноном, следует, что в системе представления информации с основанием m символу a k, вероятность появления которого равна p(a k), оптимально и, что особенно важно, теоретически допустимо ставить в соответствие код длины: -log m p(a k) (3) Из этого утверждения в частности следует, что символ с высокой вероятностью должен кодироваться несколькими битами, тогда как маловероятный требует многих битов. Также данная формула показывает, почему арифметическое кодирование в общем случае превосходит по эффективности префиксные методы, которые, в отличие от первого, кодируют символы с помощью 6

7 целого количества бит, что снижает степень сжатия и сводит на нет точные предсказания вероятностей. В свою очередь, метод арифметического кодирования обеспечивает теоретически неограниченную точность. Рассмотрим следующий пример. Закодируем слово из алфавита {0, 1} с использованием метода арифметического кодирования, и сравним показатель ML с аналогичным показателем для метода Хаффмана. Пусть дан текст S = Символ Вероятность Интервал 1 3/4 . Первым кодируется символ A. Так как символов 4, и их веса одинаковые, то мы берем четверть от исходного отрезка. Получается интервал . Символ A обработан, увеличиваем его вес на единицу. Общий вес так же увеличился на 1. Следующим кодируется символ B. Разбиваем текущий интервал соответственно отношениям весов символов к весу всех символов. Выбираем интервал, соответствующий символу B - . Увеличиваем вес символа B на единицу, и так далее. Все шаги подробно описаны в таблице 1. Веса символов A B C D Общий вес Кодируемая буква Текущая длина промежутка A 1 B 1/4 B 1/20 A 1/60 Получившийся интервал C 1/210 D 1/1680 Табл /16384 = 1979/2 14, отсюда получаем, что исходное сообщение можно представить двоичным числом є . Таким образом, мы закодировали сообщение с помощью 14 битов. ML = 2.3 бит/сим. Декодирование происходит следующим образом: на каждом шаге определяется интервал, содержащий данный код по этому интервалу однозначно задается исходный символ сообщения. Затем из текущего кода вычитается нижняя граница содержащего интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Получение маркера конца или заданного перед началом работы алгоритма числа символов означает окончание работы. Пример: распакуем код, зная множество символов, из которых состояло исходное сообщение. Итак, = 1979/ Результаты расчетов приведены в таблице 2. Веса символов A B C D Число-код и его интервал Декодированный символ /16384 є A 1/ /4096 є B 1/ /4096 є B 1/ /4096 є A 2/ /8192 є C 1/ /8192 є D 1/9 Табл. 2 Длина интервала Таким образом, из кода мы восстановили исходное сообщение (ABBACD). 8

9 Литература 1. Лидовский В. В. Теория информации: Учебное пособие. М.: Компания Спутник+, Семенюк В. В. Экономное кодирование дискретной информации. СПб.: СПбГИТМО (ТУ), 2001 (доступна на 3. Witten I. H., Neal R. M., Cleary J. G. Arithmetic Coding for Data Compression, CACM, 1987 (доступна на 9

Лекция 5 Арифметическое кодирование Проблема Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации 2 Пример. Пусть в сообщении, состоящем

Дискретная математика Часть 5 В.Е. Алексеев 2014 Глава 9. Кодирование Кодирование преобразование информации, выполняемое с разнообразными целями: экономное представление (сжатие данных), защита от помех

ЗАДАНИЕ 5. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ Кодирование это перевод информации с одного языка на другой. Декодирование обратный переход. Один символ исходного сообщения может заменяться одним или

Кодирование Хаффмана, журнал Монитор, номер 7-8, 1993 год Технологии Программирования Хаффман - 1954 год. Идея алгоритма: зная вероятность вхождения символов в сообщение, можно описать процедуру построения

Статистические методы сжатия информации # 11, ноябрь 2014 Белоус В. В. УДК: 004.627 Россия, МГТУ им. Н.Э. Баумана [email protected] 1. Введение В настоящее время во многих приложениях активно

Государственный комитет информатизации и связи Украины Одесская национальная академия связи им. А. С. Попова Кафедра документальной электросвязи СЖАТИЕ ДАННЫХ БЕЗ ПОТЕРЬ Методическое пособие к практическому

Практическая работа Изучение алгоритма сжатия Хаффмана.. Цель работы Изучить алгоритм оптимального префиксного кодирования Хаффмана и его использование для сжатия сообщений... Теоретические сведения Алгоритм

Динамическое программирование Жадные алгоритмы Код Хаффмана Динамическое программирование (ДП) - способ решения сложных задач путём разбиения их на более простые подзадачи. Подход динамического программирования

Теория информации Лекция 6. Символьные коды (продолжение) Рассмотрим какова цена использования кода с неоптимальной длиной кодового слова. Пусть {p } это вероятности в A x и наш код завершенный с длинами

Http://vmcozet/ Кодирование ВЕ Алексеев Задача оптимального кодирования Побуквенное кодирование Пусть A a a a } и B b b b } два алфавита Побуквенное кодирование состоит в том что в кодируемом тексте слове

5 г. Павлов И.С. Глава V. Теория кодирования. При передаче данных часто возникает необходимость кодирования пересылаемой информации. Процесс пересылки информации происходит по следующей схеме: Возникают

Огомолова О.., Усенков Д.Ю. огомолова Ольга орисовна, Усенков Дмитрий Юрьевич ФНО И ЕГО «КОЛЛЕГИ»: РТИМ ДЕРЕО Задания, в которых нужно кодировать и декодировать сообщения при помощи неравномерного двоичного

Лекция 4 Характеристики дискретного источника и дискретного канала без шумов Энтропия и производительность дискретного источника При построении каналов передачи сообщений основное значение имеет не количество

Оглавление Краткие теоретические сведения... 2 Кодовый алфавит и кодовое слово... 2 Префиксные коды... 3 Равномерные коды... 5 Примеры решения заданий... 5 Пример 1 задания с кратким ответом... 5 Пример

1. СОРТИРОВКА ВЫБОРОМ Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом

УДК 59.7 В.С. Выхованец Верхняя и нижняя оценки Колмогоровской сложности Аннотация. Рассматривается Колмогоровская сложность, определяемая как мера вычислительных ресурсов, необходимых для восстановления

Системы счисления Система счисления способ записи чисел с помощью заданного набора специальных символов (цифр). В вычислительной технике применяются позиционные системы счисления, в которых значение цифры

Лабораторная работа 4 Исследование сверточного кода Цель работы: получение навыков построения сверточного кодера. Содержание: Краткие теоретические сведения... 1 Сверточные кодеры... 1 Основные параметры

Лабораторная работа 1. Цель. Тема: Сжатие информации. Целью лабораторной работы является получение навыков работы с архиваторами RAR, ARJ и ZIP, и ознакомление с основными алгоритмами сжатия информации.

Кодирование без потерь. Займёмся кодированием без потерь. Каждую букву запишем с помощью нулей и единиц. Разные символы могут быть записаны последовательностями разной длины. Хотим, чтобы система кодирования

Кодирование (сжатие) звука Кодек Кодек (англ. codec, от coder/decoder шифратор/дешифратор кодировщик/декодировщик или compressor/decompressor) устройство или программа, способная выполнять преобразование

Раздел Неравномерное кодирование дискретных источников В предыдущем разделе мы убедились в том, что источники информации, вообще говоря, избыточны в том смысле, что, при эффективном кодировании можно уменьшить

КОДИРОВАНИЕ ИНФОРМАЦИИ Информационная безопасность Кодирование vs Шифрование Кодирование и шифрование информации достаточно близкие по смыслу термины. Тем не менее, они имеют существенные отличия. КоДиРоВаНие

Замкнутые маршруты и алгоритмы сегментации изображений А. Малистов, И. Иванов-Погодаев, А. Я. Канель-Белов A. Алгоритмы Пусть у нас в распоряжении имеется книга из n страниц. На каждой странице книги написано

Лекции 3, 4 9 сентября 2016 г. Алфавитный Статистический Опр. 8: Количество информации по Хартли (Хартлиевская мера информации), содержащееся в в последовательности из n символов из алфавита A мощности

4 КОДИРОВАНИЕ И ЗАЩИТА ИНФОРМАЦИИ Горяинов С.И. ПЕРЕСТРОЙКА БИНАРНЫХ ДЕРЕВЬЕВ В АЛГОРИТМЕ ХАФФМАНА Аннотация: Предметом данного исследования является время, затрачиваемое на полную перестройку бинарного

BZIP BZIP2 Burrows-Wheeler transform Move-To-Front Huffman coding Arithmetic coding Федоров Антон [email protected] Часть: блочно-сортирующее сжатие (BWT) Michael Burrows, David Wheeler, 99 Digital

ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2014 Вычислительные методы в дискретной математике 2(24) ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ МАТЕМАТИКЕ УДК 519.7 ОДНОВРЕМЕННЫЙ ПОИСК НЕСКОЛЬКИХ ДВОИЧНЫХ ШАБЛОНОВ В ПОТОКЕ

4. Динамическое программирование 4.1. Наибольшая возрастающая подпоследовательность (Longest increasing subsequence) Вам требуется написать программу, которая по заданной последовательности находит максимальную

Алгоритмы сжатия данных без потерь Антипин Иван 1 Введение Алгоритмы сжатия без потерь Алгоритмы сжатия с потерями Отсеивание информации Сжатие алгоритмом без потерь 2 Алгоритмы сжатия без потерь «Статические»

Лекция 11 3.. Быстрая сортировка В этом разделе рассмотрим алгоритм быстрой сортировки. Хотя время его работы для массива из n чисел в худшем случае составляет (n), на практике данный алгоритм является

КОДИРОВАНИЕ Источник сообщений Код сообщений Канал связи Код сообщения на выходе Сообщение на выходе Источник помех Лекция 0. Кодирование В этой схеме источник сообщений хочет передать по каналу связи

Лекция: Понятие об архитектуре компьютера. Системы счисления. Цель: сформировать первичные представления о читаемой дисциплине, рассмотреть возможности перевода чисел в различные системы счисления и так

Тема 7. Представление информации в ЭВМ.. Единицы информации. Бит - (bit-biry digit - двоичный разряд) наименьшая единица информации - количество её, необходимое для различения двух равновероятных событий.

Лабораторная работа 3 Стандарты сжатия изображений с потерей качества. Стандарт JPEG. Широко используемым на практике подклассом систем сжатия изображений с потерей качества являются системы, основанные

Лабораторная работа 3 Построение кода переменной длины. Цель работы: Изучить метод построения кода переменной длины, оценить эффективность полученного кода и сравнить ее с эффективностью кода постоянной

ЛЕКЦИЯ 3. Алгоритмы обработки одномерных массивов. Цель лекции: Знакомство с понятием массива. Приобретение навыков построения алгоритмов предназначенных для обработки одномерных массивов. 6. Алгоритмы

Теория информации Лекция 5 Символьные коды В данной лекции мы рассмотрим символьные коды переменной длины. Эти коды кодируют за раз один символ, в отличие от блочных кодов рассмотренных до этого, которые

Дискретная математика Домашнее задание 22 (повторение), решения 1 Найдите максимальное количество рёбер в таких ориентированных графах на n вершинах, которые не имеют ориентированных циклов Решение Между

Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем

1 (36) Сколько значащих нулей в двоичной записи шестнадцатеричного числа 125316? 2 (56) Логическая функция F задаётся выражением (a c) (a (b c)). Определите, какому столбцу таблицы истинности функции

Строки Евгений Капун 16 ноября 2012 г. Хеши Хеш строки число, вычисляемое на основе содержимого строки, такое что: Хеши равных строк совпадают. Хеши различных строк с большой вероятностью различаются.

Лабораторная работа 3. Системы счисления Цель: овладеть навыками оперирования числами в различных системах счисления. Задача научиться: ичную; 1) осуществлять перевод из десятичной системы счисления в

АНАЛИЗ РЕЗУЛЬТАТОВ краевой диагностической работы по информатике и ИКТ 11 (12) класс (15 марта 2016) Краевая диагностическая работа по информатике и ИКТ проводилась 15 марта 2016 года и была рассчитана

Лабораторная работа 9 Тема: «Обработка одномерных массивов. Сортировка массивов» 1. Цель работы 1.1 Получение практических навыков в работе с одномерными массивами. 1.2 Знакомство с алгоритмами упорядочения.

Предмет Уровень образования Когда и где утверждена рабочая программа Структура рабочей программы Место предмета в учебном плане Результаты освоения предмета АННОТАЦИЯ к рабочей программе ИНФОРМАТИКА Основное

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

Задания для 11 класса Отборочный этап. Первый тур 1. Кодирование информации. Системы счисления (2 балла) [Перестановки] Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно

Лекция 13 Приемы и методы работы со сжатыми данными Лектор Ст. преподаватель Купо А.Н. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики кафедра ТОРС Задание и методические

УДК 519.6 Особенности кодирования текста с помощью алгоритма Хаффмана Кизянов Антон Олегович Приамурский государственный университет имени Шолом-Алейхема Студент Кузьмина Богдана Сергеевна Приамурский

ЛАБОРАТОРНАЯ РАБОТА Способы задания и основные характеристики сверточных кодов Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными

УДК 004.8 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМ ШКОЛЬНОГО РАСПИСАНИЯ Гущина О. А. Генетический алгоритм (ГА) адаптивный поисковый алгоритм, основанный на эволюционных факторах

Дискретная математика Часть 2 Кочетов Юрий Андреевич http://www.math.nsc.ru/lbrt/k5/dm.html Лекция 1 Алгоритмы, сортировки, AVL деревья 1 Алгоритмы и их сложность Компьютеры выполняют (пока) лишь корректно

При ответе на данный вопрос необходимо объяснить понятие «арифметическое кодирование», сравнить его с другими известными вам способами кодирования и рассказать об алгоритме построения арифметического кода некоторого сообщения.

Арифметическое кодирование - один из алгоритмов энтропийного сжатия. Алгоритм арифметического кодирования обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H - информационная энтропия источника.

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия.

Предполагаемая требуемая последовательность символов , при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала ), а интервал для /-го кодируемого символа потока как ; Ь[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал -(fti-j - li-i); hi = li.! + b ■ {hi.! - li.i); if {{l t <= value) && (value < hi)) break; }; DataFile.WriteSymbol(c^) ;

где value - прочитанное из потока число (дробь), а с - записываемые в вы­ходной поток распаковываемые символы. При использовании алфавита из 256 символов Cj внутренний цикл выполняется достаточно долго, однако его можно ускорить. Заметим, что поскольку Ь[с^ {\=a; II delitel=10

First_qtr - (h 0 +l)/4; // - 16384

Half = First_qtr*2; // - 32768

Third_qtr - First_qtr*3;// = 49152

bits_to_follow =0; // Сколько битов сбрасывать

while (not DataFile.EOFO) {

с = DataFile.ReadSymbol(); // Читаем символ
j = IndexForSymbol(с); i++; // Находим его индекс
li = li.j + b*{h i . 1 - li-x + l)/delitel;
hi = li.! + b ;
First_qtr = (h 0 +l)/4; // = 16384

Half = First_qtr*2; // = 32768

Third_qtr = First_qtr*3; // = 49152

value=CompressedFile.Readl6Bit();

for(i=l; i< CompressedFile.DataLengthO; i++){

freq=((value-2 i . 1 +l)*delitel-l)/(h i . I - 1 ± . х + 1) ;

for(j=l; b<=freq; j++); // Поиск символа

li = 1ы + blj-l]*{bi.! - li- u + l)/delitel;

hi = Im + b*{h i . 1 - li.! + l)/delitel - 1;

for(;;) { // Обрабатываем варианты

if (hi < Half) // переполнения

; // Ничего else ifdi >= Half) {

2i-= Half; hi-= Half; value-= Half; }

else if (di >= First_qtr)&& (hi < Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2 i; hi+= hi+1;

value+=value+CompressedFile.ReadBit(); } DataFile.WriteSymbol(c););

Упражнение. Предложите примеры последовательностей, сжимаемых алго­ритмом с максимальным и минимальным коэффициентом.

Как видно, с неточностями арифметики мы боремся, выполняя отдель­ные операции над /, и А, синхронно в компрессоре и декомпрессоре.

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

Для того чтобы оценить степень сжатия арифметическим алгоритмом конкретной строки, нужно найти минимальное число N, такое, чтобы длина рабочего интервала при сжатии последнего символа цепочки была бы меньше 1/2^.. Этот критерий означает, что внутри нашего интервала заведо­мо найдется хотя бы одно число, в двоичном представлении которого после N-ro знака будут только 0. Длину же интервала, дорчитать просто, поскольку она равна произведению вероятностей всех символов.

Рассмотрим приводившийся ранее пример строки из двух символов л и Ъ с вероятностями 253/256 и 3/256. Длина последнего рабочего интервала для цепочки из 256 символов а и Ь с указанными вероятностями равн. Легко подсчитать, что искомое N=24 (1/2 24 = 5.96-10" 8), поскольку 23 дает слишком большой интервал (в 2 раза шире), а 25 не является минимальным числом, удовлетворяющим критерию. Выше было показано, что алгоритм Хаффмана кодирует данную цепочку в 256 бит. То есть для рассмотренного примера арифметический алгоритм дает десятикратное преимущество, пе­ред алгоритмом Хаффмана и требует менее 0.1 бита на символ.

Упражнение. Подсчитайте оценку степени сжатия для строки "КОВ.КОРОБА".

Следует сказать пару слов об адаптивном алгоритме арифметического сжатия. Его идея заключается в том, чтобы перестраивать таблицу вероят­ностей b[f] по ходу упаковки и распаковки непосредственно при получении очередного символа. Такой алгоритм не требует сохранения значений веро­ятностей символов в выходной файл и, как правило, дает большую степень сжатия. Так, например, файл вида а 1000 £ 1000 с 1000 б/ 1000 (где степень означает число повторов данного символа) адаптивный алгоритм сможет сжать, эф­фективнее, чем потратив 2 бита на символ. Приведенный выше алгоритм достаточно просто превращается в адаптивный. Ранее мы сохраняли табли­цу диапазонов в файл, а теперь мы считаем прямо по ходу работы компрес­сора и декомпрессора, пересчитываем относительные частоты, корректируя в соответствии с ними таблицу диапазонов. Важно, чтобы изменения в таб­лице происходили в компрессоре и декомпрессоре синхронно, т. е., напри­мер, после кодирования цепочки длины 100 таблица диапазонов должна быть точно такой же, как и после декодирования цепочки длины 100. Это условие легко выполнить, если изменять таблицу после кодирования и де­кодирования очередного символа. Подробнее об адаптивных алгоритмах смотрите в гл. 4.

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

Лучшая и худшая степень сжатия: лучшая > 8 (возможно кодирование менее бита на символ), худшая - 1.

Плюсы алгоритма: обеспечивает лучшую степень сжатия, чем алго-I ритм Хаффмана (на типичных данных на 1-10%).

Характерные особенности: так же как кодирование по Хаффману, не увеличивает размера исходных данных в худшем случае.

Интервальное кодирование

В отличие от классического алгоритма, интервальное кодирование пред­полагает, что мы имеем дело с целыми дискретными величинами, которые могут принимать ограниченное число значений. Как уже было отмечено, начальный интервал в целочисленной арифметике записывается в виде [ОД) или , где N- число возможных значений переменной, используемой для хранения границ интервала.

Чтобы наиболее эффективно сжать данные, мы должны закодировать каждый символ s посредством -log 2 (Ј) бит, где f, - частота символа s. Ко­нечно, на практике такая точность недостижима, но мы можем для каждого символа s отвести в интервале диапазон значений , Prev_freq[c], 10) ;