Арифметическое кодирование информации. Теория информации. Кодирование методом Хаффмана

Схема сжатия LZW

Кодирование методом Хаффмана

Групповое кодирование

Сжатие изображений

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

Один из самых простых методов сжатия - групповое кодирование или групповое сжатие. Другое название - "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может - наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. количество повторяющихся пикселов мало. Возникает даже лишняя трата ресурсов.

Кодирование методом Хаффмана (Huffman) - общая схема сжатия. Подход создан в 1952 г. для текстовых файлов. Имеется множество вариантов. Основная идея - присвоение двоичного кода каждому уникальному элементу, причем длина этих кодов различна. Для наиболее часто повторяющихся элементов используются более короткие коды. Присвоения хранятся в таблице перекодировки, которая загружается в декодирующую программу перед самими кодами. Существуют различные алгоритмы построения кодов. Степень сжатия оценивается как 8: 1 . Для файлов с длинными последовательностями схема Хаффмана работает не очень хорошо. Здесь лучше групповое сжатие. Т.к. для построения кодов нужна статистика, обычно используют 2 прохода. Сначала создается статистическая модель, затем выполняется собственно сжатие (кодирование). Т.к. работа с кодами переменной длины требует много времени, кодирование и декодирование длительны.

Метод назван по первым буквам фамилий разработчиков: Lempel, Ziv, Welch. Разработка 1984 г. Сначала метод предназначался для аппаратной реализации. Как и алгоритм Хаффмана, алгоритм LZW имеет несколько вариантов. Идея - поиск повторяющихся пиксельных узоров и их кодирование. Кодовая таблица создается не перед кодированием, а в процессе кодирования, что делает алгоритм адаптивным. Рассмотрим последовательность "ababaaacaaaad". Пусть каждая буква кодируется в изображении 2-битной величиной. Начальная кодовая таблица кодирует каждый атомарный объект: a - 00, b - 01, c - 10, d - 11 . Затем алгоритм переходит к поиску последовательностей. Он может распознать только 1-буквенные последовательности. Первая 2-буквенной последовательности не распознается и подлежит кодированию. Т.к. длина кода исчерпана, ее увеличивают на 1: a - 000, b - 001, c - 010, d - 011, ab - 100 . Следующее 2-буквенное сочетание распознается. Для каждой буквы было 2-битное описание. На последовательность требуется 2 * 2 = 4 бита. При замене последовательности 3-битным кодом экономим 1 бит на каждом появлении последовательности. Типичный коэффициент сжатия для метода 3: 1 . Изображения с повторяющимися цветными узорами сжимаются до 10: 1 . Отсканированные фотографии и изображения, не содержащие узоров, сжимаются плохо.

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

Алгоритмы Шеннона-Фено и Хаффмена в лучшем случае не могут кодировать каждый символ сообщения менее чем 1 битом информации. Предположим, в сообщении, состоящем из 0 и 1, единицы встречаются 10 раз чаще. Энтропия такого сообщения HX ≈0,469 (бит /сим ). В таком случае желательно иметь схему кодирования, позволяющую кодировать символы сообщения менее чем 1 битом информации. Одним из лучших алгоритмов такого кодирования информации является арифметическое кодирование.

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

Алгоритм кодирования заключается в построении отрезка, однозначно определяющего конкретную последовательность символов сообщения. По мере поступления входных символов отрезок сообщения сужается. Отрезки строятся следующим образом. Если имеется отрезок сообщения длиной n -1 , то для построения отрезка сообщения длиной n символов, предыдущий интервал разбивается на столько частей, сколько значений включает алфавит источника. Начало и конец каждого нового интервала сообщения определяется путем прибавления к началу предыдущего интервала произведения его ширины на значения границ отрезка, соответствующего текущему новому символу (по исходной таблице вероятностей символов и назначенных им интервалов) . Затем из полученных отрезков выбирается тот, который соответствует конкретной последовательности символов сообщения длиной n .

Для построенного отрезка сообщения находится число, принадлежащее этому отрезку, обычно, это целое число, делённому на минимально возможную степень 2. Это вещественное число и будет кодом для рассматриваемой последовательности . Все возможные коды – числа строго больше 0 и меньше 1, поэтому лидирующий 0 и десятичная точка не учитываются.

По мере кодирования исходного текста его интервал сужается, соответственно количество разрядов, служащих для его представления, возрастает. Очередные символы входного текста сокращают ширину отрезка в зависимости от их вероятностей. Более вероятные символы сужают интервал в меньшей степени, чем менее вероятные, и, следовательно, добавляют меньшее количество разрядов к результату.

Принципиальное отличие арифметического кодирования от методов сжатия Шеннона-Фено и Хаффмена в его непрерывности, т.е. в отсутствии необходимости блокирования сообщения. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения, однако требует больших вычислительных ресурсов.

Поясним идею арифметического кодирования на конкретных примерах.

Пример 1 Закодируем текстовую строку « МАТЕМАТИКА » по алгоритму арифметического кодирования.

Алфавит кодируемого сообщения содержит следующие символы: {М , А , Т , Е , И , К }.

Определим частоту каждого из символов в сообщении и назначим каждому из них отрезок, длина которого пропорциональна вероятности соответствующего символа (табл. 2.7 ).

Символы в таблице символов и интервалов можно располагать в любом порядке: по мере их появления в тексте, в алфавитном или по возрастанию вероятностей – это не принципиально. Результат кодирования может быть разным, но эффект будет одинаковым.

Таблица 2.7

Средняя длина кода на единицу сообщения

Приведем процедуру арифметического кодирования для последовательности произвольной длины:

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 ) определяется отрезок, которому принадлежит это число, - }