Algorytm Huffmana z listą i drzewem

Wymagane jest zapoznanie się z następującymi podrozdziałami:

    OL013 - Lista.
    OL014 - Algorytm wyszukiwania dwóch najmniejszych elementów na liście.
    OL015 - Drzewo binarne, algorytm inorder.

Kompresja danych polega na takim kodowaniu informacji, aby w wyniku otrzymać jak najkrótszy ciąg bitów. Algorytm Huffmana realizuje zadanie kompresji tworząc bezprzystankowe kody binarne, gdzie symbole występujące najczęściej w kodowanej informacji otrzymują kody najkrótsze, a symbole występujące rzadziej otrzymują kody dłuższe.

Dla zobrazowania zasady działania algorytmu Huffmana załóżmy, iż mamy skompresować tekst zawierający 8 symboli A, B, C, D, E, F, G i H:

EAEACDGDGEGGFGDFGHGAGGBEEEDGHH

Jeśli zastosujemy normalne kodowanie binarne, to każdemu z 8 symboli musimy przypisać kod 3 bitowy, np:

A - 000, B - 001, C - 010, D - 011, E - 100, F - 101, G - 110, H - 111

Wtedy powyższy napis można przedstawić w postaci strumienia bitów:

100000100000010011110011110100110110101110011101110111110000110110001100100100011110111111

Jak łatwo policzyć, strumień ten zawiera 30 znaków x 3 bity na znak = 90 bitów.

Policzmy teraz ilość wystąpień każdego znaku w tekście. Otrzymamy następujące wartości:

Znak A B C D E F G H
Częstość 3 1 1 4 6 2 10 3

Ze znaku i jego częstości tworzymy węzeł-liść drzewa binarnego. Węzły nie są jeszcze połączone w drzewo. Umieszczamy je na liście dwukierunkowej:

obrazek

Z listy wybieramy dwa węzły o najmniejszych częstościach występowania:

obrazek

Wyjęte z listy węzły łączymy w drzewo binarne. Korzeń staje się nowym elementem, którego częstość jest równa sumie częstości obu liści. Korzeń wstawiamy z powrotem na listę:

obrazek

Ostatnie operacje (wybranie z listy dwóch węzłów o najmniejszej częstości, utworzenie z nich drzewa i wstawienie korzenia na listę) powtarzamy dotąd, aż lista będzie zawierała tylko jeden element - binarne drzewo kodu Huffmana:

obrazek          obrazek
obrazek          obrazek
obrazek          obrazek
obrazek          obrazek
obrazek          obrazek
obrazek

Zgodnie z drzewem wynikowym otrzymaliśmy następujące kody dla poszczególnych znaków:

A - 100, B - 00000, C - 00001, D - 001, E - 11, F - 0001, G - 01, H - 101

Tekst zakodowany za pomocą tych kodów ma postać:

11100111000000100101001011101010001010010001011010110001010000011111100101101101

a oryginalny był następujący:

100000100000010011110011110100110110101110011101110111110000110110001100100100011110111111

Nawet wzrokowo widzimy, iż kod Huffmana jest krótszy. Dokonaliśmy zatem kompresji danych. Kod Huffmana daje efektywną kompresję tylko wtedy, gdy częstości występowania symboli różnią się od siebie. W przeciwnym wypadku powstaje kod o stałej liczbie bitów na symbol. W rzeczywistych systemach kompresji danych musi być jeszcze przekazana informacja o strukturze drzewa kodowego Huffmana, które pozwala odczytać skompresowany strumień danych.

       Program

Na wejście programu podajemy wiersz znaków. Na wyjściu dla każdego znaku otrzymujemy informację o jego liczbie wystąpień oraz odpowiadający mu kod Huffmana. Informacja ta może posłużyć do zakodowania tekstu.

Program wykorzystuje klasę listy dwukierunkowej - TdoubleList oraz funkcję rekurencyjnego przechodzenia przez drzewo binarne - inorder.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P016

#include <iostream>
#include <string>

using namespace std;

// deklaracja węzła drzewa binarnego
//----------------------------------

struct TBTnode
{
  TBTnode * parent, * left, * right;
  char    c;
};

// deklaracja typu elementu listy
//-------------------------------

struct TlistElement
{
  TlistElement * next, * prev;
  int          key;
  TBTnode      * node;
};

// deklaracja typu klasy listy dwukierunkowej
//-------------------------------------------

class TdoubleList
{
  private:

    TlistElement * front, * back;
    unsigned     cnt;

  public:
           
// konstruktor
//------------

    TdoubleList()
    {
      front = back = NULL;
      cnt   = 0;
    }
    
// Zwraca długość listy
//---------------------

    unsigned size()
    {
      return cnt;
    }

// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------

    TlistElement * push_front(TlistElement * p)
    {
      p->next = front; p->prev = NULL;
      if(front) front->prev = p;
      front = p;
      if(!back) back = front;
      cnt++;
      return front;
    }
    
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------

    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL; p->prev = back;
      back = p;
      if(!front) front = back;
      cnt++;
      return back;
    }
    
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------

    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next; p1->prev = p2;
      p2->next = p1;
      if(p1->next) p1->next->prev = p1;
      else back = p1;
      cnt++;
      return p1;
    }
    
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------

    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        else front->prev = NULL;
        cnt--;
        return p;
      }
      else return NULL;     
    }
    
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------

    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = back->prev;
          back->next = NULL;
        };
        cnt--;
        return p;
      }
      else return NULL;
    }
    
// usuwa z listy element p i zwraca adres usuniętego elementu

    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;
      
      if(p->prev) p->prev->next = p->next;
      else front = p->next;
      if(p->next) p->next->prev = p->prev;
      else back = p->prev;
      cnt--;
      return p;
    } 

// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------

    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > cnt)) return NULL;
      else if(n == cnt) return back;
      else if(n < cnt / 2)
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
      else
      {
        p = back;
        while(cnt > n++) p = p->prev;
        return p;
      }  
    }

// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------

    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          if(p->node) 
            cout << p->node->c << " : " << p->key << endl;
          p = p->next;
        }
      }
    }

// Wyszukuje na liście dwa najmniejsze elementy
//---------------------------------------------

    void find2min(TlistElement * &p1, TlistElement * &p2)
    {
      TlistElement * p;

      p1 = front; p2 = front->next;
      if(p1->key > p2->key)
      {
        TlistElement * x;
        x = p1; p1 = p2; p2 = x;
      }
      p = front->next->next;
      while(p)
      {
        if(p->key < p2->key)
        {
          p2 = p;
          if(p1->key > p2->key)
          {
            TlistElement * x;
            x = p1; p1 = p2; p2 = x;
          }      
        }
        p = p->next;
      }     
    }    
};

// Funkcja rekurencyjne przechodzenia drzewa binarnego
//----------------------------------------------------

void inorder(TBTnode * n, char c[], int lenc)
{
  if(!(n->left))
  {
    cout << n->c << " : ";
    for(int i = 0; i < lenc; i++) cout << c[i];
    cout << endl;
  }
  else
  {
    c[lenc] = '0'; inorder(n->left,c,lenc + 1);
    c[lenc] = '1'; inorder(n->right,c,lenc + 1);    
  }
}

//******************************************************
//**   Przykładowa implementacja algorytmu Huffmana   **
//******************************************************

main()
{
  int i;
    
// Ze standardowego wejścia odczytujemy wiersz znaków

  string line;  // przechowuje odczytany tekst
  
  getline(cin,line);
  
// Zliczamy liczbę wystąpień każdego znaku

  int ccount[256]; // liczniki znaków
  
  for(i = 0; i < 256; i++) ccount[i] = 0;
  for(i = line.size() - 1; i >= 0; i--) ccount[line[i]]++;
  
// tworzymy listę pojedynczych węzłów drzewa binarnego,
// na której umieszczamy tylko znaki występujące w
// odczytanym wierszu - pomijamy znaki nieobecne.

TdoubleList  dl;
TlistElement * p1, * p2, * p;
TBTnode      * n;
  
  for(i = 255; i >= 0; i--)
    if(ccount[i])
    {
      n = new TBTnode;
      n->parent = n->left = n->right = NULL;
      n->c = i;
      p = new TlistElement;
      p->node = n;
      p->key = ccount[i];
      dl.push_front(p);
    }

// wyświetlamy znaki wraz z ich częstościami w wierszu

  cout << endl;
  dl.showKeys();
  cout << endl;
  
// tworzymy drzewo binarne Huffmana

  while(dl.size() > 1)
  {

// na liście wyszukujemy dwa najmniejsze elementy

    dl.find2min(p1,p2);

// z węzłów zawartych w p1 i p2 tworzymy nowy węzeł

    n = new TBTnode;
    n->parent = NULL;
    n->left  = p1->node;
    n->right = p2->node;
    n->left->parent = n->right->parent = n;
    
// nowy węzeł drzewka umieszczamy w p1

    p1->node = n;

// obliczamy wartość klucza

    p1->key += p2->key;
    
// p2 usuwamy z listy i z pamięci - nie jest już potrzebne

    delete dl.erase(p2);
  }  

// wywołujemy rekurencyjną funkcję inorder, która
// przejdzie przez całe drzewko wypisując kody Huffmana
// poszczególnych liści - znaków

  char hcodes[256]; // przechowuje kody Huffmana odczytane z drzewka

  inorder(dl.index(1)->node,hcodes,0);
  
// gotowe - kończymy program

  cout << endl << endl; 
  system("PAUSE");
}

DAAFDDGFDSESESFSFDDFADFDAFDAFDDFSFDSFDSFDSDXFDDFSFDFFDAFDFDXFDFDGFDGFDSDAAAASAAD
SASASASASASASASAAAAAAAAASASSAWASAAAAAASASASDADDSADSADSSAASAAAADSADSSDAAAAADSASAD
SAAAAAAAASDADSADSADSASASASSSAAAAASSADSASADSAAAAFDFESDSADSADDSADADSFFFDSDSDAAAAAA

A : 92
D : 53
E : 3
F : 28
G : 3
S : 58
W : 1
X : 2

A : 0
S : 10
W : 110000
X : 110001
E : 110010
G : 110011
F : 1101
D : 111

       Zadanie

Powyższy program jest tylko częścią systemu kompresji Huffmana - określa on kody dla poszczególnych znaków zawartych w kompresowanym tekście. Zastanów się nad rozbudową programu, która obejmie również fazę kodowania znaków tekstu wg otrzymanych kodów. A może zaprojektujesz kompletną aplikację kompresji dowolnych plików binarnych oraz ich dekompresji? W takim przypadku zastanów się, jak przekazać w skompresowanym pliku informację o zastosowanym przy kompresji drzewie Huffmana. Informacja ta jest niezbędna do wydobycia znaków ze skompresowanego pliku.

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe