Kompresja Huffmana


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew

Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy

  Co to jest kompresja
Kody o stałej długości
Kody bezprzystankowe
Kodowanie Huffmana

Problem

Dany łańcuch przedstawić za pomocą możliwie małej liczby bitów.


Co to jest kompresja

Z kompresją danych spotykamy się często w informatyce i jej zastosowaniach. Pliki kompresuje się, aby zajmowały mniej miejsca na nośnikach danych lub były szybciej transmitowane poprzez sieć. Aby zrozumieć ideę kompresji, spójrz na poniższy przykład:

 

Załóżmy, że mamy pewien ciąg znaków zbudowany z dużych liter od A do Z. Wygląda on następująco:

 

ABJHLHJAAAAOOOOAOALKAJJJJAKUAMMMMMUANGGGHAJJJAKKKKKKAKKKKKKKAB

 

Czy można go zapisać w krótszy sposób, czyli czy można go skompresować? Na początek zauważamy, że w ciągu występują powtarzające się znaki. Można je zapisać bardziej efektywnie, wprowadzając prostą zasadę: ciąg powtarzających się znaków zapisujemy jako liczbę i znak, który się powtarza, a liczba określa ilość tych powtórzeń. Gdy zastosujemy tę regułę, otrzymamy poniższy ciąg znaków:

 

ABJHLHJ4A4OAOALKA4JAKUA6MUAN3GHA3JA6KA7KAB

 

Tekst jest wyraźnie krótszy. Co więcej, możemy go z powrotem przetworzyć na tekst pierwotny, zastępując liczby odpowiednią ilością znaków. Zwróć jednakże uwagę, że taka kompresja była możliwa po wprowadzeniu dodatkowych znaków, mianowicie cyfr. Te dodatkowe znaki są interpretowane inaczej od reszty znaków tworzących nasz tekst.

 

Taki system kompresji był kiedyś stosowany, np. w grafice, gdzie na obrazie występują duże obszary w jednolitym kolorze (to jakby powtarzające się ciągi znaków). Oczywiście jest on prymitywny, ponieważ nie rozpoznaje powtarzających się struktur wieloznakowych, np: ABABABABABABABABAB. Znacznie lepszy system kompresji opracował amerykański informatyk David Huffman. Polega on na zastępowaniu znaków ciągami bitów o różnej długości – znaki występujące najczęściej posiadają kody najkrótsze, dzięki czemu sumaryczna liczba bitów jest mniejsza niż przy stosowaniu kodów o stałej długości. Zanim przejdziemy do omówienia metody kodowania Huffmana, przyjrzyjmy się tzw. kodom o stałej długości (fixed length codes) i kodom bezprzystankowym (ang. prefix-free codes).

 

Kody o stałej długości

Załóżmy, że chcemy kodować 4 znaki: A, B, C i D. Znakom tym przypisujemy kody dwubitowe:

 

A → 00
B → 01
C → 10
D → 11

 

Załóżmy dalej, że mamy zakodować tekst:

 

ABACCDABBD

 

Każdą literę zastępujemy odpowiadającą jej grupą dwóch bitów:

 

ABACCDABBD → 00010010101100010111

 

Proces odwrotny jest równie prosty. Ciąg bitów dzielimy na grupy dwubitowe i każdą z tych grup zamieniamy na odpowiadającą jej literę:

 

01001000 → 01 00 10 00 → BACA

 

Tak działa kodowanie liter w standardzie ASCII, gdzie każdy znak to 8 bitów. Jak widzimy, kody o stałej liczbie bitów nie sprawiają kłopotów.

 

Uwaga techniczna:
W opisywanych tutaj algorytmach zamiast bitów używane są łańcuchy znakowe zawierające znaki 0 i 1. Podyktowane to zostało względami dydaktycznymi. Po prostu łańcuchy znakowe są dla ucznia łatwiejsze do ogarnięcia. Gdyby zostały wybrane bity, należałoby rozwiązać wiele dodatkowych problemów, np. łączenie poszczególnych bitów w ciąg, określanie długości takiego ciągu oraz jego podział na bajty w celu umieszczenia w pamięci. Są to sprawy w sumie drugorzędne, implementacyjne. Nie wpływają one na samą zasadę działania poszczególnych algorytmów. Zdolny informatyk nie będzie miał większych problemów z przerobieniem prezentowanych algorytmów tak, aby wynikiem ich pracy były ciągi bitów, a nie łańcuchy tekstowe ze znaków 0 i 1.

W tekście odwołujemy się do bitów w cudzysłowach, aby dać do zrozumienia, że faktycznie u nas są to znaki 0 lub 1 kodu ASCII, a nie prawdziwe bity. Pamiętaj o tym!

 

Kody bezprzystankowe

Jeśli chcemy stosować kody o różnej liczbie bitów, to muszą one spełniać jeden podstawowy warunek: żaden kod nie może być przedrostkiem (czyli początkowym fragmentem) innego kodu. Dlaczego to jest takie ważne? Wyobraź sobie, że masz dwa kody:

 

A → 0
B → 01

 

Dostałeś ciąg bitów:

 

0101000....

 

Jaki znak jest na początku? A czy B? Zatem każdy kod dłuższy nie może posiadać na początku tych samych bitów co kod krótszy, inaczej czasami nie będziemy w stanie ich rozróżnić.

Kody bezprzystankowe reprezentuje się drzewem binarnym. Interpretacja takiego drzewa jest bardzo prosta. Liść określa zawsze kodowany znak. Ścieżka prowadząca od korzenia drzewa do danego liścia określa kod znaku: gałąź lewa ma wartość bitową 0, gałąź prawa ma wartość bitową 1. Idąc po ścieżce, zbieramy kolejne bity aż dojdziemy do liścia. W ten sposób otrzymamy kod znaku w liściu. Oto przykład:

 

     A → 0
B → 10
C → 110
D → 111

 

Zwróć uwagę, że węzeł nie będący liściem posiada zawsze dwóch synów. Czy potrafisz uzasadnić tę własność drzewa kodu bezprzystankowego? Druga cecha to niezrównoważenie drzewa. Skoro kody mają posiadać różną długość, to ścieżki również muszą być różnej długości, a taką cechę posiadają tylko drzewa niezrównoważone.

Węzeł drzewa powinien posiadać trzy pola: left, right (wskazania lewego i prawego syna) oraz key (kodowany znak).

 

Lazarus Code::Blocks Free Basic
type
  PTNode = ^TNode;
  TNode  = record
    left  : PTNode;
    right : PTNode;
    key   : char;
  end;
struct TNode
{
  TNode * left;
  TNode * right;
  char key;
};
Type TNode
  left  As TNode Ptr
  right As TNode Ptr
  key   As String * 1
End Type

 

Zasada tworzenia drzewa kodu bezprzystankowego jest następująca:

 

Korzeń drzewa powinien zawsze zawierać węzeł startowy.

Zapamiętujemy kodowany znak i przystępujemy do odczytu kolejnych bitów jego kodu w pętli, ustawiając węzeł bieżący na korzeń drzewa. Jeśli nie ma dalszych bitów, to zapamiętany znak umieszczamy w bieżącym węźle. Inaczej odczytujemy bit kodu. Jeśli ma on wartość 0 i nie istnieje lewy syn bieżącego węzła, to tworzymy lewego syna. Jeśli ma wartość 1 i prawy syn nie istnieje, to tworzymy go. Przechodzimy do lewego syna (dla bitu 0) lub do prawego syna (dla bitu 1) i kontynuujemy pętlę odczytu bitów.

Gdy pętla się zakończy, przechodzimy do definicji kolejnego znaku i całość procedury powtarzamy. Jeśli brak dalszych definicji, kończymy. Drzewo jest gotowe.

 

Algorytm tworzenia drzewa kodu przystankowego

Wejście
n    liczba znaków kodu
root   zmienna przechowująca adres korzenia drzewa. Drzewo powinno zawierać jeden węzeł startowy.

W strumieniu wejściowym powinny się znaleźć n par: znak i ciąg bitów

Wyjście:
root    wskazuje drzewo kodu bezprzystankowego
Elementy pomocnicze:
p    wskaźnik węzła
s  – znak kodu
b  – łańcuch kodu
i  – licznik pętli znaków, i C
j  – licznik pętli bitów kodu, j C
Lista kroków:
K01: Dla i = 1,2,...,n: wykonuj K02...K19  
K02:     Czytaj s, b ; odczytujemy znak oraz jego kod ze strumienia wejściowego
K03:     proot ; ustawiamy węzeł bieżący na węzeł startowy
K04:     Dla j = 0,1,...,|b|-1: wykonuj K05...K18 ; przetwarzamy kolejne "bity" kodu
K05:         Jeśli b[j] = "1", to idź do K13 ; przetwarzamy "bit" 0
K06:         Jeśli (pleft) ≠ nil, to idź do K11 ; sprawdzamy, czy bieżący węzeł ma lewego syna
K07:         Utwórz nowy węzeł ; jeśli nie, to tworzymy lewego syna
K08:         (pleft) ← adres nowego węzła  
K09:         (pleftleft) ← nil ; ustawiamy pola nowego węzła
K10:         (pleftright) ← nil  
K11:         p ← (pleft) ; przechodzimy do lewego syna
K12:         Następny obieg pętli K04 ; i kontynuujemy pętlę
K13:         Jeśli (pright) ≠ nil, to idź do K18 ; to samo dla "bitu" 1
K14:         Utwórz nowy węzeł  
K15:         (pright) ← adres nowego węzła  
K16:         (prightleft) ← nil  
K17:         (prightright) ← nil  
K18:         p ← (pright)  
K19:     (pkey) ← s ; znak umieszczamy w węźle
K20 Zakończ  

 

Zasada odczytu informacji zakodowanej kodem bezprzystankowym jest następująca (przy założeniu, że informacja nie zawiera błędów typu zbyt mała liczba bitów lub przekłamania bitów):

 

Ustawiamy wskaźnik bieżącego węzła na korzeń drzewa.

W pętli odczytujemy "bit" kodu i przechodzimy wzdłuż odpowiedniej krawędzi drzewa: dla "bitu" 0 wzdłuż krawędzi lewej, dla "bitu" 1 wzdłuż krawędzi prawej. Następnie sprawdzamy, czy doszliśmy do liścia. Jeśli tak, wypisujemy znak przechowywany w liściu i ustawiamy wskaźnik bieżącego węzła na korzeń drzewa. Pętlę kontynuujemy aż do wyczerpania wszystkich bitów w ciągu wejściowym.

 

Algorytm dekodowania wiadomości w kodzie bezprzystankowym

Wejście
root    wskazanie korzenia drzewa kodu bezprzystankowego

W strumieniu wejściowym powinien się znaleźć tekst zawierający zakodowaną informację za pomocą znaków 0 i 1 w kodzie bezprzystankowym.

Wyjście:
Rozkodowana wiadomość
Elementy pomocnicze:
p    wskaźnik węzła
b  – łańcuch znaków 0 i 1 tworzący zakodowaną wiadomość w kodzie bezprzystankowym
i  – licznik pętli bitów, i C
Lista kroków:
K01: Czytaj b ; odczytujemy ciąg "bitów" 0 i 1 ze strumienia wejściowego
K02: proot ; ustawiamy wskaźnik na węzeł startowy drzewa
K03: Dla i = 0,1,...,|b|-1: wykonuj K04...K07 ; w pętli przetwarzamy kolejne "bity"
K04:     Jeśli b[i] = "0", to p ← (pleft)
    Inaczej                p ← (pright)
; przechodzimy wzdłuż odpowiedniej krawędzi
K05:     Jeśli (pleft) ≠ nil, to następny obieg pętli K03 ; sprawdzamy, czy osiągnęliśmy liść
K06:     Pisz (pkey) ; jeśli tak, piszemy znak z węzła
K07:     proot ; wracamy na początek drzewa
K08: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program jest przykładową aplikacją dydaktyczną, która wczytuje definicję kodu bezprzystankowego, tworzy na jej podstawie odpowiednie drzewo kodu, po czym wczytuje ciąg zer i jedynek, w których zapisana jest wiadomość. Następnie odtwarza wiadomość, korzystając z utworzonego drzewa kodu. Format danych wejściowych jest następujący:

 

Pierwsza liczba określa ilość słów kodowych n. Następnie występuje n wierszy typu znak, spacja, kod binarny. W ostatnim wierszu jest łańcuch z zakodowaną tym kodem wiadomością.

 

Przykładowe dane wejściowe:

 

6
A 0
B 100
C 101
D 110
E 1110
F 1111
110111010101111010011100

 

Lazarus
// Kody bezprzystankowe
// Data: 26.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program pfcodes;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
type
  PTNode = ^TNode;
  TNode  = record
    left  : PTNode;
    right : PTNode;
    key   : char;
  end;

// Tworzy z danych wejściowych
// drzewo kodu bezprzystankowego
//------------------------------
procedure makeT(var root : PTNode);
var
  n,i,j : integer;
  s,x   : char;
  b     : string;
  p     : PTNode;
begin
  new(root);                    // Tworzymy węzeł startowy
  root^.left  := nil;           // Wypełniamy pola
  root^.right := nil;

  readln(n);                    // Odczytujemy liczbę definicji

  for i := 1 to n do            // W pętli tworzymy drzewo
  begin
    readln(s,x,b);              // Czytamy znak, spację x i kod

    p := root;                  // Rozpoczynamy od korzenia

    for j := 1 to length(b) do  // Przetwarzamy kolejne bity kodu
      if b[j] = '0' then        // Czy bit = 0?
      begin
        if p^.left = nil then   // Czy istnieje lewy syn?
        begin
          new(p^.left);         // Jeśli nie, to go tworzymy
          p^.left^.left  := nil;
          p^.left^.right := nil;
        end;
        p := p^.left;           // Przechodzimy do lewego syna
      end
      else                      // To samo dla bit = 1
      begin
        if p^.right = nil then  // Czy istnieje prawy syn?
        begin
          new(p^.right);        // Jeśli nie, to go tworzymy
          p^.right^.left  := nil;
          p^.right^.right := nil;
        end;
        p := p^.right;          // Przechodzimy do prawego syna
      end;

    p^.key := s;                // Do liścia wstawiamy znak

  end;
end;

// Dekoduje wiadomość w kodzie bezprzystankowym
//---------------------------------------------
procedure decodeT(root : PTNode);
var
  p : PTNode;
  b : string;
  i : integer;
begin
  readln(b);                   // Odczytujemy kod

  writeln;

  p := root;                   // Bieżący węzeł ustawiamy na początek drzewa

  for i := 1 to length(b) do   // Przetwarzamy kolejne bity kodu
  begin
    if b[i] = '0' then p := p^.left
    else               p := p^.right;
    if p^.left = nil then
    begin
      write(p^.key);
      p := root;
    end;
  end;

  writeln;

end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  root : PTNode;            // Korzeń drzewa
begin
  makeT(root);              // Tworzymy drzewo kodu bezprzystankowego
  decodeT(root);            // Dekodujemy wiadomość
  DFSRelease(root);         // Usuwamy drzewo z pamięci
end.
Code::Blocks
// Kody bezprzystankowe
// Data: 26.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>

using namespace std;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
struct TNode
{
  TNode * left;
  TNode * right;
  char key;
};

// Tworzy z danych wejściowych
// drzewo kodu bezprzystankowego
//------------------------------
void makeT(TNode * & root)
{
  int n,i,j;
  char s;
  string b;
  TNode * p;

  root = new TNode;             // Tworzymy węzeł startowy
  root->left  = NULL;           // Wypełniamy pola
  root->right = NULL;

  cin >> n;                     // Odczytujemy liczbę definicji

  for(i = 0; i < n; i++)        // W pętli tworzymy drzewo
  {
    cin >> s >> b;              // Czytamy znak i kod

    p = root;                   // Rozpoczynamy od korzenia

    for(j = 0; j < (int)b.length(); j++)  // Przetwarzamy kolejne bity kodu
      if(b[j] == '0')                // Czy bit = 0?
      {
        if(!p->left)                 // Czy istnieje lewy syn?
        {
          p->left = new TNode;       // Jeśli nie, to go tworzymy
          p->left->left  = NULL;
          p->left->right = NULL;
        }
        p = p->left;                 // Przechodzimy do lewego syna
      }
      else                           // To samo dla bit = 1
      {
        if(!p->right)                // Czy istnieje prawy syn?
        {
          p->right = new TNode;      // Jeśli nie, to go tworzymy
          p->right->left  = NULL;
          p->right->right = NULL;
        }
        p = p->right;          // Przechodzimy do prawego syna
      }

    p->key = s;                // Do liścia wstawiamy znak

  }
}

// Dekoduje wiadomość w kodzie bezprzystankowym
//---------------------------------------------
void decodeT(TNode * root)
{
  TNode * p;
  string b;
  int i;

  cin >> b;                   // Odczytujemy kod

  cout << endl;

  p = root;                   // Bieżący węzeł ustawiamy na początek drzewa

  for(i = 0; i < (int)b.length(); i++)   // Przetwarzamy kolejne bity kodu
  {
    if(b[i] == '0') p = p->left;
    else            p = p->right;
    if(!p->left)
    {
      cout << p->key;
      p = root;
    }
  }

  cout << endl;

}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(TNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  TNode * root;            // Korzeń drzewa

  makeT(root);             // Tworzymy drzewo kodu bezprzystankowego
  decodeT(root);           // Dekodujemy wiadomość
  DFSRelease(root);        // Usuwamy drzewo z pamięci

  return 0;
}
Free Basic
' Kody bezprzystankowe
' Data: 26.06.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Definicja węzła drzewa kodu bezprzystankowego
'----------------------------------------------
Type TNode
  left  As TNode Ptr
  right As TNode Ptr
  key   As String * 1
End Type

' Tworzy z danych wejściowych
' drzewo kodu bezprzystankowego
'------------------------------
Sub makeT(ByRef root As TNode Ptr)

  Dim As Integer n,i,j
  Dim As String * 1 s,x
  Dim As String b
  Dim As TNode Ptr p

  root = new TNode             ' Tworzymy węzeł startowy
  root->left  = 0              ' Wypełniamy pola
  root->right = 0

  Input #1, n                  ' Odczytujemy liczbę definicji

  For i = 1 To n               ' W pętli tworzymy drzewo
    s = Input(2,#1)            ' Czytamy znak i spację
    Input #1,b                 ' Czytamy kod
    
    p = root                   ' Rozpoczynamy od korzenia
    
    For j = 1 To Len(b)        ' Przetwarzamy kolejne bity kodu
      If Mid(b,j,1) = "0" Then ' Czy bit = 0?
        If p->Left = 0 Then    ' Czy istnieje lewy syn?
          p->left = new TNode  ' Jeśli nie, to go tworzymy
          p->left->left  = 0
          p->left->right = 0
        End If
        p = p->Left            ' Przechodzimy do lewego syna
      Else                     ' To samo dla bit = 1
        if p->Right = 0 Then   ' Czy istnieje prawy syn?
          p->right = new TNode ' Jeśli nie, to go tworzymy
          p->right->left  = 0
          p->right->right = 0
        End If
        p = p->Right           ' Przechodzimy do prawego syna
      End If
    Next
    
    p->key = s                 ' Do liścia wstawiamy znak
    
  Next
  
End Sub

' Dekoduje wiadomość w kodzie bezprzystankowym
'---------------------------------------------
Sub decodeT(ByVal root As TNode Ptr)
	
  Dim As TNode Ptr p
  Dim As String b
  Dim As Integer i

  Input #1, b                ' Odczytujemy kod

  Print

  p = root                   ' Bieżący węzeł ustawiamy na początek drzewa

  For i = 1 To Len(b)        ' Przetwarzamy kolejne bity kodu
    If Mid(b,i,1) = "0" Then
    	p = p->Left
    Else
      p = p->Right
    End If
    If p->Left = 0 then
      print p->key;
      p = root
    End If
  Next

  Print
  
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(ByVal v As TNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As TNode Ptr root   ' Korzeń drzewa

Open Cons For Input As #1

makeT(root)             ' Tworzymy drzewo kodu bezprzystankowego
decodeT(root)           ' Dekodujemy wiadomość
DFSRelease(root)        ' Usuwamy drzewo z pamięci

Close #1

End
Wynik
6
A 0
B 100
C 101
D 110
E 1110
F 1111
110111010101111010011100

DECAFABEA

 

Tłumaczenie wiadomości na kod bezprzystankowy polega zawsze na znajdowaniu odpowiedniego kodu dla tłumaczonego znaku. Jeśli mamy do dyspozycji drzewo kodu, to możemy wykorzystać w odpowiedni sposób rekurencyjny algorytm przechodzenia drzewa, np. preorder. Może to działać następująco:

 

Do funkcji rekurencyjnej wchodzimy z trzema parametrami – z kodowanym znakiem, ze wskazaniem węzła drzewa kodu bezprzystankowego oraz z łańcuchem opisującym ścieżkę do tego węzła. Pamiętamy, że ścieżka ta zawiera tylko cyfry 0 (dla krawędzi w lewo) i 1 (dla krawędzi w prawo). Jeśli węzeł jest liściem, to sprawdzamy, czy znak przechowywany w węźle jest znakiem otrzymanym jako parametr. Jeśli tak, to wyprowadzamy na wyjście łańcuch z parametru i kończymy z wynikiem true. W przeciwnym razie kończymy z wynikiem false. Jeśli węzeł nie jest liściem, to posiada dwóch synów. Wywołujemy rekurencyjnie funkcję dla lewego syna, przekazując w parametrze łańcuch z dodanym na końcu znakiem '0', który reprezentuje bit 0. Jeśli wynikiem będzie true, to kończymy, zwracając ten wynik. W przeciwnym razie wywołujemy rekurencyjnie funkcję dla prawego syna, przekazując w parametrze łańcuch z dodanym na końcu znakiem '1'. Zwracamy jako wynik to, co zwróci wywołana funkcja.

 

Metoda taka praktycznie nie byłaby stosowana, posiada ona jedynie wartość dydaktyczną. W praktyce drzewo kodu przystankowego zostałoby przekształcone w odpowiednie drzewo poszukiwań binarnych, w którym kluczami byłyby kodowane znaki. Dodatkowo węzły przechowywałyby informację o kodzie znaku. Kodowanie polegałoby na wyszukaniu węzła z kodowanym znakiem i użyciu kodu przechowywanego w tym węźle. Takie podejście skracałoby czas poszukiwań do klasy O(log n). Jako ćwiczenie możesz zastanowić się nad sposobem przekształcenia drzewa kodu bezprzystankowego w zrównoważone drzewo binarnych poszukiwań. Wyjdzie z tego całkiem ciekawy algorytm.

 

Algorytm rekurencyjnego kodowania kodem bezprzystankowym codeT(c,p,b)

Wejście
c    kodowany znak
p    wskazanie węzła drzewa kodu bezprzystankowego
b    łańcuch ścieżki do węzła

Pierwsze wywołanie funkcji rekurencyjnej codeT() powinno być wykonane z poszukiwanym znakiem, z korzeniem drzewa oraz z tekstem pustym.

Wyjście:
true, jeśli kod znaku został znaleziony. Wtedy na wyjście trafia jego kod.
false, jeśli kod znaku nie został znaleziony
Lista kroków:
K01: Jeśli (pleft) ≠ nil, to idź do K05 ; sprawdzamy, czy węzeł p jest liściem
K02: Jeśli c ≠ (pkey), to zakończ z wynikiem false ; sprawdzamy, czy węzeł przechowuje kodowany znak
K03: Pisz b ; jeśli tak, to na wyjście wyprowadzamy kod
K04 Zakończ z wynikiem true  
K05: Jeśli codeT(c,(pleft),b+"0") = true, to zakończ z wynikiem true ; wywołanie rekurencyjne dla lewego syna
K06: Zakończ z wynikiem codeT(c,(pright),b+"1") ; wywołanie rekurencyjne dla prawego syna

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program jest przykładową aplikacją dydaktyczną, która wczytuje definicję kodu bezprzystankowego, tworzy na jej podstawie odpowiednie drzewo kodu, po czym wczytuje łańcuch z wiadomością zbudowaną ze znaków kodu. Znaki te zostają zakodowane zgodnie z definicją drzewa kodu, a wynik jest wyświetlany w oknie konsoli. Format danych wejściowych jest następujący:

 

Pierwsza liczba określa ilość słów kodowych n. Następnie występuje n wierszy typu znak, spacja, kod binarny. W ostatnim wierszu jest łańcuch z wiadomością do zakodowania.

 

Przykładowe dane wejściowe:

 

6
A 0
B 100
C 101
D 110
E 1110
F 1111
DECAFABEA
ree Pascal
// Kodowanie kodem bezprzystankowym
// Data: 27.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------

program pfcodes;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
type
  PTNode = ^TNode;
  TNode  = record
    left  : PTNode;
    right : PTNode;
    key   : char;
  end;

// Tworzy z danych wejściowych
// drzewo kodu bezprzystankowego
//------------------------------
procedure makeT(var root : PTNode);
var
  n,i,j : integer;
  s,x   : char;
  b     : string;
  p     : PTNode;
begin
  new(root);                    // Tworzymy węzeł startowy
  root^.left  := nil;           // Wypełniamy pola
  root^.right := nil;

  readln(n);                    // Odczytujemy liczbę definicji

  for i := 1 to n do            // W petli tworzymy drzewo
  begin
    readln(s,x,b);              // Czytamy znak, spację x i kod

    p := root;                  // Rozpoczynamy od korzenia

    for j := 1 to length(b) do  // Przetwarzamy kolejne bity kodu
      if b[j] = '0' then        // Czy bit = 0?
      begin
        if p^.left = nil then   // Czy istnieje lewy syn?
        begin
          new(p^.left);         // Jeśli nie, to go tworzymy
          p^.left^.left  := nil;
          p^.left^.right := nil;
        end;
        p := p^.left;           // Przechodzimy do lewego syna
      end
      else                      // To samo dla bit = 1
      begin
        if p^.right = nil then  // Czy istnieje prawy syn?
        begin
          new(p^.right);        // Jeśli nie, to go tworzymy
          p^.right^.left  := nil;
          p^.right^.right := nil;
        end;
        p := p^.right;          // Przechodzimy do prawego syna
      end;

    p^.key := s;                // Do liścia wstawiamy znak

  end;
end;

// Koduje wiadomość za pomocą kodu bezprzystankowego
//--------------------------------------------------
function codeT(c : char; p : PTNode; b : string) : boolean;
begin
  if p^.left = nil then
  begin
    if c <> p^.key then codeT := false
    else
    begin
      write(b);
      codeT := true;
    end;
  end
  else codeT := codeT(c,p^.left,b+'0') or codeT(c,p^.right,b+'1');
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  root : PTNode;            // Korzeń drzewa
  s    : string;            // Kodowana wiadomość
  i    : integer;
begin
  makeT(root);              // Tworzymy drzewo kodu bezprzystankowego

  readln(s);                // Odczytujemy wiadomość

  for i := 1 to length(s) do
    codeT(s[i],root,'');    // Kodujemy poszczególne znaki

  writeln;

  DFSRelease(root);         // Usuwamy drzewo z pamięci

end.
Code::Blocks
// Kodowanie kodem bezprzystankowym
// Data: 27.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------------

#include <iostream>
#include <string>

using namespace std;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
struct TNode
{
  TNode * left;
  TNode * right;
  char key;
};

// Tworzy z danych wejściowych
// drzewo kodu bezprzystankowego
//------------------------------
void makeT(TNode * & root)
{
  int n,i,j;
  char s;
  string b;
  TNode * p;

  root = new TNode;             // Tworzymy węzeł startowy
  root->left  = NULL;           // Wypełniamy pola
  root->right = NULL;

  cin >> n;                     // Odczytujemy liczbę definicji

  for(i = 0; i < n; i++)        // W pętli tworzymy drzewo
  {
    cin >> s >> b;              // Czytamy znak, spację x i kod

    p = root;                   // Rozpoczynamy od korzenia

    for(j = 0; j < (int)b.length(); j++)  // Przetwarzamy kolejne bity kodu
      if(b[j] == '0')                // Czy bit = 0?
      {
        if(!p->left)                 // Czy istnieje lewy syn?
        {
          p->left = new TNode;       // Jeśli nie, to go tworzymy
          p->left->left  = NULL;
          p->left->right = NULL;
        }
        p = p->left;                 // Przechodzimy do lewego syna
      }
      else                           // To samo dla bit = 1
      {
        if(!p->right)                // Czy istnieje prawy syn?
        {
          p->right = new TNode;      // Jeśli nie, to go tworzymy
          p->right->left  = NULL;
          p->right->right = NULL;
        }
        p = p->right;          // Przechodzimy do prawego syna
      }

    p->key = s;                // Do liścia wstawiamy znak

  }
}

// Koduje wiadomość za pomocą kodu bezprzystankowego
//--------------------------------------------------
bool codeT(char c, TNode * p, string b)
{
  if(!p->left)
  {
    if(c != p->key) return false;
    else
    {
      cout << b;
      return true;
    }
  }
  else return codeT(c,p->left,b+"0") || codeT(c,p->right,b+"1");
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(TNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  TNode * root;            // Korzeń drzewa
  string s;                // Kodowana wiadomość
  unsigned int i;

  makeT(root);             // Tworzymy drzewo kodu bezprzystankowego

  cin >> s;                // Odczytujemy wiadomość

  for(i = 0; i < s.length(); i++)
    codeT(s[i],root,"");   // Kodujemy poszczególne znaki

  cout << endl;

  DFSRelease(root);        // Usuwamy drzewo z pamięci

  return 0;
}
Free Basic
' Kodowanie kodem bezprzystankowym
' Data: 27.06.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------------

' Definicja węzła drzewa kodu bezprzystankowego
'----------------------------------------------
Type TNode
  left  As TNode Ptr
  right As TNode Ptr
  key   As String * 1
End Type

' Tworzy z danych wejściowych
' drzewo kodu bezprzystankowego
'------------------------------
Sub makeT(ByRef root As TNode Ptr)

  Dim As Integer n,i,j
  Dim As String * 1 s,x
  Dim As String b
  Dim As TNode Ptr p

  root = new TNode             ' Tworzymy węzeł startowy
  root->left  = 0              ' Wypełniamy pola
  root->right = 0

  Input #1, n                  ' Odczytujemy liczbę definicji

  For i = 1 To n               ' W pętli tworzymy drzewo
    s = Input(2,#1)            ' Czytamy znak i spację
    Input #1,b                 ' Czytamy kod
    
    p = root                   ' Rozpoczynamy od korzenia
    
    For j = 1 To Len(b)        ' Przetwarzamy kolejne bity kodu
      If Mid(b,j,1) = "0" Then ' Czy bit = 0?
        If p->Left = 0 Then    ' Czy istnieje lewy syn?
          p->left = new TNode  ' Jeśli nie, to go tworzymy
          p->left->left  = 0
          p->left->right = 0
        End If
        p = p->Left            ' Przechodzimy do lewego syna
      Else                     ' To samo dla bit = 1
        if p->Right = 0 Then   ' Czy istnieje prawy syn?
          p->right = new TNode ' Jeśli nie, to go tworzymy
          p->right->left  = 0
          p->right->right = 0
        End If
        p = p->Right           ' Przechodzimy do prawego syna
      End If
    Next
    
    p->key = s                 ' Do liścia wstawiamy znak
    
  Next
  
End Sub

' Koduje wiadomość za pomocą kodu bezprzystankowego
'--------------------------------------------------
Function codeT(c As String, p As TNode Ptr, b As String) As Integer

  If p->Left = 0 Then
    If c <> p->key Then
    	Return 0
    Else
      print b;
      return 1
    End If
  Else
    Return codeT(c,p->left,b+"0") OrElse codeT(c,p->right,b+"1")
  End If
End Function

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(ByVal v As TNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As TNode Ptr root   ' Korzeń drzewa
Dim As String s
Dim As Integer i

Open Cons For Input As #1

makeT(root)             ' Tworzymy drzewo kodu bezprzystankowego

Input #1,s              ' Odczytujemy wiadomość

For i = 1 To Len(s)     ' Kodujemy poszczególne znaki
  codeT(Mid(s,i,1),root,"")
Next

DFSRelease(root)        ' Usuwamy drzewo z pamięci

Close #1

End
Wynik
6
A 0
B 100
C 101
D 110
E 1110
F 1111
DECAFABEA
110111010101111010011100

 

Kodowanie Huffmana

Kodowanie Huffmana polega na przypisywaniu znakom występującym najczęściej w kodowanej wiadomości kodów krótkich. Znaki pojawiające się rzadziej otrzymują kody dłuższe. To zróżnicowanie długości pozwala otrzymać kod o mniejszej liczbie bitów, niż gdybyśmy stosowali kody o stałej długości. W rozdziale tym opiszemy algorytm tworzenia drzewa kodu bezprzystankowego Huffmana. Reszta operacji została opisana powyżej.

 

Załóżmy, że chcemy zakodować następującą wiadomość:

 

ACBECAHCADFEGAFAGACBBADAAFAAEAGACAFABEFBCCFA

 

Obliczamy ilość wystąpień każdego znaku:

 

A  –  16
B  –  5
C  –  7
D  –  2
E  –  4
F  –  6
G  –  3
H  –  1

 

Gdybyśmy zakodowali ten tekst kodem o stałej długości, to przy 8 znakach potrzebowalibyśmy dla każdego z nich kodów 3 bitowych. W sumie tekst ten zająłby:

 

3 • (16 + 5 + 7 + 2 + 4 + 6 + 3 + 1)  = 132 bity

 

Tworzymy listę węzłów drzewa kodu bezprzystankowego. Na liście umieszczamy kolejne węzły, które w docelowym drzewie będą liśćmi. Każdy węzeł przechowuje kodowany znak oraz częstość wystąpień tego znaku w kodowanym tekście. Lista jest uporządkowana wg rosnącej liczby wystąpień. Dla naszego tekstu pierwszy węzeł zawiera znak H, który w tekście pojawia się jeden raz. Ostatni węzeł zawiera znak A o największej liczbie wystąpień, równej 16.
Dopóki na liście jest więcej niż jeden element, będziemy powtarzać następującą operację:

Z listy pobieramy dwa pierwsze węzły. Węzły te zawsze zawierają znaki o najmniejszej liczbie wystąpień. U nas są to węzły H:1 i D:2.

Tworzymy nowy węzeł i dołączamy do niego dwa pobrane z listy węzły. W nowym węźle zapamiętujemy sumę wystąpień znaków w dwóch pobranych węzłach. Węzeł nie musi pamiętać żadnego znaku, ponieważ w drzewie kodu bezprzystankowego będzie on węzłem wewnętrznym. Tutaj stosujemy znak '?".
Utworzony węzeł dodajemy do listy tak, aby była wciąż uporządkowana rosnąco. Tutaj trafi na początek listy.
Powtarzamy powyżej opisane operacje dla dwóch pierwszych węzłów na liście:

Odłączamy je od listy.

Tworzymy nowy węzeł z sumą wystąpień odłączonych węzłów. Dołączamy do niego te dwa węzły.
Węzeł wstawiamy na listę.
Powtarzamy te same operacje dla węzłów E:4 i B:5. Odłączamy je od listy. Tworzymy nowy węzeł. Umieszczamy w nim sumę wystąpień znaków E i B.
Po czym węzeł ten dołączamy do listy, zachowując jej uporządkowanie.

Wykonujemy to samo dla pary węzłów ?:6 i F:6.

Nowy węzeł ?:12 wstawiamy na listę przed A:16.

To samo dla C:7 i ?:9.

Nowy węzeł ?:16 znów trafia przed A:16.

To samo dla ?:12 i ?:16.

Tym razem nowy węzeł ?:28 trafia za A:16.

Na liście zostały tylko dwa węzły, A:16 i ?:26. Po raz ostatni wykonujemy dla nich opisane operacje.

W ich wyniku na liście pozostaje jeden węzeł, który jest korzeniem drzewa kodu bezprzystankowego Huffmana.
Z drzewa możemy odczytać kody dla poszczególnych znaków:
A → 0
B → 1111
C → 110
D → 10001
E → 1110
F → 101
G → 1001
H → 10000

 

Kody Huffmana mają różną długość, jeśli w kodowanym tekście znaki różnią się częstością występowania – znak A ma najkrótszy kod, ponieważ występuje najczęściej. Nasza wiadomość zostanie zakodowana za pomocą następującej liczby bitów:

 

16 • 1 + 5 • 4 + 7 • 3 + 2 • 5 + 4 • 4 + 6 • 3 + 3 • 4 + 1 • 5 = 16 + 20 + 21 + 10 + 16 + 18 + 12 + 5 = 118 bitów zamiast 132 bitów przy kodzie o stałej długości. Współczynnik kompresji 89,39%.

 

Algorytm kodowania kodem bezprzystankowym Huffmana składa się z trzech etapów:

  1. Przetwarzamy tekst wejściowy. Wynikiem tego przetworzenia będzie lista węzłów drzewa kodu bezprzystankowego. Każdy węzeł przechowuje znak tekstu oraz jego liczbę wystąpień. Lista jest uporządkowana rosnąco względem liczb wystąpień znaków.
  2. Lista węzłów zostaje przetworzona na drzewo kodu bezprzystankowego.
  3. Wynikowe drzewo kodu bezprzystankowego zostaje wykorzystane do zakodowania tekstu wejściowego.

Pierwszy etap jest dosyć prosty. Tworzymy pustą listę. Przeglądamy kolejne znaki tekstu. Dla każdego znaku sprawdzamy, czy na liście znajduje się węzeł z takim znakiem. Jeśli tak, to zwiększamy liczbę wystąpień znaku, która jest przechowywana w węźle. Jeśli nie, to na początku listy dopisujemy nowy węzeł z przetwarzanym znakiem, w którym liczba wystąpień jest ustawiona na 1. Gdy przeglądniemy wszystkie znaki tekstu, otrzymamy listę węzłów ze znakami występującymi w tekście oraz z liczbą ich wystąpień. Listę sortujemy rosnąco względem liczb wystąpień znaków. W naszym algorytmie wykorzystujemy sortowanie bąbelkowe, lecz można tutaj zastosować dowolny inny algorytm sortujący. Jednakże dla małej liczby elementów sortowanie bąbelkowe jest całkiem efektywne.

Drugi i trzeci etap opisaliśmy powyżej.

Ponieważ węzeł Huffmana jest elementem listy oraz drzewa, to musi posiadać następujące pola:

 

Lazarus Code::Blocks Free Basic
type
  PHTNode = ^HTNode;
  HTNode  = record
    next  : PHTNode; 
    left  : PHTNode;
    right : PHTNode;
    ch    : char;
    count : integer;
  end;
struct HTNode
{
  HTNode * next;
  HTNode * left;
  HTNode * right;
  char ch;
  int count;
};
Type HTNode
  next  As HTNode Ptr
  left  As HTNode Ptr
  right As HTNode Ptr
  ch    As String * 1
  count As Integer
End Type

 

next  –  wskazuje następny element listy
left, right  –  wskazuje lewego, prawego syna
ch  –  kodowany znak
count  –  ilość wystąpień znaku w tekście

 

Algorytm tworzenia listy węzłów drzewa kodu bezprzystankowego dla algorytmu Huffmana

Wejście
s    łańcuch tekstu do zakodowania
root    wskazanie pustej listy jednokierunkowej
Wyjście:
root    adres pierwszego elementu listy wierzchołków drzewa kodu bezprzystankowego. Lista jest posortowana rosnąco względem pól count.
Elementy pomocnicze:
i    licznik znaków
p    wskaźnik węzła
t    test uporządkowania listy
Lista kroków:
K01: rootnil ; rozpoczynamy z pustą listą. Zmienna root wskazuje zawsze jej początek.
K02: Dla i = 0,1,..., |s| - 1, wykonuj K03...K14 ; w pętli zliczamy znaki tekstu
K03:     proot  
K04:     Dopóki (p nil) ((pch) ≠ s[i]) wykonuj:
        p ← (pnext)
; szukamy znaku w węzłach na liście 
K05:     Jeśli pnil, to idź do K14  
K06:     Utwórz nowy węzeł ; jeśli na liście nie ma węzła ze znakiem, to taki węzeł tworzymy
K07:     p ← adres nowego węzła  
K08:     (pnext) ← root ; ustawiamy pola węzła, będzie on pierwszym elementem listy
K09:     (pleft) ← nil ; węzeł nie posiada synów
K10:     (pright) ← nil  
K11:     (pch) ← s[i] ; zapamiętujemy w węźle przetwarzany znak
K12:     (pcount) ← 0 ; liczba wystąpień początkowo równa
K13:     rootp ; węzeł staje się pierwszym elementem listy
K14:     (pcount) ← (pcount) + 1 ; zwiększamy o 1 liczbę wystąpień znaku
K15: t ← true ; zakładamy, że lista jest uporządkowana
K16: proot ; p wskazuje pierwszy element
K17: Dopóki (pnext) ≠ nil wykonuj K18...K22  
K18:     Jeśli (pcount) ≤ (pnextcount), to idź do K22 ; sortujemy bąbelkowo
K19:     (pch) ↔ (pnextch) ; wymieniamy ze sobą zawartości węzłów (tylko pola ch i count)
K20:     (pcount) ↔ (pnextcount)  
K21:     t ← false ; zaznaczamy, że lista nie była uporządkowana
K22     p ← (pnext) ; przesuwamy się na kolejne dwa elementy listy
K23: Jeśli t = false, to idź do K15 ; jeśli lista nie była posortowana, to kolejny obieg sortujący
K24: Zakończ  

 

Algorytm tworzenia drzewa kodu Huffmana

Wejście
root    lista wierzchołków kodu bezprzystankowego uporządkowana rosnąco względem pól count
Wyjście:
root    drzewo kodu bezprzystankowego Huffmana
Elementy pomocnicze:
p,r,v1,v2    wskazania węzłów
Lista kroków:
K01: v1root ; pobieramy z listy dwa węzły
K02: v2 ← (v1next)  
K03: Jeśli v2 = nil, to zakończ ; na liście tylko jeden węzeł, kończymy
K04: root ← (v2next) ; nowy początek listy za pobranymi węzłami
K05: Utwórz nowy węzeł  
K06: p ← adres nowego węzła  
K07: (pleft) ← v1 ; pobrane węzły stają się synami nowego węzła
K08: (pright) ← v2  
K09: (pcount) ← (v1count) + (v2count) ; wyliczamy nową częstość
K10: Jeśli (root = nil) ((pcount) ≤ (rootcount)), to
    (p→next) ← root;
    root
p
    Idź do K01
; węzeł wstawiamy z powrotem na listę
K11: rroot ; szukamy na liście miejsca dla węzła p
K12: Dopóki ((rnext) ≠ nil) ((pcount) > (rnextcount)), wykonuj
    r ← (rnext)
 
K13: (pnext) ← (rnext) ; węzeł p wstawiamy za węzłem wskazywanym przez r
K14: (rnext) ← p  
K15: Idź do K01  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program jest przykładową aplikacją dydaktyczną, która demonstruje zastosowanie kodowania Huffmana do kompresji danych tekstowych. Na wejściu należy podać dowolny łańcuch tekstowy zbudowany z przynajmniej dwóch różnych znaków. Następnie program utworzy kod bezprzystankowy Huffmana dla każdego znaku w łańcuchu i zakoduje łańcuch tym kodem. Na wyjściu otrzymujemy kody dla poszczególnych znaków oraz zakodowany tym kodem łańcuch wejściowy.

 

Lazarus
// Kodowanie Huffmana
// Data: 5.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program Huffman;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
type
  PHTNode = ^HTNode;
  HTNode  = record
    next  : PHTNode;     // Pole dla listy
    left  : PHTNode;     // Pola dla drzewa
    right : PHTNode;
    ch    : char;
    count : integer;
  end;

// Tworzy listę wierzchołków
//--------------------------
procedure MakeList(var root : PHTNode; s : string);
var
  i,x : integer;
  cx  : char;
  p   : PHTNode;
  t   : boolean;
begin
  root := nil;                     // Tworzymy pustą listę
  for i := 1 to length(s) do       // Tworzymy węzły i zliczamy znaki
  begin
    p := root;                     // Szukamy na liście znaku s[i]
    while (p <> nil) and (p^.ch <> s[i]) do p := p^.next;
    if p = nil then                // Jeśli go nie ma, to
    begin
      new(p);                      // tworzymy dla niego nowy węzeł
      p^.next  := root;            // Węzeł trafi na początek listy
      p^.left  := nil;             // Ustawiamy pola węzła
      p^.right := nil;
      p^.ch    := s[i];
      p^.count := 0;
      root     := p;               // Wstawiamy węzeł na początek listy
    end;
    inc(p^.count);                 // Zwiększamy licznik wystąpień znaku
  end;
  repeat                           // Listę sortujemy rosnąco względem count
    t := true;                     // Zakładamy posortowanie listy
    p := root;                     // Sortujemy od pierwszego elementu
    while p^.next <> nil do
    begin
      if p^.count > p^.next^.count then
      begin
        cx := p^.ch;               // Wymieniamy zawartość dwóch kolejnych elementów
        p^.ch := p^.next^.ch;
        p^.next^.ch := cx;
        x := p^.count;
        p^.count := p^.next^.count;
        p^.next^.count := x;
        t := false;                // Sygnalizujemy nieposortowanie listy
      end;
      p := p^.next;                // Przechodzimy do następnego elementu
    end;
  until t;
end;

// Tworzy z listy drzewo Huffmana
//-------------------------------
procedure MakeTree(var root : PHTNode);
var
  p,r,v1,v2 : PHTNode;
begin
  while true do
  begin
    v1 := root;                    // Pobieramy z listy dwa pierwsze węzły
    v2 := v1^.next;

    if v2 = nil then break;        // Jeśli tylko jeden element, zakończ

    root := v2^.next;              // Lista bez v1 i v2

    new(p);                        // Tworzymy nowy węzeł
    p^.left := v1;                 // Dołączamy do niego v1 i v2
    p^.right := v2;                // i wyliczamy nową częstość
    p^.count := v1^.count + v2^.count;

    // Węzeł wstawiamy z powrotem na listę tak, aby była uporządkowana

    if (root = nil) or (p^.count <= root^.count) then
    begin
      p^.next := root;
      root := p;
      continue;
    end;

    r := root;

    while (r^.next <> nil) and (p^.count > r^.next^.count) do r := r^.next;

    p^.next := r^.next;
    r^.next := p;
  end;
end;

// Drukuje zawartość drzewa Huffmana
//----------------------------------
procedure PrintTree(p : PHTNode; b : string);
begin
  if p^.left = nil then writeln(p^.ch,' ',b)
  else
  begin
    PrintTree(p^.left, b + '0');
    PrintTree(p^.right,b + '1');
  end;
end;

// Koduje znak
//------------
function codeT(c : char; p : PHTNode; b : string) : boolean;
begin
  if p^.left = nil then
  begin
    if c <> p^.ch then codeT := false
    else
    begin
      write(b);
      codeT := true;
    end;
  end
  else codeT := codeT(c,p^.left,b+'0') or codeT(c,p^.right,b+'1');
end;

// Koduje tekst kodem Huffmana
//----------------------------
procedure CodeHuffman(root : PHTNode;s : string);
var
  i : integer;
begin
  for i := 1 to length(s) do      // Kodujemy poszczególne znaki
    CodeT(s[i],root,'');

end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PHTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end
end;

// **********************
// *** Program główny ***
// **********************

var
  root : PHTNode;       // Początek listy / korzeń drzewa
  s : string;           // Przetwarzany łańcuch

begin
  readln(s);            // Czytamy łańcuch wejściowy

  MakeList(root,s);     // Tworzymy listę wierzchołków
  MakeTree(root);       // Tworzymy drzewo kodu Huffmana
  PrintTree(root,'');   // Wyświetlamy kody znaków
  CodeHuffman(root,s);  // Kodujemy i wyświetlamy wynik

  DFSRelease(root);     // Usuwamy drzewo z pamięci

  writeln;
  writeln;
end.
Code::Blocks
// Kodowanie Huffmana
// Data: 5.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>

using namespace std;

// Definicja węzła drzewa kodu bezprzystankowego
//----------------------------------------------
struct HTNode
{
  HTNode * next;
  HTNode * left;
  HTNode * right;
  char ch;
  int count;
};

// Tworzy listę wierzchołków
//--------------------------
void MakeList(HTNode * & root, string s)
{
  unsigned int i,x;
  char cx;
  HTNode * p;
  bool t;

  root = NULL;                    // Tworzymy pustą listę
  for(i = 0; i < s.length(); i++) // Tworzymy węzły i zliczamy znaki
  {
    p = root;                     // Szukamy na liście znaku s[i]
    while (p && (p->ch != s[i])) p = p->next;
    if(!p)                        // Jeśli go nie ma, to
    {
      p = new HTNode;             // tworzymy dla niego nowy węzeł
      p->next  = root;            // Węzeł trafi na początek listy
      p->left  = NULL;            // Ustawiamy pola węzła
      p->right = NULL;
      p->ch    = s[i];
      p->count = 0;
      root     = p;               // Wstawiamy węzeł na początek listy
    }
    p->count++;                   // Zwiększamy licznik wystąpień znaku
  }
  do                              // Listę sortujemy rosnąco względem count
  {
    t = true;                     // Zakładamy posortowanie listy
    p = root;                     // Sortujemy od pierwszego elementu
    while(p->next)
    {
      if(p->count > p->next->count)
      {
        cx = p->ch;               // Wymieniamy zawartość dwóch kolejnych elementów
        p->ch = p->next->ch;
        p->next->ch = cx;
        x = p->count;
        p->count = p->next->count;
        p->next->count = x;
        t = false;                // Sygnalizujemy nieposortowanie listy
      }
      p = p->next;                // Przechodzimy do następnego elementu
    }
  } while(!t);
}

// Tworzy z listy drzewo Huffmana
//-------------------------------
void MakeTree(HTNode * & root)
{
  HTNode *p, *r, *v1, *v2;

  while(true)
  {
    v1 = root;                    // Pobieramy z listy dwa pierwsze węzły
    v2 = v1->next;

    if(!v2) break;                // Jeśli tylko jeden element, zakończ

    root = v2->next;              // Lista bez v1 i v2

    p = new HTNode;               // Tworzymy nowy węzeł
    p->left = v1;                 // Dołączamy do niego v1 i v2
    p->right = v2;                // i wyliczamy nową częstość
    p->count = v1->count + v2->count;

    // Węzeł wstawiamy z powrotem na listę tak, aby była uporządkowana

    if(!root || (p->count <= root->count))
    {
      p->next = root;
      root = p;
      continue;
    }

    r = root;

    while (r->next && (p->count > r->next->count)) r = r->next;

    p->next = r->next;
    r->next = p;
  }
}

// Drukuje zawartość drzewa Huffmana
//----------------------------------
void PrintTree(HTNode * p, string b)
{
  if(!p->left) cout << p->ch << " " << b << endl;
  else
  {
    PrintTree(p->left, b + "0");
    PrintTree(p->right,b + "1");
  }
}

// Koduje znak
//------------
bool CodeT(char c, HTNode * p, string b)
{
  if(!p->left)
  {
    if(c != p->ch) return false;
    else
    {
      cout << b;
      return true;
    }
  }
  else return CodeT(c,p->left,b+"0") || CodeT(c,p->right,b+"1");
}

// Koduje tekst kodem Huffmana
//----------------------------
void CodeHuffman(HTNode * root, string s)
{
  unsigned int i;

  for(i = 0; i < s.length(); i++)  // Kodujemy poszczególne znaki
    CodeT(s[i],root,"");
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(HTNode * v)
{
  if(v)
  {
    DFSRelease(v->left);          // usuwamy lewe poddrzewo
    DFSRelease(v->right);         // usuwamy prawe poddrzewo
    delete v;                     // usuwamy sam węzeł
  }
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  HTNode * root;                  // Początek listy / korzeń drzewa
  string s;                       // Przetwarzany łańcuch

  getline(cin,s);                 // Czytamy łańcuch wejściowy

  MakeList(root,s);               // Tworzymy listę wierzchołków
  MakeTree(root);                 // Tworzymy drzewo kodu Huffmana
  PrintTree(root,"");             // Wyświetlamy kody znaków
  CodeHuffman(root,s);            // Kodujemy i wyświetlamy wynik

  DFSRelease(root);               // Usuwamy drzewo z pamięci

  cout << endl << endl;

  return 0;
}
Free Basic
' Kodowanie Huffmana
' Data: 5.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Definicja węzła drzewa kodu bezprzystankowego
'----------------------------------------------
Type HTNode
  next  As HTNode Ptr
  left  As HTNode Ptr
  right As HTNode Ptr
  ch    As String * 1
  count As Integer
End Type

' Tworzy listę wierzchołków
'--------------------------
Sub MakeList(ByRef root As HTNode Ptr, s As String)

  Dim As Integer i,x,t
  Dim As string cx
  Dim As HTNode Ptr p

  root = 0                        ' Tworzymy pustą listę
  For i = 1 To Len(s)             ' Tworzymy węzły i zliczamy znaki
    p = root                      ' Szukamy na liście znaku s[i]
    while (p <> 0) AndAlso (p->ch <> Mid(s,i,1)): p = p->Next: Wend
    If p = 0 Then                 ' Jeśli go nie ma, to
      p = new HTNode              ' tworzymy dla niego nowy węzeł
      p->next  = root             ' Węzeł trafi na początek listy
      p->left  = 0                ' Ustawiamy pola węzła
      p->right = 0
      p->ch    = Mid(s,i,1)
      p->count = 0
      root     = p                ' Wstawiamy węzeł na początek listy
    End If
    p->count += 1                 ' Zwiększamy licznik wystąpień znaku
  Next
  do                              ' Listę sortujemy rosnąco względem count
    t = 1                         ' Zakładamy posortowanie listy
    p = root                      ' Sortujemy od pierwszego elementu
    While p->Next
      If p->count > p->next->count Then
        cx = p->ch                ' Wymieniamy zawartość dwóch kolejnych elementów
        p->ch = p->next->ch
        p->next->ch = cx
        x = p->count
        p->count = p->next->count
        p->next->count = x
        t = 0                     ' Sygnalizujemy nieposortowanie listy
      End If
      p = p->Next                 ' Przechodzimy do następnego elementu
    Wend
  loop Until t = 1
End Sub

' Tworzy z listy drzewo Huffmana
'-------------------------------
sub MakeTree(ByRef root As HTNode Ptr)

  Dim As HTNode Ptr p,r,v1,v2

  While 1
    v1 = root                    ' Pobieramy z listy dwa pierwsze węzły
    v2 = v1->Next

    If v2 = 0 Then Exit While    ' Jeśli tylko jeden element, zakończ

    root = v2->Next              ' Lista bez v1 i v2

    p = new HTNode               ' Tworzymy nowy węzeł
    p->left = v1                 ' Dołączamy do niego v1 i v2
    p->right = v2                ' i wyliczamy nową częstość
    p->count = v1->count + v2->count

    ' Węzeł wstawiamy z powrotem na listę tak, aby była uporządkowana

    If (root = 0) OrElse (p->count <= root->count) Then
      p->next = root
      root = p
      Continue While
    End If

    r = root

    while (r->Next <> 0) AndAlso (p->count > r->next->count): r = r->Next: Wend

    p->next = r->Next
    r->next = p
  Wend
End sub

' Drukuje zawartość drzewa Huffmana
'----------------------------------
sub PrintTree(p As HTNode Ptr, b As String)
  If p->Left = 0 Then
    Print p->ch ;" ";b
  Else
    PrintTree(p->left, b + "0")
    PrintTree(p->right,b + "1")
  End If
End Sub

' Koduje znak
'------------
Function codeT(c As String, p As HTNode Ptr, b As String) As Integer

  If p->Left = 0 Then
    If c <> p->ch Then
    	Return 0
    Else
      print b;
      return 1
    End If
  Else
    Return CodeT(c,p->left,b+"0") OrElse codeT(c,p->right,b+"1")
  End If
End Function

' Koduje tekst kodem Huffmana
'----------------------------
sub CodeHuffman(root As HTNode Ptr, s As String)
  Dim As Integer i

  For i = 1 To Len(s)             ' Kodujemy poszczególne znaki
    CodeT(Mid(s,i,1),root,"")
  Next
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(ByVal v As HTNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' **********************
' *** Program główny ***
' **********************


Dim root as HTNode Ptr           ' Początek listy / korzeń drzewa
Dim s As String                  ' Przetwarzany łańcuch

Line Input s                     ' Czytamy łańcuch wejściowy

MakeList(root,s)                 ' Tworzymy listę wierzchołków
MakeTree(root)                   ' Tworzymy drzewo kodu Huffmana
PrintTree(root,"")               ' Wyświetlamy kody znaków
CodeHuffman(root,s)              ' Kodujemy i wyświetlamy wynik

DFSRelease(root)                 ' Usuwamy drzewo z pamięci

Print
Print

End
Wynik
ACBECAHCADFEGAFAGACBBADAAFAAEAGACAFABEFBCCFA
A 0
H 10000
D 10001
G 1001
F 101
C 110
E 1110
B 1111
01101111111011001000011001000110111101001010101001011011111111010001001010011100
10010110010101111111010111111101101010

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 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