Algorytmy » Kompresja

Shanon-Fano, kodowanie

Kodowanie Shanon-Fano to historycznie pierwsza dobrze znana metoda kodowania oparta na teorii informacji opracowana niezależnie przez Shanona i Fano.
Głównym celem metod kodowania entropijnego, jakim jest kodowanie Shanon-Fano, jest minimalizacja długości strumienia symboli przyporządkowując poszczególnym symbolom jak najkrótsze symbole.
Główne założenia metody to:
- kody przyporządkowywane są pojedynczym symbolom i mają różną liczbę bitów

 np: A - 0; B - 1010; C - 110; D - 11101;
- kody symboli, których prawdopodobieństwo wystąpienia jest większe otrzymują krótsze kody niż kody o mniejszym prawdopodobieństwie

 np. Jeżeli A występuje 10 razy, B - 2, C - 4, a D - 1 to najkrótszy kod będzie mieć A, następny w kolejości C, potem B i na końcu D
- kod jest jednoznacznie dekodowalny
 np. Kod A - 0; B - 01; c - 11; D - 10 nie jest jednoznacznie dekodowalny, ponieważ strumień 0010 można odczytać jako ABA lub jako AAD.
Aby zachować warunek jenoznacznej dekodowalności (koniecznej w każdej metodzie bezstratnej) do otrzymywania kodów użyto drzewa binarnego. Drzewo jest budowane od korzenia. Elementy znajdujące się bliżej korzenia mają krótszy kod.
Na początek zadeklarujmy sobie takie struktury:
type TKod = record
       Kod: Byte;
       Ilosc: Integer;
       Dl: Byte;
       Wartosc: Word;
    end;
       TKody = array [0..255] of TKod;
var
  Hist: TKody;

Żeby zbudować takie drzewo należy postępować wg następującego algorytmu:
1. Określić prawdopodobieństwo wystąpienia poszczególnych symboli w strumieniu danych. (można wykorzystać zarówno dokładną liczbę wystąpień, jak również określić prawdopodobieństwo np. na podstawie jakiejś porcji danych ze strumienia lub zakodowane "na sztywno" prawdopodobieństwa np. na podstawie statystycznej liczby wystąpień danego znaku w języku polskim)
W naszej implementacji tego algorytmu wykorzystamy liczbę symboli w strumieniu. Jeżeli jednak zamierzamy kompresować bardzo duże zbiory, to należy użyć prawdopodobieństw
procedure Histogram(NazwaPliku: string);
var
  Plik: TFileStream;
  Buf: Byte;
begin
for Buf := 0 to 255 do
  with Hist[Buf] do
  begin
    Kod := Buf;
    Ilosc := 0;
    Dl := 0;
    Wartosc := 0;
  end;
  Plik := TFileStream.Create(NazwaPliku, fmOpenRead);
  while Plik.Position < Plik.Size do
  begin
    Plik.Read(Buf, 1);
    Inc(Hist[Buf].Ilosc);
  end;
  Plik.Free;
end;


 2. Posortowanie listy symboli w zależności od prawdopodobieństw, zaczynając od najbardziej prawdopodobnych.
procedure SortujIl(var A: TKody);

  procedure QuickSort(var A: TKody; iLo, iHi: Integer);
  var
    Lo, Hi, Mid: Integer;
    T: TKod;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2].Ilosc;
    repeat
      while A[Lo].Ilosc > Mid do
        Inc(Lo);
      while A[Hi].Ilosc < Mid do
        Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then QuickSort(A, iLo, Hi);
    if Lo < iHi then QuickSort(A, Lo, iHi);
  end;

begin
  QuickSort(A, 0, 255);
end;


3. Podział listy symboli na dwie grupy o możliwie bliskiej łącznej liczbie wystąpień symboli z obydwu części.
4. Przyporządkowanie jednej grupie symboli cyfry '0', a drugiej '1'
5. Rekursywne powtarzanie kroków 3 i 4 dla każdej z wyznaczonych grup i dopisywanie kolejnych cyfr, aż wszystkie grupy będą jedoelementowe.
procedure WyznaczKody(var A: TKody);

  procedure Koduj(var A: TKody; iLo, iHi, Sr: Integer);
  var
    Suma, i, j: Integer;
  begin
    Suma := 0;
    i := iLo;
    while Suma < (Sr div 2) do
    begin
      Suma := Suma + A[i].Ilosc;
      Inc(i);
    end;
    for j := iLo to i-1 do    
    begin
      A[j].Wartosc := A[j].Wartosc shl 1;
      Inc(A[j].Dl);
    end;
    for j := i to iHi do
    begin
      A[j].Wartosc := A[j].Wartosc shl 1 or 1;
      Inc(A[j].Dl);
    end;
    if i-1 > iLo then
      Koduj(A, iLo, i-1, Suma);
    if i < iHi then
      Koduj(A, i, iHi, Sr - Suma);
  end;
 
var
  j, Sr: Integer;
begin
  Sr := 0;
  j := 0;
  while A[j].Ilosc > 0 do
  begin
    Sr := Sr + A[j].Ilosc;
    Inc(j);
  end;
  Koduj(A, 0, j-1, Sr);
end;

6. Ostatecznie kodujemy poszczególne symbole ze strumienia
procedure Koduj;
var
  PlikZ: TFileStream;
  PlikDo: TBitStream;
  Buf: Byte;
  LiczbaZnakow: Cardinal;
begin
  if not OpenDialog1.Execute then Exit;
  if not SaveDialog1.Execute then Exit;
  Histogram(OpenDialog1.FileName);
  SortujIl(Hist);
  WyznaczKody(Hist);
  SortujKod(Hist);
  PlikZ := TFileStream.Create(OpenDialog1.FileName, fmOpenRead);
  PlikDo := TBitStream.Create(SaveDialog1.FileName, fmCreate);
  LiczbaZnakow := PlikZ.Size;
  ProgressBar1.Max := LiczbaZnakow;
  {Przepisujemy tablicę częstości wystąpień do pomocniczej tablicy, którą zapiszemy w pliku. Jest to bardziej ekonomiczne, niż przekazywanie całego drzewa}
  for Buf := 0 to 255 do
    HistPom[Buf] := Hist[Buf].Ilosc;
    PlikDo.WriteBuffer(LiczbaZnakow, SizeOf(Cardinal));
    PlikDo.WriteBuffer(HistPom, SizeOf(HistPom));
  while PlikZ.Position < PlikZ.Size do
  begin
    ProgressBar1.Position := PlikZ.Position;
    PlikZ.Read(Buf, 1);
    PlikDo.WriteBitsR(Hist[Buf].Wartosc, Hist[Buf].Dl);
  end;
  PlikDo.FlushBuf;
  PlikZ.Free;
  PlikDo.Free;
end;


Dekodowanie przebiega następująco:
1. Pobranie ze strumienia danych informacji na temat prawdopodobieństwa występowania poszczególnych symboli.
2. Zbudowanie drzewa binarnego analogicznie jak przy kodowaniu
3. Pobieranie kolejnych bitów i przeszukiwanie drzewa w celu znalezienia kolejnych liści.

procedure Dekoduj;

  function Znajdz(var Buf: Word; Dl: Byte): SmallInt;
  {Tutaj mamy uproszczone wyszukiwanie. Jeżeli użylibyśmy drzewa binarnego, a nie tablicy symboli to proces dekompresji mógłby być szybszy}
  var
    i: SmallInt;
  begin
    i := 255;
    while (i >= 0) and ((Hist[i].Wartosc < Buf) or (Hist[i].Dl < Dl)) do
      Dec(i);
    if i > 0 then Buf := Hist[i].Kod;
    Result := i;
  end;

var
  PlikDo: TFileStream;
  PlikZ: TBitStream;
  Buf: Word;
  Dl: Byte;
  LiczbaZnakow, L: Cardinal;
  begin
  if not OpenDialog1.Execute then Exit;
  if not SaveDialog1.Execute then Exit;
  PlikDo := TFileStream.Create(SaveDialog1.FileName, fmCreate);
  PlikZ := TBitStream.Create(OpenDialog1.FileName, fmOpenRead);
  PlikZ.ReadBuffer(LiczbaZnakow, SizeOf(Cardinal));
  PlikZ.ReadBuffer(HistPom, SizeOf(HistPom));
  for Buf := 0 to 255 do
    with Hist[Buf] do
    begin
      Kod := Buf;
      Dl := 0;
      Wartosc := 0;
      Ilosc := HistPom[Buf];
    end;
    SortujIl(Hist);
    WyznaczKody(Hist);
    SortujKod(Hist);
    L := 0;
    ProgressBar1.Max := LiczbaZnakow;
    while L < LiczbaZnakow do
    begin
      Buf := 0;
      Dl := 0;
      repeat
        Buf := (Buf shl 1) or PlikZ.ReadBitsR(1);
        Inc(Dl);
      until Znajdz(Buf, Dl) > 0;
      PlikDo.Write(Byte(Buf), 1);
      Inc(L);
      ProgressBar1.Position := L;
    end;
    PlikZ.Free;
    PlikDo.Free;
  end;


Teraz czas na przykład.

Załóżmy, że mamy alfabet składający się z 5 symboli (zamiast rozważanych 256 w algorytmie): A, B, C, D, E. Ilość wystąpień każdego z nich:
A - 6
B - 12
C - 4
D - 5
E - 4
Teraz według algorytmu posortujmy w kolejności rosnącej:
B - 12
A - 6
D - 5
C - 4
E - 4
Dalej podzielmy to na dwie jak najbardziej zbliżone liczbą wystąpień grupy i górnej przyporządkujmy symbol '0', a dolnej '1':
B - 12  0
A - 6    0

D - 5   1
C - 4   1
E - 4   1

Dalej każdą z tych grup dzielimy na kolejne dwie i przyporządkowujemy symbole według tej samej zasady:
B - 12  00

A - 6    01

D - 5   10

C - 4   11
E - 4   11

I ostatni podział:
B - 12  00

A - 6    01

D - 5   10

C - 4   110

E - 4   111

W ten sposób przyporządkowaliśmy tym symbolom takie symbole:
A - 01; B - 00; C - 110; D - 10; E - 111; (jeżeli takie same dane wprowadzilibyście do napisanego wcześniej programu otrzymalibyście odrobinę inne wartości. W danej implementacji w celu uproszczenia obliczeń zmiast dzielić na dwie jak najbardziej równe części bierzemy wszystkie elementy zaczynając od największego, aż suma ich wystąpień przekroczy połowę wartości wystąpień wszystkich znaków w grupie)
Drzewo binarne odpowiadające temu podziałowi można przedstawić tak:

      __|__
   0|               |1
   _|_          |
0|     |1    0|        |1
 B    A       D    |
                    0|       |1
                     C       E  

Jak widać nasz strumień zajmie 70 bitów (6*A+2*B+4*C+5*D+4*E=6*2+12*2+4*3+5*2+4*3=70), podczas gdy przy tradycyjnym zapisie potrzebowalibyśmy 3 znaków do zapisu każdego symbolu (A-000; B-001; C-010; D-011; E-100) i strumień zająłby 31*3 = 93 bity. Całkiem nieźle, prawda? Powiem tylko, że teoretycznie można skompresować cały strumień do ok. 67,44 bitów (taka jest ilość informacji zawarta w źródle na podstawie teorii informacji)

W praktycznej realizacji algorytmu przyjmujemy pewne uproszczenia.
Nie tworzymy typowego drzewa, a jedynie wykorzystujemy w tym celu zmodyfikowaną tablicę czestotliwości wystąpień (oszczędność pamięciowa). Nie przekazujemy też całego drzewa do pliku, a jedynie czestości wystąpień znaków. Dekoder sam odtwarza drzewo w taki sam sposób w jaki koder je tworzył. Dzięki temu plik wynikowy jest dużo mniejszy (a to jest najważniejszy cel).

