Список разделов: Статьи по дате:
27.03.2005 | Главная > Алгоритмы > Кодирование информации, применяемое при сжатии данных

Комментариев к статье: 27 шт.

Кодирование информации, применяемое при сжатии данных

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

Кодировщик переделывает символ на входе в код на выходе, используя вероятности символов, которые поставляет ему моделировщик. В данной статье речь пойдет о двух самых распространенных и известных методах кодирования информации во время сжатия: кодирование Хаффмана (Huffman) и арифметическое кодирование и его разновидности.

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

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

Для работы алгоритма необходимо иметь таблицу значений вероятностей различных символов, которые могут встретиться в данный момент кодирования (в данном месте обрабатываемого текста, где кодер в данный момент будет кодировать очередной символ).

На основе этой таблицы строится бинарное дерево Хаффмана следующим образом:

  1. Отсортировать символы по возрастанию вероятности их появления
  2. Первые два символа в получившемся ряде объединить в один, сопоставив первому символу ноль, второму символу - единицу. Вероятности этих двух символов сложить.
  3. Если в ряде остался один символ, то закончить, иначе перейти к пункту 1

Пример построения дерева

Предположим, что мы имеем алфавит из 8 символов. Подпрограмма, осуществляющая моделирование задает нам следующие возможные вероятности этих символов:
A - 7%, B - 13%, C - 2%, D - 28%, E - 14%, F - 22%, G - 10%, H - 4%.

Сортируем символы по возрастанию вероятности:
C - 2%, H - 4%, A - 7%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

Левые два объединяем в один:
CH - 6%, A - 7%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

В данном случае сортировка не требуется. Заметим также, что для символа C теперь появился код 0, для H - 1. Эти символы находятся в самом низу кроны дерева Хаффмана (дерево растет вниз, т.е. крона его внизу), и к ним впоследствии будут добавлены новые узлы дерева, которые будут стоять выше. Пока же дерево выглядит следующим образом:

Снова объединяем два левых символа в один:
CHA - 13%, G - 10%, B - 13%, E - 14%, F - 22%, D - 28%.

После сортировки получим:
G - 10%, CHA - 13%, B - 13%, E - 14%, F - 22%, D - 28%.

Дерево выглядит следующим образом:

Когда мы обработаем все символы дерево примет вид:

Теперь, чтобы закодировать любой символ нужно пройти от корня дерева до символа запоминая биты, определяющие направление движения. Коды символов получились следующие:
A - 1111, B - 000, C - 11100, D - 01, E - 001, F - 10, G - 110, H - 11101.

Таким образом, самые вероятные символы: D и F имеют наименьшую длину кода: 2 бита, а менее вероятные символы имеют коды большей длины. Все коды уникально идентифицируют символ, т.е. из кода можно получить исходный текст в полном объеме.

Недостаток метода Хаффмана

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

Представим себе, что символ встречается в тексте с 99% вероятностью. Метод Хаффмана присвоит этому символу код 1, длиной в 1 бит. Имея файл размером 1 Мбайт, сжат он будет до 1 бит/байт, т.е. до 128 Кбайт, хотя сжать его можно гораздо эффективней: буквально до нескольких сот байт! Арифметическое кодирование лишено этого недостатка.

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

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

Таблица накопительных счетчиков устроена так, что частота появления N + 1 - го символа алфавита равна разности его счетчика и счетчика N - го символа. Другими словами, если мы имеем алфавит из 8 символов с частотами 7, 9, 2, 16, 22, 14, 11 и 55 соответственно, то таблица накопительных счетчиков будет следующей: 7, 16, 18, 34, 56, 70, 81, 136.

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

Принцип кодирования

Для кодирования символов необходимо разбить полуинтервал [0; 1) на части. Каждая часть символизирует частоту повторения символа таким образом, что отношение длины интервала символа к длине всего интервала численно равно величине вероятности. Для примера возьмем алфавит из четырех символов с частотами: 23, 16, 82 и 5. Разделим интервал в соответствии с вероятностями этих символов на четыре подинтервала: [0, 0.1825), [0.1825, 0.3095), [0.3095, 0.9604) и [0.9604, 1). Ширина третьего интервала самая большая т.к. третий символ наиболее вероятен.

Для кодирования задаются два числа - левый и правый края текущей области в интервале, которые сначала имеют значения 0 и 1 соответственно. При кодировании текущая область интервала сужается с каждым новым закодированным символом следующим образом:
Li = Li - 1 + Rng i - 1 * li
Hi = Hi - 1 - Rngi - 1 * (1 - hi)

Здесь L и H - границы текущей области интервала на соответствующем шаге, Rng - ширина текущей области на том же шаге, l и h - соответственно нижняя и верхняя границы интервала кодируемого символа.

Когда кодирование всех символов сообщения будет закончено числа L и H нужно записать в выходной поток, они и будут закодированным сообщением. Замечу, что оба числа записывать необязательно: для декодирования достаточно записать число, принадлежащее этому интервалу. Запись сообщения производится тем количеством бит, которое необходимо для представления числа с получившейся точностью, т.о. чем больше сообщение, тем с большей точностью необходимо записывать эти числа, увеличивая длину выходного сообщения.

Реализация кодирования

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

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

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

Range - кодирование

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

Быстрое кодирование

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

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

Заключение

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

Комментариев к статье: 27 шт.


(С) Copyright 2005-2016. На данном сайте содержится авторский материал, принадлежащий Двуреченскому Павлу. Перепечатка данного материала возможна только со ссылкой на www.paveldvlip.ru и указанием имени автора.