Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


22. Datenkomprimierung



Implementation

Für die Konstruktion des Häufigkeitsbaumes der wird der allgemeine Prozeß der Entfernung des kleinsten Elements aus einer Menge ungeordneter Elemente benötigt, weshalb wir die Prozedur pqdownheap aus Kapitel 11 benutzen, um mit Hilfe der Häufigkeitszähler einen indirekten Heap zu erzeugen und zu verwalten. Da wir zuerst an den kleinen Werten interessiert sind, wollen wir annehmen, daß die Richtung der Ungleichungen in pqdownheap umgekehrt worden ist. Ein Vorteil der Anwendung der indirekten Vorgehensweise besteht darin, daß es einfach ist, Häufigkeitszähler mit dem Wert 0 zu ignorieren. Abbildung 22.6 zeigt den Heap, der für unser Beispiel erzeugt wird; genau gesagt, wird dieser Heap aufgebaut, indem zuerst das heap-Feld in der Weise initialisiert wird, daß es auf die von null verschiedenen Häufigkeitszähler zeigt, und indem danach wie folgt die Prozedur pqdownheap aus Kapitel 11 verwendet wird:

    N:=0;
    for i:=0 to 26 do
      if count[i]<>0 then
        begin N:=N+1; heap[N]:=i end;
    for k:=N downto 1 do pqdownheap(k);

Abbildung 22.6
Abbildung 22.6 Anfänglicher Heap (indirekt) für die Erzeugung des Huffmann-Baumes.

Wie oben erwähnt wurde, wird dabei vorausgesetzt, daß die Richtung der Ungleichungen in der Implementation von pqdownheap umgekehrt worden ist.

Nunmehr ist die Benutzung dieser Prozedur zur Konstruktion des Baumes in der oben beschriebenen Weise sehr einfach: Wir entnehmen die beiden kleinsten Elemente aus dem Heap, addieren sie und legen das Ergebnis wieder im Heap ab. Bei jedem Schritt erzeugen wir einen neuen Zählwert und verringern die Größe des Heap um eins. Im Ergebnis dieses Prozesses werden N - 1 neue Zählwerte erzeugt, einer für jeden inneren Knoten des erzeugten Baumes, wie im folgenden Programmstück:

    repeat
      t:=heap[1]; heap[1]:=heap[N]; N:=N-1;
      pqdownheap(1);
      count[26+N]:=count[heap[1]]+count[t];
      dad[t]:=26+N; dad[heap[1]]:=-26-N;
      heap[1]:=26+N; pqdownheap(1);
    until N=1;
    dad[26+N]:=0;

Die ersten beiden Zeilen dieser Schleife stellen in Wirklichkeit pqremove dar; die Größe des Heap wird um eins verringert. Danach wird ein neuer innerer Knoten mit dem Index 26 + N »erzeugt«, und er erhält einen Wert, der gleich der Summe des Wertes an der Wurzel und des gerade entfernten Wertes ist. Danach wird dieser Knoten an die Wurzel gesetzt, was ihre Priorität erhöht, wodurch ein weiterer Aufruf von pqdownheap erforderlich wird, um die Ordnung im Heap wiederherzustellen. Der Baum selbst wird mit Hilfe eines Feldes von »Vorgänger«-Verkettungen dargestellt: dad[t] ist der Index des Vorgängers des Knotens, dessen Gewicht in count[t] gespeichert ist. Das Vorzeichen von dad[t] gibt an, ob der Knoten ein linker oder rechter Nachfolger seines Vorgängers ist. Zum Beispiel gilt in dem obigen Baum count[30] = 21, dad[30] = -28 und count[28] = 37 (womit angegeben wird, daß der Knoten mit dem Gewicht 21 den Index 30 hat und der rechte Nachfolger eines Vorgängers mit dem Index 28 und dem Gewicht 37 ist). In Abbildung 22.7 ist das Feld dad für die inneren Knoten des Baumes aus Abbildung 22.5 angegeben.

Abbildung 22.7
Abbildung 22.7 Darstellung eines Huffmann-Baumes (innerer Knoten) mit Hilfe der Vorgänger-Verkettung.

Der folgende Programmabschnitt erzeugt den eigentlichen Huffman-Code, so wie er durch den Trie in Abbildung 22.5 dargestellt ist, aus der Darstellung des Verschlüsselungsbaumes, der im Verlaufe des Analyseprozesses berechnet wurde. Der Code wird durch zwei Felder repräsentiert: code[k] gibt die Binärdarstellung des k-ten Buchstaben an, und len[k] gibt die Anzahl der Bits von code[k] an, die im Code zu verwenden ist. Beispielsweise ist I der neunte Buchstabe und hat den Code 001, daher ist code[9] = 1 und len[9] = 3.

    for k:=0 to 26 do
      if count[k]=0 then
        begin code[k]:=0; len[k]:=0 end
      else
        begin
        i:=0; j:=1; t:=dad[k]; x:=0;
        repeat
          if t<0 then begin x:=x+j; t:=-t end;
          t:=dad[t]; j:=j+j; i:=i+1
        until t=0;
        code[k]:=x; len[k]:=i;
        end;

Schließlich können wir diese berechneten Darstellungen des Codes benutzen, um die Zeichenfolge zu kodieren:

    for j:=1 to M do
      for i:=len[index(a[j])] downto 1 do
        write(bits(code[index(a[j])],i-1,1):1);

Dieses Programm verwendet die Prozedur bits aus den Kapiteln 10 und 17 für den Zugriff auf einzelne Bits. Unser Beispiel wird mit nur 236 Bits kodiert, was gegenüber den für die einfache Kodierung verwendeten 300 Bits eine Einsparung von 21% bedeutet:

0110111100100110101101011000111001111001110111011100100001111111110
1101001110101110011111000001101000100101101100101101111000010010010
0001111111011011110100010000011010011010001111000100001010010111001
01111110100011101110101001110111001

Nunmehr muß, wie bereits erwähnt, der Baum gespeichert oder zusammen mit der Zeichenfolge übertragen werden, um diese dekodieren zu können. Zum Glück ist dies mit keinerlei ernsthaften Schwierigkeiten verbunden. In Wirklichkeit ist es nur erforderlich, das Feld code zu speichern, da der digitale Such-Trie, der sich aus dem Einfügen der Einträge aus diesem Feld in einen ursprünglich leeren Baum ergibt, der Baum für die Dekodierung ist.

Demzufolge sind die obengenannten Einsparungen bei der Speicherung nicht ganz korrekt, da die Zeichenfolge nicht ohne den Trie dekodiert werden kann und wir den Speicherplatzbedarf des Trie (d. h. des Feldes code) mit berücksichtigen müssen. Eine Kodierung mit Hilfe des Huffman-Codes ist daher nur für umfangreiche Dateien effizient, wo die Einsparungen bei der Zeichenfolge ausreichend sind, um diesen Mehraufwand auszugleichen, oder auch in Situationen, wo der Kodierungs-Trie im voraus berechnet und für eine große Anzahl von Zeichenfolgen benutzt werden kann. Zum Beispiel könnte für Textdokumente ein Trie, der auf den Häufigkeiten des Auftretens der Buchstaben in der deutschen Sprache beruht, verwendet werden. In gleicher Weise könnte ein Trie, der auf den Häufigkeiten des Auftretens von Zeichen in Pascal-Programmen beruht, für die Kodierung von Programmen benutzt werden (zum Beispiel befindet sich »;« wahrscheinlich in der Nähe der Spitze eines solchen Trie). Ein Kodierungsalgorithmus mit Hilfe des Huffman-Codes liefert bei Anwendung auf den Text des vorliegenden Kapitels eine Einsparung von ungefähr 23%.

Wie zuvor führt für echt zufällige Dateien selbst dieses verfeinerte Kodierungsschema zu keinem Erfolg, da jedes Zeichen annähernd gleich häufig auftritt, was zu einem vollständig ausgeglichenen Kodierungsbaum und einer gleichen Anzahl von Bits pro Zeichen im Code führen würde.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]