Cały program kompresujący można znaleźć tutaj

7 komentarzy

MAZI666 2007-01-03 16:45

Witam!
Szukam implementacji tego alogrytmu w C/C++. Natknąl sie gdzies ktos na takową, lub sam ja stworzyl? Z gory dziekuje. Pozdriawiam

Marooned 2004-01-11 13:08

Tylko dodam, że że ta metoda jest odwrotną do kodowania Huffmana tyle, że tam nie zaczyna się od korzenia, ale od gałęzi. Wynik jest ten sam. (Jutro zalka z tego [systemy informacyjne], ale jestem zwolniony :P)

Pawlik67 2003-01-09 20:20

Przyznam się, że art bardzo mnie zainteresował. Chętnie oczekiwałbym kolejnych. Zrodziły mi się jednak pytania :
1. Rozumiem, że wraz ze skompresowanym plikiem musi być przesłany "kod" drzewa ?
2. Jak tworzy się take drzewa ? ( mam na myśli metodę - opis )
Pozdrawiam

Kapustka 2003-01-07 18:08

Dzięki za przykład :)

Adam Boduch 2003-01-06 14:08

Całkiem dobry pomysł, z tymi ramkami, co otaczają kod źródłowy :)

Kapustka 2003-01-06 01:41

Podoba mi się :) - Krótko i treściwie. (odrobinę żałuję że całość jest tak silnie oparta na delphi, ale nie będę marudził).

Drobne wątpliwości wywołał fragment:
"1. Określić prawdopodobieństwo wystąpienia poszczególnych symboli w strumieniu danych. "

Czy chodzi o to, że zliczamy ilość wystąpień w każdej litery w całym tekście (ew. w reprezentacyjnej próbce), czyli inaczej mówiąc, sortujemy litery pod względem ilości wystąpień ?

Jeśli tak, to słowo "prawdopodobieństwo" jest odrobinę mylące, jako że mamy do czynienia z dobrze określoną sytuacją i nie wydarzy się nic "nieprzewidzialnego". Nie wiem czy to co napisałem jest zrozumiałe? Chodzi o to, że dopiero wtedy, gdy nie mamy kompletu informacji, do opisu (z konieczności) musimy użyć prawdopodobieństwa. W tej sytuacji wszystko jest wiadome, informacja jest pełna.

Napomknięty problem "jednoznacznego opisu" jest niezwykle ciekawy (arcyciekawy), co więcej, narzuca się skojarzenie z pokrewnym mu problemem "Odpowiedniości słów", który do dziś jest w ogóle nierozwiązywalny (nie chodzi o to, że rozwiązanie jest czasochłonne, tylko że ten problem do tej pory nie ma swojego rozwiązania! )

... ale ... wypowiedź w stylu "gwarancją jednoznaczności jest zastosowanie drzewa binarnego" jest cokolwiek niewystarczająca i rodzi kilka pytań -> Dlaczego tak jest? Jak zbudowane jest to drzewo? (generalnie drzewa buduje się od korzenia, więc to jeszcze za mało ...).

Artykuł ciekawy, przy czym w moim odczuciu pozostawia za sobą kilka otwartych pytań (zresztą może to i dobrze, bo ostatecznie skłania do zamyślenia się)

Zagadnienie kodowania jest przebogatą kopalnią pytań i sprytnych algorytmów i jedyną rzeczą o jakiej marzę, to aby Dryo pozwolił się ponieść i nakreślił przed nami to bogactwo ... a będzie cudownie :)

P.S. Dryo, jeśli tylko wypunktujesz te zagadnienia rachunku prawdopodobieństwa, które wymagają objaśnienia - chętnię Ciebie wspomogę.

Pozdrawiam