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

  Следуя  этим рекомендациям, кодировщик гарантирует, что после операций сдвига будет или

  low < first_qtr < half ≤ high (1a)

  или

  low < half < third_qtr <= high (1b).

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

  max_frequency≤(top_value + 1)/4 + 1,

  которое удовлетворяет программе, т.к. max_frequency = 214 - 1 и top_value = 216 - 1.

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

  Переполнение  и завершение 

  Теперь  рассмотрим возможность переполнения при целочисленном умножении. Переполнения не произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать max_frequency. range имеет наибольшее значение в top_value + 1, поэтому максимально возможное произведение в программе есть 216*(214 - 1), которое меньше 230.

  При завершении процесса кодирования необходимо послать  уникальный завершающий символ (EOF-символ), а затем послать вслед достаточное  количество битов для гарантии того, что закодированная строка попадет  в итоговый рабочий интервал. Т.к. процедура done_encoding() может быть уверена, что low и high ограничены либо выражением (1a), либо (1b), ему нужно только передать 01 или 10 соответственно, для удаления оставшейся неопределённости. Удобно это делать с помощью процедуры bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохранять заполнение нижнего конца буфера. Неважно, какое значение имеют эти биты, поскольку EOF уникально определяется последними переданными битами. 

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

  Программа должна работать с моделью, которая  предоставляет пару перекодировочных таблиц index_to_char[] и char_to_index[], и массив накопленных частот cum_freq[]. Причем к последнему предъявляются следующие требования:

  cum_freq[i-1] >= cum_freq[i];

  никогда не делается попытка кодировать символ i, для которого

  cum_freq[i-1] = cum_freq[i];

  cum_freq[0] <= Max_frequency.

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

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

  При инициализации  все частоты устанавливаются  в 0. Процедура update_model(symbol), вызывается из encode_symbol() и decode_symbol() после обработки каждого символа.

  Обновление  модели довольно дорого по причине необходимости поддержания накопленных сумм. В программе используемые счетчики частот оптимально размещены в массиве в порядке убывания своих значений, что является эффективным видом самооpганизуемого линейного поиска. Процедура update_model() сначала проверяет новую модель на предмет превышения ею ограничений по величине накопленной частоты, и если оно имеет место, то уменьшает все частоты делением на 2, заботясь при этом, чтобы счетчики не превратились в 0, и перевычисляет накопленные значения. Затем, если необходимо, update_model() переупорядочивает символы для того, чтобы разместить текущий в его правильной категории относительно частотного порядка, чередуя для отражения изменений перекодированные таблицы. В итоге процедура увеличивает значение соответствующего счетчика частоты и приводит в порядок соответствующие накопленные частоты.

 

  Эффективность сжатия 

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

  1.         расходы на завершение текста;

  2.         использование арифметики не бесконечной точности;

  3.         такое масштабирование счетчиков, что их сумма не превышает max_frequency.

  Арифметическое кодирование должно досылать дополнительные биты в конец каждого текста, совершая т.о. дополнительные усилия на завершение текста. Для ликвидации неясности с последним символом процедура done_encoding() посылает два бита. В случае, когда перед кодированием поток битов должен блокироваться в 8-битовые символы, будет необходимо закругляться к концу блока. Такое комбинирование может дополнительно потребовать 9 битов.

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

  Дополнительные  затраты на масштабирование счетчиков отчасти больше, но все равно очень малы. Для коротких текстов (меньших 214 байт) их нет. Но даже с текстами в 105 - 106 байтов накладные расходы, подсчитанные экспериментально, составляют менее 0.25% от кодируемой строки.

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

 

  Заключение 

  В данной курсовой работе были рассмотрены вопросы  архивации данных различными методами. Подробно описаны алгоритмы сжатия данных по мере появления и развития.

  В курсовой работе был реализован алгоритм арифметического  кодирования и создана программа  «Архиватор» со всеми необходимыми функциями.

  Для реализации использовался язык C# и визуальная среда программирования Microsoft Visual Studio. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.

 

  Список  литературы

  1.  

    2.    

   3.      

  4

 

Приложение 1. Программный  код

  // Количество  бит для кода

  const int bits_in_register = 16;

  // Максимально возможное значение кода

  const int top_value = (int)(((long)1 << bits_in_register) - 1);

  // Диапазоны

  const int first_qtr = (top_value / 4 + 1);

  const int half = (2 * first_qtr);

  const int third_qtr = (3 * first_qtr);

  // Количество  символов алфавита

  const int no_of_chars = 256;

  // Специальный символ Конец файла

  const int eof_symbol = (no_of_chars + 1);

  // Всего символов в модели

  const int no_of_symbols = (no_of_chars + 1);

  // Порог частоты для масштабирования

  const int max_frequency = 16383;

  // Таблицы перекодировки

  public int[] index_to_char = new int[no_of_symbols];

  public int[] char_to_index = new int[no_of_chars];

  // Таблицы частот

  public int[] cum_freq = new int[no_of_symbols + 1];

  public int[] freq = new int[no_of_symbols + 1];

  // Регистры границ и кода

  public static long low, high;

  public static long value;

  // Поддержка побитовых операций с файлами

  public static long bits_to_follow;

  // Буфер

  public static int buffer;

  // Количество бит в буфере

  public static int bits_to_go;

  // Количество бит после конца файла

  public static int garbage_bits;

  // Указатель  на входной файл

  FileStream datain;

  // Указатель  на выходной файл

  FileStream dataout;

  //--------------------------------------------------------------

  // Инициализация адаптивной модели

  public void start_model ()

  {

  int i;

  // Установки таблиц перекодировки

  for ( i = 0; i < no_of_chars; i++)

  {

  char_to_index [i] = i + 1;

  index_to_char [i + 1] = i;

  }

  // Установка счетчиков накопленных частот

  for ( i = 0; i <= no_of_symbols; i++)

  {

  freq [i] = 1;

  cum_freq[i] = no_of_symbols - i;

  }

  freq [0] = 0;

  }

  //------------------------------------------------------------

  // Обновление модели очередным символом

  void update_model(int symbol)

  {

  // Новый индекс

  int i;

  int ch_i, ch_symbol;

  int cum;

  // Проверка  на переполнение счетчика частоты

  if (cum_freq[0] == max_frequency)

  {

  cum = 0;

  /* Масштабирование  частот при переполнении (если  счетчики частот достигли своего  максимума, то делим на пополам) */

  for (i = no_of_symbols; i >= 0; i--)

  {

  freq[i] = (freq[i] + 1) / 2;

  cum_freq[i] = cum;

  cum += freq[i];

  }

  }

  /* Обновление  перекодировочных таблиц в случае перемещения символа */

  for (i = symbol; freq[i] == freq[i - 1]; i--) ;

  if (i < symbol)

  {

  ch_i = index_to_char[i];

  ch_symbol = index_to_char[symbol];

  index_to_char[i] = ch_symbol;

  index_to_char[symbol] = ch_i;

  char_to_index[ch_i] = symbol;

  char_to_index[ch_symbol] = i;

  }

  // Увеличить  значение счетчика частоты для символа

  freq[i] += 1;

  // Обновление значений в таблицах частот

  while (i > 0)

  {

  i -= 1;

  cum_freq[i] += 1;

  }

  }

  //------------------------------------------------------------

  // Инициализация побитового ввода

  void start_inputing_bits ()

  {

  bits_to_go = 0;

  garbage_bits = 0;

  }

  //------------------------------------------------------------

  // Ввод  очередного бита сжатой информации

  int input_bit ()

  {

  int t;

  // Чтение  байта если буфер пуст