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

Цель лекции: изучить основные виды и алгоритмы сжатия данных и научиться решать задачи сжатия данных по методу Хаффмана и с помощью кодовых деревьев.

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение.

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

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

Введем ряд определений, которые будут использоваться далее в изложении материала.

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт, но он может быть битом, тритом {0,1,2}, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины), а если же допускаются слова разной длины, то – неравномерным (переменной длины).

Код – полное множество слов.

Токен – единица данных, записываемая в сжатый поток некоторым алгоритмом сжатия. Токен состоит из нескольких полей фиксированной или переменной длины.

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

Декодирование – обратный кодированию процесс, при котором осуществляется восстановление данных.

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.$$\textit{Отношение сжатия} = \frac{\textit{размер выходного потока}}{\textit{размер входного потока}}$$ Значение 0,6 означает, что данные занимают 60% от первоначального объема. Значения больше 1 означают, что выходной поток больше входного (отрицательное сжатие, или расширение).

Коэффициент сжатия – величина, обратная отношению сжатия.$$\textit{Коэффициент сжатия} = \frac{\textit{размер входного потока}}{\textit{размер выходного потока}}$$ Значения больше 1 обозначают сжатие, а значения меньше 1 – расширение.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

Lcp=p1L1+p2L2+...+pnLn,

где – вероятности кодовых слов;

L1,L2,...,Ln – длины кодовых слов.

Существуют два основных способа проведения сжатия.

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в "словаре" (некоторая структура данных). Если строка новых данных, поступающих на вход, идентична какому-либо фрагменту, уже находящемуся в словаре, в выходной поток помещается указатель на этот фрагмент. Лучшие словарные методы применяют метод Зива-Лемпела.

Рассмотрим несколько известных алгоритмов сжатия данных более подробно.

Метод Хаффмана

Этот алгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Хаффмановское кодирование (сжатие) – это широко используемый метод сжатия, присваивающий символам алфавита коды переменной длины, основываясь на вероятностях появления этих символов.

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1. Программная реализация метода Хаффмана.

#include "stdafx.h"
#include <iostream>
using namespace std;

void Expectancy();
long MinK();
void SumUp();
void BuildBits();
void OutputResult(char **Result);
void Clear();

const int MaxK = 1000;
long k[MaxK + 1], a[MaxK + 1], b[MaxK + 1];
char bits[MaxK + 1][40];
char sk[MaxK + 1];
bool Free[MaxK + 1];
char *res[256];
long i, j, n, m, kj, kk1, kk2;
char str[256];

int _tmain(int argc, _TCHAR* argv[]){
  char *BinaryCode;
  Clear();
  cout << "Введите строку для кодирования : ";
  cin >> str;
  Expectancy();
  SumUp();
  BuildBits();
  OutputResult(BinaryCode);
  cout << "Закодированная строка : " << endl;
  cout << BinaryCode << endl;
  system("pause");
  return 0;
}
//описание функции обнуления данных в массивах
void Clear(){
  for (i = 0; i < MaxK + 1; i++){
    k[i] = a[i] = b[i] = 0;
    sk[i] = 0;
    Free[i] = true;
    for (j = 0; j < 40; j++)
      bits[i][j] = 0;
  }
}
/*описание функции вычисления вероятности вхождения каждого символа в тексте*/
void Expectancy(){
  long *s = new long[256];
  for ( i = 0; i < 256; i++)
    s[i] = 0;
  for ( n = 0; n < strlen(str); n++ )
    s[str[n]]++;
  j = 0;
  for ( i = 0; i < 256; i++)
    if ( s[i] != 0 ){
      j++;
      k[j] = s[i];
      sk[j] = i;
    }
  kj = j;
}
/*описание функции нахождения минимальной частоты символа в исходном тексте*/
long MinK(){
  long min;
  i = 1;
  while ( !Free[i]  i < MaxK) i++;
  min = k[i];
  m = i;
  for ( i = m + 1; i <= kk2; i++ )
    if ( Free[i]  k[i] < min ){
      min = k[i];
      m = i;
    }
  Free[m] = false;
  return min;
}
//описание функции подсчета суммарной частоты символов
void SumUp(){
  long s1, s2, m1, m2;
  for ( i = 1; i <= kj; i++ ){
    Free[i] = true;
    a[i] = 0;
    b[i] = 0;
  }
  kk1 = kk2 = kj;
  while (kk1 > 2){
    s1 = MinK();
    m1 = m;
    s2 = MinK();
    m2 = m;
    kk2++;
    k[kk2] = s1 + s2;
    a[kk2] = m1;
    b[kk2] = m2;
    Free[kk2] = true;
    kk1--;
  }
}
//описание функции формирования префиксных кодов
void BuildBits(){
  strcpy(bits[kk2],"1");
  Free[kk2] = false;
  strcpy(bits[a[kk2]],bits[kk2]);
  strcat( bits[a[kk2]] , "0");
  strcpy(bits[b[kk2]],bits[kk2]);
  strcat( bits[b[kk2]] , "1");
  i = MinK();
  strcpy(bits[m],"0");
  Free[m] = true;
  strcpy(bits[a[m]],bits[m]);
  strcat( bits[a[m]] , "0");
  strcpy(bits[b[m]],bits[m]);
  strcat( bits[b[m]] , "1");
  for ( i = kk2 - 1; i > 0; i-- )
    if ( !Free[i] ) {
      strcpy(bits[a[i]],bits[i]);
      strcat( bits[a[i]] , "0");
      strcpy(bits[b[i]],bits[i]);
      strcat( bits[b[i]] , "1");
    }
}
//описание функции вывода данных 
void OutputResult(char **Result){
  (*Result) = new char[1000];
  for (int t = 0; i < 1000 ;i++)
    (*Result)[t] = 0;
  for ( i = 1; i <= kj; i++ )
    res[sk[i]] = bits[i];
  for (i = 0; i < strlen(str); i++)
    strcat( (*Result) , res[str[i]]);
}

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

Кодовые деревья

Рассмотрим реализацию алгоритма Хаффмана с использованием кодовых деревьев.

Кодовое дерево (дерево кодирования Хаффмана, Н-дерево) – это бинарное дерево, у которого:

Метод Хаффмана на входе получает таблицу частот встречаемости символов в исходном тексте. Далее на основании этой таблицы строится дерево кодирования Хаффмана.

Алгоритм построения дерева Хаффмана.

Шаг 1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемый текст.

Шаг 2. Выбираются два свободных узла дерева с наименьшими весами.

Шаг 3. Создается их родитель с весом, равным их суммарному весу.

Шаг 4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

Шаг 5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой – бит 0.

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

Существует два подхода к построению кодового дерева: от корня к листьям и от листьев к корню.

Пример построения кодового дерева. Пусть задана исходная последовательность символов:

aabbbbbbbbccсcdeeeee.

Ее исходный объем равен 20 байт (160 бит). В соответствии с приведенными на рис 41.1 данными (таблица вероятности появления символов, кодовое дерево и таблица оптимальных префиксных кодов) закодированная исходная последовательность символов будет выглядеть следующим образом:

110111010000000011111111111111001010101010.

Следовательно, ее объем будет равен 42 бита. Коэффициент сжатия приближенно равен 3,8.

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

Пример 2. Программная реализация алгоритма Хаффмана с помощью кодового дерева.

#include "stdafx.h"
#include <iostream>
using namespace std;
struct sym { 
      unsigned char ch;
      float freq;     
      char code[255];
      sym *left;
      sym *right;
};
void Statistics(char *String);
sym *makeTree(sym *psym[],int k);
void makeCodes(sym *root);
void CodeHuffman(char *String,char *BinaryCode, sym *root);
void DecodeHuffman(char *BinaryCode,char *ReducedString, 
                   sym *root);
int chh;//переменная для подсчета информация из строки
int k=0;
//счётчик количества различных букв, уникальных символов
int kk=0;//счетчик количества всех знаков в файле
int kolvo[256]={0};
//инициализируем массив количества уникальных символов
sym simbols[256]={0};//инициализируем массив записей 
sym *psym[256];//инициализируем массив указателей на записи
float summir=0;//сумма частот встречаемости

int _tmain(int argc, _TCHAR* argv[]){
  char *String = new char[1000];
  char *BinaryCode = new char[1000];
  char *ReducedString = new char[1000];
  String[0] = BinaryCode[0] = ReducedString[0] = 0;
  cout << "Введите строку для кодирования : ";
  cin >> String;
  sym *symbols = new sym[k];
  //создание динамического массива структур simbols
  sym **psum = new sym*[k];
  //создание динамического массива указателей на simbols
  Statistics(String);
  sym *root = makeTree(psym,k);
  //вызов функции создания дерева Хаффмана    
  makeCodes(root);//вызов функции получения кода
  CodeHuffman(String,BinaryCode,root);
  cout << "Закодированная строка : " << endl;
  cout << BinaryCode << endl;
  DecodeHuffman(BinaryCode,ReducedString, root);
  cout << "Раскодированная строка : " << endl;
  cout << ReducedString << endl;
  delete psum;
  delete String;
  delete BinaryCode;
  delete ReducedString;
  system("pause");
  return 0;
}
//рeкурсивная функция создания дерева Хаффмана
sym *makeTree(sym *psym[],int k) { 
  int i, j;
    sym *temp;
    temp = new sym;
    temp->freq = psym[k-1]->freq+psym[k-2]->freq;
    temp->code[0] = 0;
    temp->left = psym[k-1];
    temp->right = psym[k-2];
    if ( k == 2 )
        return temp;
    else {
    //внесение в нужное место массива элемента дерева Хаффмана
      for ( i = 0; i < k; i++)
        if ( temp->freq > psym[i]->freq ) {
          for( j = k - 1; j > i; j--)
            psym[j] = psym[j-1]; 
            psym[i] = temp;
            break;
        } 
    }
  return makeTree(psym,k-1);
}
//рекурсивная функция кодирования дерева
void makeCodes(sym *root) { 
  if ( root->left ) {
    strcpy(root->left->code,root->code);
    strcat(root->left->code,"0");
    makeCodes(root->left);
  }
  if ( root->right ) {
    strcpy(root->right->code,root->code);
    strcat(root->right->code,"1");
    makeCodes(root->right);
  }
}
/*функция подсчета количества каждого символа и его вероятности*/
void Statistics(char *String){
  int i, j;
  //побайтно считываем строку и составляем таблицу встречаемости 
  for ( i = 0; i < strlen(String); i++){
    chh = String[i];
    for ( j = 0; j < 256; j++){
      if (chh==simbols[j].ch) {
        kolvo[j]++;
        kk++; 
        break;
      }
      if (simbols[j].ch==0){
        simbols[j].ch=(unsigned char)chh;
        kolvo[j]=1;
        k++; kk++;
        break;
      } 
    } 
  }
  // расчет частоты встречаемости
  for ( i = 0; i < k; i++)
    simbols[i].freq = (float)kolvo[i] / kk;
  // в массив указателей заносим адреса записей
  for ( i = 0; i < k; i++) 
    psym[i] = simbols[i];
  //сортировка по убыванию 
  sym tempp;
  for ( i = 1; i < k; i++)
  for ( j = 0; j < k - 1; j++)
    if ( simbols[j].freq < simbols[j+1].freq ){
      tempp = simbols[j];
      simbols[j] = simbols[j+1];
      simbols[j+1] = tempp;
    }
  for( i=0;i<k;i++)  {
    summir+=simbols[i].freq; 
    printf("Ch= %d\tFreq= %f\tPPP= %c\t\n",simbols[i].ch,
            simbols[i].freq,psym[i]->ch,i);
  }
  printf("\n Slova = %d\tSummir=%f\n",kk,summir);
}
//функция кодирования строки
void CodeHuffman(char *String,char *BinaryCode, sym *root){
  for (int  i = 0; i < strlen(String); i++){
    chh = String[i];
    for (int  j = 0; j < k; j++)
      if ( chh == simbols[j].ch ){
        strcat(BinaryCode,simbols[j].code);
      }
  }
}
//функция декодирования строки
void DecodeHuffman(char *BinaryCode,char *ReducedString, 
                   sym *root){
  sym *Current;// указатель в дереве
  char CurrentBit;// значение текущего бита кода
  int BitNumber;
  int CurrentSimbol;// индекс распаковываемого символа
  bool FlagOfEnd;  // флаг конца битовой последовательности
  FlagOfEnd = false;
  CurrentSimbol = 0;
  BitNumber = 0;
  Current = root;
  //пока не закончилась битовая последовательность
  while ( BitNumber != strlen(BinaryCode) ) {
    //пока не пришли в лист дерева
    while (Current->left != NULL  Current->right != NULL  
           BitNumber != strlen(BinaryCode) ) {
      //читаем значение очередного бита
      CurrentBit = BinaryCode[BitNumber++];
      //бит – 0, то идем налево, бит – 1, то направо
      if ( CurrentBit == '0' ) 
        Current = Current->left;
      else 
        Current = Current->right;
    }
    //пришли в лист и формируем очередной символ
    ReducedString[CurrentSimbol++] = Current->ch;
    Current = root;
  }
  ReducedString[CurrentSimbol] = 0;
}

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

Ключевые термины

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

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

Сжатие с потерями – это метод сжатия данных, при котором для обеспечения максимальной степени сжатия исходного массива данных часть содержащихся в нем данных отбрасывается.

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

Алфавит кода – это множество всех символов входного потока.

Кодовый символ – это наименьшая единица данных, подлежащая сжатию.

Кодовое слово – это последовательность кодовых символов из алфавита кода.

Токен – это единица данных, записываемая в сжатый поток некоторым алгоритмом сжатия.

Фраза – это фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – это процесс сжатия данных.

Декодирование – это обратный кодированию процесс, при котором осуществляется восстановление данных.

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

Коэффициент сжатия – это величина, обратная отношению сжатия.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в некоторой структуре данных, называемой словарем.

Хаффмановское кодирование (сжатие) – это метод сжатия, присваивающий символам алфавита коды переменной длины основываясь на вероятностях появления этих символов.

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова.

Оптимальный префиксный код – это префиксный код, имеющий минимальную среднюю длину.

Кодовое дерево (дерево кодирования Хаффмана, Н-дерево) – это бинарное дерево, у которого: листья помечены символами, для которых разрабатывается кодировка; узлы (в том числе корень) помечены суммой вероятностей появления всех символов, соответствующих листьям поддерева, корнем которого является соответствующий узел.

Краткие итоги

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

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

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 41.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученным алгоритмами сжатия данных по методу Хаффмана и с использованием кодовых деревьев, реализовав программный код на языке С++. Рекомендуется воспользоваться материалами лекции 41, где подробно рассматриваются описание используемых в работе алгоритмов, примеры их реализации на языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи и привести примеры входных и выходных файлов, полученных на этапе тестирования программ. В отчете отразить анализ степени сжатия данных на примере тестовых заданий.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы