Algorytmy i Struktury Danych - Kompresja Huffmana

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 → 00

Dostałeś ciąg bitów:

0000000…

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).

Pascal

type
  PTnode = ^Tnode;
  Tnode  = record
    left  : PTnode;
    right : PTnode;
    key   : char;
  end;

C++

struct Tnode
{
  Tnode * left;
  Tnode * right;
  char key;
};

Basic

Type Tnode
  left  As Tnode Ptr
  right As Tnode Ptr
  key   As String * 1
End Type

Python (dodatek)

class Tnode:


    def __init__(self, k):
        self.left  = None
        self.right = None
        self.key   = k

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 par znak:kod.
s : kodowany znak.
b : łańcuch z kodem binarnym znaku.
root : zmienna przechowująca adres korzenia drzewa. Drzewo powinno zawierać jeden węzeł startowy.
W strumieniu wejściowym powinno się znaleźć n par: znak i ciąg reprezentujących go bitów.

Wyjście:

root : wskazuje drzewo kodu bezprzystankowego.

Elementy pomocnicze:

p : wskaźnik węzła.
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 kroki K02…K19
K02:   Czytaj s, b ; odczytujemy znak oraz jego kod
                  ; ze strumienia wejściowego
K03:   p ← root ; ustawiamy węzeł bieżący na węzeł startowy
K04:   Dla j = 0, 1, …, |b|-1: ; przetwarzamy kolejne "bity" kodu
       wykonuj kroki K05…K18
K05:     Jeśli b[j] = "1", ; przetwarzamy "bit" 0
         to idź do kroku K13
K06:     Jeśli p→left ≠ nil, ; sprawdzamy, czy bieżący węzeł
         to idź do kroku K11   ; ma lewego syna
K07:     Utwórz nowy węzeł ; jeśli nie, to go tworzymy
K08:     p→left ← adres nowego węzła
K09:     p→left→left ← nil ; ustawiamy pola nowego węzła
K10:     p→left→right ← nil
K11:     p ← p→left ; przechodzimy do lewego syna
K12:     Następny obieg pętli K04 ; i kontynuujemy pętlę
K13:     Jeśli p→right ≠ nil, ; to samo dla "bitu" 1
         to idź do kroku K18
K14:     Utwórz nowy węzeł
K15:     p→right ← adres nowego węzła
K16:     p→right→left ← nil
K17:     p→right→right ← nil
K18:     p ← p→right
K19:   p→key ← 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 z powrotem 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.
b : łańcuch znaków 0 i 1 tworzący zakodowaną wiadomość w kodzie bezprzystankowym.
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.
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: p ← root ; ustawiamy wskaźnik
              ; na węzeł startowy drzewa
K03: Dla i = 0, 1, …, |b|-1:  ; w pętli przetwarzamy
     wykonuj kroki K04…K07 ; kolejne "bity"
K04:   Jeśli b[i] = "0", ; przechodzimy wzdłuż
       to p ← p→left   ; odpowiedniej krawędzi
       Inaczej p ← p→right
K05:   Jeśli p→left ≠ nil,       ; sprawdzamy, czy
       to następny obieg pętli K03 ; osiągnęliśmy liść
K06:   Pisz p→key ; jeśli tak, piszemy znak z węzła
K07:   p ← root ; wracamy na początek drzewa
K08: Zakończ

Przykładowe programy

Uwaga:

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ą.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// 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
// R - wskazanie korzenia
//------------------------------
procedure make_t(var R : PTnode);
var
  n, i, j : integer;
  s, x   : char;
  b     : string;
  p     : PTnode;
begin
  // Tworzymy węzeł startowy
  new(R);
  // Wypełniamy pola
  R^.left  := nil;
  R^.right := nil;
  // Odczytujemy liczbę definicji
  readln(n);
  // W pętli tworzymy drzewo
  for i := 1 to n do
  begin
    // Czytamy znak, spację x i kod
    readln(s, x, b);
    // Rozpoczynamy od korzenia
    p := R;
    // Przetwarzamy kolejne bity kodu
    for j := 1 to length(b) do
      // Czy bit = 0?
      if b[j] = '0' then
      begin
        // Czy istnieje lewy syn?
        if p^.left = nil then
        begin
          // Jeśli nie, to go tworzymy
          new(p^.left);
          p^.left^.left  := nil;
          p^.left^.right := nil;
        end;
        // Przechodzimy do lewego syna
        p := p^.left;
      end
      else
      // To samo dla bit = 1
      begin
         // Czy istnieje prawy syn?
        if p^.right = nil then
        begin
          // Jeśli nie, to go tworzymy
          new(p^.right);
          p^.right^.left  := nil;
          p^.right^.right := nil;
        end;
        // Przechodzimy do prawego syna
        p := p^.right;
      end;
      // Do liścia wstawiamy znak
      p^.key := s;
  end;
end;

// Dekoduje wiadomość
// w kodzie bezprzystankowym
// R - korzeń
//--------------------------
procedure decode_t(R : PTnode);
var
  p : PTnode;
  b : string;
  i : integer;
begin
  // Odczytujemy kod
  readln(b);
  writeln;
  // Bieżący węzeł ustawiamy
  // na początek drzewa
  p := R;
  // Przetwarzamy kolejne bity kodu
  for i := 1 to length(b) do
  begin
    if b[i] = '0' then
      p := p^.left
    else
      p := p^.right;
    if p^.left = nil then
    begin
      write(p^.key);
      p := R;
    end;
  end;
  writeln;
end;

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

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

var
  // Korzeń drzewa
  root : PTnode;
begin
  // Inicjujemy korzeń
  root := nil;
  // Tworzymy drzewo
  // kodu bezprzystankowego
  make_t(root);
  // Dekodujemy wiadomość
  decode_t(root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
end.

C++

// 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 make_t(Tnode * & root)
{
  int n, i, j;
  char s;
  string b;
  Tnode * p;

  // Tworzymy węzeł startowy
  root = new Tnode;
  // Wypełniamy pola
  root->left  = NULL;
  root->right = NULL;
  // Odczytujemy liczbę definicji
  cin >> n;
  // W pętli tworzymy drzewo
  for(i = 0; i < n; i++)
  {
    // Czytamy znak i kod
    cin >> s >> b;
    // Rozpoczynamy od korzenia
    p = root;
    // Przetwarzamy kolejne bity kodu
    for(j = 0; j < int(b.length()); j++)
      // Czy bit = 0?
      if(b [j] == '0')
      {
        // Czy istnieje lewy syn?
        if(!p->left)
        {
           // Jeśli nie, to go tworzymy
          p->left = new Tnode;
          p->left->left  = NULL;
          p->left->right = NULL;
        }
        // Przechodzimy do lewego syna
        p = p->left;
      }
      else
      // To samo dla bit = 1
      {
        // Czy istnieje prawy syn?
        if(!p->right)
        {
          // Jeśli nie, to go tworzymy
          p->right = new Tnode;
          p->right->left  = NULL;
          p->right->right = NULL;
        }
        // Przechodzimy do prawego syna
        p = p->right;
      }
    // Do liścia wstawiamy znak
    p->key = s;
  }
}

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

  // Odczytujemy kod
  cin >> b;
  cout << endl;
  // Bieżący węzeł ustawiamy
  // na początek drzewa
  p = root;
  // Przetwarzamy kolejne bity kodu
  for(i = 0; i < int(b.length()); i++)
  {
    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 dfs_release(Tnode * v)
{
  if(v)
  {
    // usuwamy lewe poddrzewo
    dfs_release(v->left);
    // usuwamy prawe poddrzewo
    dfs_release(v->right);
    // usuwamy sam węzeł
    delete v;
  }
}

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

int main()
{
  // Korzeń drzewa
  Tnode * root;
  // Tworzymy drzewo kodu bezprzystankowego
  make_t(root);
  // Dekodujemy wiadomość
  decode_t(root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
  return 0;
}

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 make_t(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

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

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

  ' Odczytujemy kod
  Input #1, b
  Print
  ' Bieżący węzeł ustawiamy
  ' na początek drzewa
  p = root
  ' Przetwarzamy kolejne bity kodu
  For i = 1 To Len(b)
    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 dfs_release (ByVal v As Tnode Ptr)
  If v Then
    ' usuwamy lewe poddrzewo
    dfs_release(v->left)
    ' usuwamy prawe poddrzewo
    dfs_release(v->right)
    ' usuwamy sam węzeł
    delete v
  End If
End Sub

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

' Korzeń drzewa
Dim As Tnode Ptr root

Open Cons For Input As #1
' Tworzymy drzewo kodu bezprzystankowego
make_t(root)
' Dekodujemy wiadomość
decode_t(root)
' Usuwamy drzewo z pamięci
dfs_release(root)
Close #1
End

Python (dodatek)

# Kody bezprzystankowe
# Data: 9.08.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------


# Klasa węzła
# drzewa kodu bezprzystankowego
class Tnode:


    def __init__(self, k):
        self.left  = None
        self.right = None
        self.key   = k


# Tworzy z danych wejściowych
# drzewo kodu bezprzystankowego
# r - korzeń
def make_t():
    # Tworzymy pusty węzeł startowy
    r = Tnode('')
    # Odczytujemy liczbę definicji
    n = int(input())
    # W pętli tworzymy drzewo
    for i in range(n):
        # Czytamy znak kod
        arr = input().split()
        s = arr[0]
        b = arr[1]
        # Rozpoczynamy od korzenia
        p = r
        # Przetwarzamy kolejne bity kodu
        for j in b:
            # Czy bit = 0?
            if j == "0":
                # Czy istnieje lewy syn?
                if not p.left:
                    # Jeśli nie, to go tworzymy
                    p.left = Tnode('')
                # Przechodzimy do lewego syna
                p = p.left
            else:
                # To samo dla bit = 1
                # Czy istnieje prawy syn?
                if not p.right:
                    # Jeśli nie, to go tworzymy
                    p.right = Tnode('')
                # Przechodzimy do prawego syna
                p = p.right
        # Do liścia wstawiamy znak
        p.key = s
    return r


# Dekoduje wiadomość
# w kodzie bezprzystankowym
# r - korzeń drzewa
def decode_t(r):
    # Odczytujemy kod
    b = input()
    print()
    # Bieżący węzeł ustawiamy
    # na początek drzewa
    p = r
    # Przetwarzamy kolejne bity kodu
    for i in b:
        if i == "0":
            p = p.left
        else:
            p = p.right
        if not p.left:
            print(p.key, end="")
            p = r
    print()


# Procedura DFS:postorder
# usuwająca drzewo
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # zerujemy odwołania
        v.left  = None
        v.right = None


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Tworzymy drzewo
# kodu bezprzystankowego
root = make_t()
# Dekodujemy wiadomość
decode_t(root)
# Usuwamy drzewo z pamięci
dfs_release(root)

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 na przykład wykorzystać 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 code_t(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 code_t() 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 p→left ≠ nil, ; sprawdzamy, czy węzeł p jest liściem
     to idź do kroku K05
K02: Jeśli c ≠ p→key, ; sprawdzamy, czy węzeł przechowuje kodowany znak
     to zakończ z wynikiem false
K03: Pisz b ; jeśli tak, to na wyjście wyprowadzamy kod
K04: Zakończ z wynikiem true
K05: Jeśli code_t(c, p→left, b+"0") = true, ; wywołanie rekurencyjne dla lewego syna
     to zakończ z wynikiem true
K06: Zakończ z wynikiem code_t(c, p→right, b+"1") ; wywołanie rekurencyjne dla prawego syna

Przykładowe programy

Uwaga:

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.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

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 make_t(var root : PTnode);
var
  n, i, j : integer;
  s, x   : char;
  b     : string;
  p     : PTnode;
begin
  // Tworzymy węzeł startowy
  new(root);
  // Wypełniamy pola
  root^.left  := nil;
  root^.right := nil;
  // Odczytujemy liczbę definicji
  readln(n);
  // W pętli tworzymy drzewo
  for i := 1 to n do
  begin
    // Czytamy znak, spację x i kod
    readln(s, x, b);
    // Rozpoczynamy od korzenia
    p := root;
    // Przetwarzamy kolejne bity kodu
    for j := 1 to length(b) do
      // Czy bit = 0?
      if b[j] = '0' then
      begin
        // Czy istnieje lewy syn?
        if p^.left = nil then
        begin
          // Jeśli nie, to go tworzymy
          new(p^.left);
          p^.left^.left  := nil;
          p^.left^.right := nil;
        end;
        // Przechodzimy do lewego syna
        p := p^.left;
      end
      else
      // To samo dla bit = 1
      begin
        // Czy istnieje prawy syn?
        if p^.right = nil then
        begin
          // Jeśli nie, to go tworzymy
          new (p^.right);
          p^.right^.left  := nil;
          p^.right^.right := nil;
        end;
        // Przechodzimy do prawego syna
        p := p^.right;
      end;
    // Do liścia wstawiamy znak
    p^.key := s;
  end;
end;

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

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

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

var
  // Korzeń drzewa
  root : PTnode;
  // Kodowana wiadomość
  s : string;
  i : integer;

begin
  root := nil;
  // Tworzymy drzewo
  // kodu bezprzystankowego
  make_t(root);
  // Odczytujemy wiadomość
  readln(s);
  for i := 1 to length(s) do
    // Kodujemy poszczególne znaki
    code_t(s[i], root, '');
  writeln;
  // Usuwamy drzewo z pamięci
  dfs_release(root);
end.

C++

// 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 make_t(Tnode * & root)
{
  int n, i, j;
  char s;
  string b;
  Tnode * p;

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

  // Odczytujemy liczbę definicji
  cin >> n;
  // W pętli tworzymy drzewo
  for(i = 0; i < n; i++)
  {
    // Czytamy znak, spację x i kod
    cin >> s >> b;
    // Rozpoczynamy od korzenia
    p = root;
    // Przetwarzamy kolejne bity kodu
    for(j = 0; j < (int)b.length(); j++)
      // Czy bit = 0?
      if(b[j] == '0')
      {
        // Czy istnieje lewy syn?
        if(!p->left)
        {
          // Jeśli nie, to go tworzymy
          p->left = new Tnode;
          p->left->left  = NULL;
          p->left->right = NULL;
        }
        // Przechodzimy do lewego syna
        p = p->left;
      }
      else
      // To samo dla bit = 1
      {
        // Czy istnieje prawy syn?
        if(!p->right)
        {
          // Jeśli nie, to go tworzymy
          p->right = new Tnode;
          p->right->left  = NULL;
          p->right->right = NULL;
        }
        // Przechodzimy do prawego syna
        p = p->right;
      }
    // Do liścia wstawiamy znak
    p->key = s;
  }
}

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

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

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

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

  // Tworzymy drzewo
  // kodu bezprzystankowego
  make_t(root);
  // Odczytujemy wiadomość
  cin >> s;
  // Kodujemy poszczególne znaki
  for(i = 0; i < s.length(); i++)
    code_t(s[i], root, "");
  cout << endl;
  // Usuwamy drzewo z pamięci
  dfs_release(root);
  return 0;
}

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 make_t(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

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

' Koduje wiadomość za pomocą
' kodu bezprzystankowego
'---------------------------
Function code_t(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 code_t(c, p->left, b+"0") OrElse _
           code_t(c, p->right, b+"1")
  End If
End Function

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

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

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

Open Cons For Input As #1
' Tworzymy drzewo
' kodu bezprzystankowego
make_t(root)
' Odczytujemy wiadomość
Input #1, s
' Kodujemy poszczególne znaki
For i = 1 To Len(s)
  code_t(Mid(s, i, 1), root, "")
Next
' Usuwamy drzewo z pamięci
dfs_release(root)
Close #1
End

Python (dodatek)

# Kodowanie kodem bezprzystankowym
# Data: 10.08.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------


# Klasa węzła drzewa
# kodu bezprzystankowego
class Tnode:


    def __init__(self, k):
        self.left  = None
        self.right = None
        self.key   = k


# Tworzy z danych wejściowych
# drzewo kodu bezprzystankowego
# r - korzeń
def make_t():
    # Tworzymy pusty węzeł startowy
    r = Tnode('')
    # Odczytujemy liczbę definicji
    n = int(input())
    # W pętli tworzymy drzewo
    for i in range(n):
        # Czytamy znak kod
        arr = input().split()
        s = arr[0]
        b = arr[1]
        # Rozpoczynamy od korzenia
        p = r
        # Przetwarzamy kolejne bity kodu
        for j in b:
            # Czy bit = 0?
            if j == "0":
                # Czy istnieje lewy syn?
                if not p.left:
                    # Jeśli nie, to go tworzymy
                    p.left = Tnode('')
                # Przechodzimy do lewego syna
                p = p.left
            else:
                # To samo dla bit = 1
                # Czy istnieje prawy syn?
                if not p.right:
                    # Jeśli nie, to go tworzymy
                    p.right = Tnode('')
                # Przechodzimy do prawego syna
                p = p.right
        # Do liścia wstawiamy znak
        p.key = s
    return r


# Koduje wiadomość za pomocą
# kodu bezprzystankowego
def code_t(c, p, b):
    if not p.left:
        if c != p.key:
            return 0
        else:
            print(b, end="")
            return 1
    else:
        return code_t(c, p.left, b+"0") or \
               code_t(c, p.right, b+"1")


# Procedura DFS:postorder
# usuwająca drzewo
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # zerrujemy odwołania
        v.left  = None
        v.right = None


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Tworzymy drzewo
# kodu bezprzystankowego
root = make_t()
# Odczytujemy wiadomość
s = input()
# Kodujemy poszczególne znaki
for i in s:
    code_t(i, root, "")
# Usuwamy drzewo z pamięci
dfs_release(root)

Wynik:

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

do podrozdziału do strony

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:

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.
Lista węzłów zostaje przetworzona na drzewo kodu bezprzystankowego.
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:

Pascal

type
  PHTnode = ^HTnode;
  HTnode  = record
    next  : PHTnode;
    left  : PHTnode;
    right : PHTnode;
    ch    : char;
    count : integer;
  end;

C++

struct HTnode
{
  HTnode * next;
  HTnode * left;
  HTnode * right;
  char ch;
  int count;
};

Basic

Type HTnode
  next  As HTnode Ptr
  left  As HTnode Ptr
  right As HTnode Ptr
  ch    As String * 1
  count As Integer
End Type

Python (dodatek)

class HTnode:


    def __init__(self):
        self.next  = None
        self.left  = None
        self.right = None
        self.ch    = ''
        self.count = 0

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: root ← nil ; rozpoczynamy z pustą listą.
     ; Zmienna root wskazuje zawsze jej początek.
K02: Dla i = 0, 1, …, |s|-1, ; w pętli zliczamy
     wykonuj kroki K03…K14 ; znaki tekstu
K03:   p ← root
K04:   Dopóki p ≠ nil  p→ch ≠ s[i]: ; szukamy znaku
       wykonuj: p ← p→next ; w węzłach na liście
K05:   Jeśli p ≠ nil, 
       to idź do kroku 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:   p→next ← root ; ustawiamy pola węzła, 
       ; będzie on pierwszym elementem listy
K09:   p→left ← nil ; węzeł nie posiada synów
K10:   p→right ← nil
K11:   p→ch ← s[i] ; zapamiętujemy w węźle
       ; przetwarzany znak
K12:   p→count ← 0 ; liczba wystąpień początkowo
       ; równa zero
K13:   root ← p ; węzeł staje się pierwszym
       ; elementem listy
K14:   p→count ← p→count+1 ; zwiększamy o 1
       ; liczbę wystąpień znaku
K15: t ← true ; zakładamy, że lista jest uporządkowana
K16: p ← root ; p wskazuje pierwszy element
K17: Dopóki p→next ≠ nil:
     wykonuj kroki K18…K22
K18:   Jeśli p→count ≤ p→next→count, ; sortujemy
       to idź do kroku K22 ; bąbelkowo
K19:   p→ch ↔ p→next→ch ; wymieniamy ze sobą
       ; zawartości węzłów (tylko pola ch i count)
K20:   p→count ↔ p→next→count
K21:   t ← false ; zaznaczamy, że lista
       ; nie była uporządkowana
K22    p ← p→next ; przesuwamy się na kolejne
       ; dwa elementy listy
K23: Jeśli t = false, ; jeśli lista nie była posortowana, 
     to idź do kroku K15 ; 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, v₁, v₂ : wskazania węzłów.

Lista kroków:

K01: v₁ ← root ; pobieramy z listy dwa węzły
K02: v₂ ← v₁→next
K03: Jeśli v₂ = nil, ; na liście tylko jeden węzeł?
     to zakończ
K04: root ← v₂→next ; nowy początek listy
     ; za pobranymi węzłami
K05: Utwórz nowy węzeł
K06: p ← adres nowego węzła
K07: p→left ← v₁ ; pobrane węzły stają się
     ; synami nowego węzła
K08: p→right ← v₂K09: p→count ← v₁→count+v₂→count ; wyliczamy
     ; nową częstość
K10: Jeśli root = nil  p→count ≤ root→count, 
     to p→next ← root ; węzeł wstawiamy
        root ←  p ; z powrotem na listę
        Idź do kroku K01
K11: r ← root ; szukamy na liście miejsca dla węzła p
K12: Dopóki r→next) ≠ nil  p→count) > r→next→count, 
     wykonuj: r ← r→next
K13: p→next ← r→next ; węzeł p wstawiamy
     ; za węzłem wskazywanym przez r
K14: r→next ← p
K15: Idź do kroku K01

Przykładowe programy

Uwaga:

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.

Pascal

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

// Tworzy z listy drzewo Huffmana
//-------------------------------
procedure make_tree(var root : PHTnode);
var
  p, r, v1, v2 : PHTnode;
begin
  while true do
  begin
    // Pobieramy z listy dwa pierwsze węzły
    v1 := root;
    v2 := v1^.next;
    // Jeśli tylko jeden element, zakończ
    if v2 = nil then break;
    // Lista bez v1 i v2
    root := v2^.next;
    // Tworzymy nowy węzeł
    new(p);
    // Dołączamy do niego v1 i v2
    p^.left := v1;
    // i wyliczamy nową częstość
    p^.right := v2;
    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 print_tree(p : PHTnode;
                     b : string);
begin
  if p^.left = nil then
    writeln(p^.ch, ' ', b)
  else
  begin
    print_tree(p^.left, b+'0');
    print_tree(p^.right, b+'1');
  end;
end;

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

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

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

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

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

begin
  // Czytamy łańcuch wejściowy
  readln(s);
  // Tworzymy listę wierzchołków
  make_list(root, s);
  // Tworzymy drzewo kodu Huffmana
  make_tree(root);
  // Wyświetlamy kody znaków
  print_tree(root, '');
  // Kodujemy i wyświetlamy wynik
  code_huffman(root, s);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
  writeln;
  writeln;
end.

C++

// 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 make_list(HTnode * & root,
               string s)
{
  unsigned int i, x;
  char cx;
  HTnode * p;
  bool t;

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

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

  while(true)
  {
    // Pobieramy z listy dwa pierwsze węzły
    v1 = root;
    v2 = v1->next;
    // Jeśli tylko jeden element, zakończ
    if(!v2) break;
    // Lista bez v1 i v2
    root = v2->next;
    // Tworzymy nowy węzeł
    p = new HTnode;
    // Dołączamy do niego v1 i v2
    p->left = v1;
    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 print_tree(HTnode * p,
                string b)
{
  if(!p->left)
    cout << p->ch << " " << b << endl;
  else
  {
    print_tree(p->left, b+"0");
    print_tree(p->right, b+"1");
  }
}

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

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

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

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

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

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

  // Czytamy łańcuch wejściowy
  getline(cin, s);
  // Tworzymy listę wierzchołków
  make_list(root, s);
  // Tworzymy drzewo kodu Huffmana
  make_tree(root);
  // Wyświetlamy kody znaków
  print_tree(root, "");
  // Kodujemy i wyświetlamy wynik
  code_huffman(root, s);
  // Usuwamy drzewo z pamięci
  dfs_release (root);
  cout << endl << endl;
  return 0;
}

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 make_list(ByRef root As HTnode Ptr,_
                       s As String)

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

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

' Tworzy z listy drzewo Huffmana
'-------------------------------
sub make_tree(ByRef root As HTnode Ptr)

  Dim As HTnode Ptr p, r, v1, v2

  While 1
    ' Pobieramy z listy dwa pierwsze węzły
    v1 = root
    v2 = v1->Next
    ' Jeśli tylko jeden element, zakończ
    If v2 = 0 Then Exit While
    ' Lista bez v1 i v2
    root = v2->Next
    ' Tworzymy nowy węzeł
    p = new HTnode
    ' Dołączamy do niego v1 i v2
    p->left = v1
    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 print_tree(p As HTnode Ptr, _
               b As String)
  If p->Left = 0 Then
    Print p->ch; " ";b
  Else
    print_tree(p->left, b + "0")
    print_tree(p->right, b + "1")
  End If
End Sub

' Koduje znak
'------------
Function code_t(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 code_t(c, p->left, b+"0") OrElse _
           code_t(c, p->right, b+"1")
  End If
End Function

' Koduje tekst kodem Huffmana
'----------------------------
sub code_huffman(root As HTnode Ptr, _
                    s As String)
  Dim As Integer i

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

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

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

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

' Czytamy łańcuch wejściowy
Line Input s
' Tworzymy listę wierzchołków
make_list(root, s)
' Tworzymy drzewo kodu Huffmana
make_tree(root)
' Wyświetlamy kody znaków
print_tree(root, "")
' Kodujemy i wyświetlamy wynik
code_huffman(root, s)
' Usuwamy drzewo z pamięci
dfs_release(root)
Print
Print
End

Python (dodatek)

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


# Definicja węzła drzewa
# kodu bezprzystankowego
#-----------------------
class HTnode:


    def __init__(self,s):
      self.next  = None
      self.left  = None
      self.right = None
      self.ch    = s
      self.count = 0


# Tworzy listę wierzchołków
# s - tekst
#--------------------------
def make_list(s):
    # Tworzymy pustą listę
    r = None
    # Tworzymy węzły i zliczamy znaki
    for i in range(len(s)):
        # Szukamy na liście znaku s[i]
        p = r
        while p and p.ch != s[i]:
            p = p.next
        # Jeśli go nie ma, to
        if not p:
            # tworzymy dla niego nowy węzeł
            p = HTnode(s[i])
            # Węzeł trafi na początek listy
            p.next = r
            # Ustawiamy pola węzła
            p.left  = None
            p.right = None
            p.count = 0
            # Wstawiamy węzeł na początek listy
            r = p
        # Zwiększamy licznik wystąpień znaku
        p.count += 1
    # Listę sortujemy rosnąco względem count
    while True:
        # Zakładamy posortowanie listy
        t = True
        # Sortujemy od pierwszego elementu
        p = r
        while p.next:
            if p.count > p.next.count:
                # Wymieniamy zawartość
                # dwóch kolejnych elementów
                p.ch, p.next.ch = p.next.ch, p.ch
                p.count, p.next.count = \
                p.next.count, p.count
                # Sygnalizujemy nieposortowanie listy
                t = False
            # Przechodzimy do następnego elementu
            p = p.next
        if t: break
    return r

# Tworzy z listy drzewo Huffmana
# r - korzeń
#-------------------------------
def make_tree(r):
    while True:
        # Pobieramy z listy dwa pierwsze węzły
        v1 = r
        v2 = v1.next
        # Jeśli tylko jeden element, zakończ
        if not v2: break
        # Lista bez v1 i v2
        r = v2.next
        # Tworzymy nowy węzeł
        p = HTnode('')
        # Dołączamy do niego v1 i v2
        p.left = v1
        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 not r or p.count <= r.count:
            p.next = r
            r = p
            continue
        rr = r
        while rr.next and p.count > rr.next.count:
            rr = rr.next
        p.next = rr.next
        rr.next = p
    return r


# Drukuje zawartość drzewa Huffmana
#----------------------------------
def print_tree(p, b):
    if not p.left:
        print(p.ch, b)
    else:
        print_tree(p.left, b+"0")
        print_tree(p.right,b+"1")


# Koduje znak
#------------
def code_t(c, p, b):
    if not p.left:
        if c != p.ch:
            return 0
        else:
            print(b, end="")
            return 1
    else:
        return code_t(c, p.left,  b+"0") or \
               code_t(c, p.right, b+"1")


# Koduje tekst kodem Huffmana
# r - korzeń
# s - tekst
#----------------------------
def code_huffman(r, s):
    # Kodujemy poszczególne znaki
    for i in range(len(s)):
        code_t(s[i], r, "")


# Procedura DFS:postorder usuwająca drzewo
#-----------------------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy sam węzeł
        v.left = None
        v.right = None


# **********************
# *** Program główny ***
# **********************

# Czytamy łańcuch wejściowy
s = input()
# Tworzymy listę wierzchołków
root = make_list(s)
# Tworzymy drzewo kodu Huffmana
root = make_tree(root)
# Wyświetlamy kody znaków
print_tree(root, "")
# Kodujemy i wyświetlamy wynik
code_huffman(root, s)
# Usuwamy drzewo z pamięci
dfs_release(root)
print()

Wynik:

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

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Kompresja Huffmana

Problem

Co to jest kompresja

Kody o stałej długości

Kody bezprzystankowe

Algorytm tworzenia drzewa kodu przystankowego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm dekodowania wiadomości w kodzie bezprzystankowym

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Kodowanie Huffmana

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm tworzenia drzewa kodu Huffmana

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy