Algorytmy » Kompresja

Shanon-Fano, kodowanie

Dryobates

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;
  1. 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;

  1. Podział listy symboli na dwie grupy o możliwie bliskiej łącznej liczbie wystąpień symboli z obydwu części.
  2. Przyporządkowanie jednej grupie symboli cyfry '0', a drugiej '1'
  3. 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</p>
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; <font color="000080">{Przepisujemy tablicę częstości wystąpień do pomocniczej tablicy, którą zapiszemy w pliku. Jest to bardziej ekonomiczne, niż przekazywanie całego drzewa}</span> 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 (6A+2B+4C+5D+4E=62+122+43+52+43=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

Kompresja

7 komentarzy

M6

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

Marooned

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

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

Dzięki za przykład :)

Adam Boduch

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

Kapustka

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