Алгоритмы сжатия данных

 

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

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

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

  Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:                                     Символ Частота Вероятность Диапазон

  О                 3                   0.3            [0.0; 0.3)

  К                 2                   0.2            [0.3; 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).

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

  Рис. 4. Графический процесс кодирования  первых трех символов

  Таким образом, окончательная длина интервала  равна произведению вероятностей всех встретившихся символов, а его  начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [li, hi).

  Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее  в полученном при работе интервале [/i, hi). Для последовательности "КОВ.", состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

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

  Реализация  алгоритма арифметического кодирования 

  Ниже показан  фрагмент псевдокода процедур кодирования  и декодирования. Символы в нем  нумеруются как 1,2,3... Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. При убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого "обратного" соглашения состоит в том, что cum_freq[0] будет потом содержать нормализующий множитель, который удобно хранить в начале массива). Текущий рабочий интервал задается в [low; high] и будет в самом начале равен [0; 1) и для кодировщика, и для pаскодиpовщика. 

  Алгоритм  кодирования: 

  С каждым символом текста обращаться к процедуре encode_symbol(). Проверить, что "завершающий" символ закодирован последним. Вывести полученное значение интервала [low; high).

  encode_symbol(symbol, cum_freq)

  {…

  range = high - low

  high = low + range*cum_freq[symbol-1]

  low = low + range*cum_freq[symbol]

  …

  }

  Алгоритм  декодирования: 

  Value - это поступившее на вход число. Обращение к процедуре decode_symbol() пока она не возвратит "завершающий" символ.

  decode_symbol(cum_freq)

  //поиск  такого символа, что

  cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1]

  Это обеспечивает размещение value внутpи нового интервала [low;high), что отражено в оставшейся части программы:

  range = high - low

  high = low + range*cum_freq[symbol-1]

  low = low + range*cum_freq[symbol]

  return symbol

  Реализация  алгоритма на C# приведена в Приложении. 

  Реализация  модели 

  В языке  Си байт представляет собой целое  число от 0 до 255 (тип char). Здесь же мы представляем байт как целое число от 1 до 257 включительно (тип index), где EOF трактуется как 257-ой символ. Перевод из типа char в index, и наоборот, реализуется с помощью двух таблиц - index_to_char[] и char_to_index[].

  Вероятности представляются в модели как целочисленные счетчики частот, а накапливаемые частоты хранятся в массиве cum_freq[]. Этот массив - "обратный", и счетчик общей частоты, применяемый для нормализации всех частот, размещается в cum_freq[0]. Накапливаемые частоты не должны превышать установленный в max_frequency максимум, а реализация модели должна предотвращать переполнение соответствующим масштабированием. Необходимо также хотя бы на 1 обеспечить различие между двумя соседними значениями cum_freq[], иначе рассматриваемый символ не сможет быть передан.  

  Доказательство правильности декодирования 

  Проверим верность определения процедурой decode_symbol() следующего символа. Из псевдокода видно, что decode_symbol() должна использовать value для поиска символа, сократившего при кодировании рабочий интервал так, что он продолжает включать в себя value. Стpоки range = (long) (high - low) + 1; и cum=(int)((((long)(value-low)+1)*cum_freq[0]-1)/ range); в decode_symbol() определяют такой символ, для котоpого

    

  где "| |" обозначает операцию взятия целой части - деление с отбрасыванием дробной части.

  Другими словами:

   (1) 

  где range = high - low + 1, .

  Последнее неравенство выражения (1) происходит из факта, что cum_freq[symbol-1] должно быть целым. Затем мы хотим показать, что low'≤value≤high', где low' и high' есть обновленные значения для low и high как определено ниже.

  

  Из выружения (1) имеем: ≤value + 1 – 1/cum_freq[0], поэтому low'≤value, т.к. и value, и low', и cum_freq[0] > 0.

  

  Из выражения (1) имеем:

    

  Приращаемая передача и получение 

  В отличие  от псевдокода, программа представляет low и high целыми числами. В псевдокоде текущий интервал представлен через [low; high), а в программе это [low; high] - интервал, включающий в себя значение high. Hа самом деле более правильно, хотя и более непонятно, утверждать, что в программе представляемый интервал есть [low; high + 0.1111...) по той причине, что при масштабировании границ для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high.

  По мере сужения кодового интервала, старшие биты low и high становятся одинаковыми, и поэтому могут быть переданы немедленно, т.к. на них будущие сужения интервала все равно уже не будут влиять. Поскольку мы знаем, что low≤high, это воплотится в следующую программу:

  for (;;)

  {

  if (high < Half)

  {

  output_bit(0);

  low = 2 * low;

  high = 2 * high + 1;

  }

  else if (low >= Half)

  {

  output_bit(1);

  low = 2 * (low - Half);

  high = 2 * (high - Half) + 1;

  }

  else break;

  }

  гарантирующую, что после ее завершения будет справедливо неравенство: low<Half≤high. Это можно найти в процедуре encode_symbol().

  Причащаемый ввод исходных данных выполняется с помощью числа, названного value. В программе, обработанные биты перемещаются в верхнюю часть, а заново получаемые поступают в нижнюю. Вначале, start_decoding() заполняет value полученными битами. После определения следующего входного символа процедурой decode_symbol(), происходит вынос ненужных, одинаковых в low и в high, битов старшего порядка сдвигом value на это количество разрядов (выведенные биты восполняются введением новых с нижнего конца).

  for (;;)

  {

  if (high < Half)

  {

  value = 2 * value + input_bit();

  low = 2 * low;

  high = 2 * high + 1;

  }

  else if (low > Half)

  {

  value = 2 * (value - Half) + input_bit();

  low = 2 * (low - Half);

  high = 2 * (high - Half) + 1;

  }

  else break;

  } 

  Отрицательное переполнение 

  Как показано в псевдокоде, арифметическое кодирование  работает при помощи масштабирования  накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Предположим, что low и high настолько близки друг к другу, что операция масштабирования приводит полученные от модели разные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодирование продолжать невозможно. Следовательно, кодировщик должен следить за тем, чтобы интервал [low; high] всегда был достаточно широк. Простейшим способом для этого является обеспечение ширины интервала не меньшей max_frequency - максимального значения суммы всех накапливаемых частот.

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

  first_qtr ≤low<half≤high<third_qtr. (*)

  Тогда следующие  два бита вывода будут иметь взаимообратные значения: 01 или 10. Например, если следующий бит будет нулем (т.е. high опускается ниже half и [0; half] становится рабочим интервалом), а следующий за ним - единицей, т.к. интервал должен располагаться выше средней точки рабочего интервала. Наоборот, если следующий бит оказался 1, то за ним будет следовать 0. Поэтому теперь интервал можно безопасно расширить вправо, если только мы запомним, что какой бы бит не был следующим, вслед за ним необходимо также передать в выходной поток его обратное значение. Т.о. происходит преобразование [first_qtr; third_qtr] в целый интервал, запоминая в bits_to_follow значение бита, за которым надо посылать обратный ему. Это объясняет, почему весь вывод совершается через процедуру bit_plus_follow(), а не непосредственно через output_bit().

  Но что делать, если после этой операции соотношение (*) остается справедливым? Представим такой случай, когда рабочий интервал [low; high] расширяется 3 раза подряд. Пусть очередной бит ниже средней точки первоначального интервала, оказался нулем. Тогда следующие 3 бита будут единицами, поскольку мы находима не просто во второй его четверти, а в верхней четверти, даже в верхней восьмой части нижней половины первоначального интервала - вот почему расширение можно произвести 3 раза. Тоже самое для случая, когда очередной бит оказался единицей, и за ним будут следовать нули. Значит в общем случае необходимо сначала сосчитать количество расширений, а затем вслед за очередным битом послать в выходной поток найденное количество обратных ему битов.