Startseite < Informatik < Algorithmen < Sortieren Komprimieren < RLE [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Huffman Lempel-Ziv > Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
Huffman
Die Idee von Morse wird von Huffman auf die Komprimierung beliebiger Daten übertragen.
Einführung Theorie: Huffman
Definition
Das Grundprinzip der Huffman-Kompression ist recht einfach:

Die Werte, die in gegebener Nachricht (zu komprimierender Datenstrom) am häufigsten vorkommen, werden so kurz wie möglich kodiert (abgespeichert). Die Kodierung für seltenere Werte beansprucht dagegen (im Normalfall) etwas mehr Speicherplatz. Deshalb spricht man hier von einer Kodierung variabler Länge.

Damit aber das Komprimat wieder eindeutig dekomprimiert werden kann, spielt die Fano-Bedingung eine entscheidende Rolle.
Fano-Bedingung
„Die Fano-Bedingung 1 ist eine Bedingung für die Dekodierbarkeit eines Codes. Ein Code erfüllt die Fano-Bedingung, wenn kein Wort aus dem Code der Anfang eines anderen Wortes desselben Codes ist”, heißt es in [INFODUDEN].
Dabei sei bemerkt, dass ein Wort hier allgemeiner als beliebige Kette von Symbolen, gleich welcher Art, aufgefaßt wird.




Das sicherlich bekannteste Beispiel zur Fano-Bedingung ist das Morsealphabet. 2

Schon in den Frühzeiten der Telegraphie kannte man bereits die Kodierung variabler Länge. Morse entschied sich für die Kodierung variabler Länge, damit die kodierte Nachricht kürzer wird. Dabei bezieht sich diese Kompression nicht auf den Speicherplatz, sondern viel mehr auf die Übertragungszeit. Zeichen, die in der (englischen) Sprache häufiger vorkommen, werden kürzer dargestellt bzw. mit weniger Zeitaufwand übermittelt als die selteneren Zeichen:
  • häufige Zeichen
    e = . #
    a = . - #
  • eher seltenere Zeichen
    o = - - - #
    s = . . . #
  • ganz seltene Zeichen
    j = . - - - #
    q = - - . - #
  • bekanntes Beispiel
    . . . # - - - # . . . #
Ohne einer signifikanten Pause (#) nach jeder Buchstaben-Kodierung wäre der Morse-Code praktisch nicht eindeutig interpretierbar (Verletzung der Fano-Bedingung); beispielsweise könnte ein kurzes Signal als e oder als Anfang von a oder als Anfang von s oder als Anfang von j und so weiter aufgefaßt werden.

Die Fano-Bedingung ermöglicht es, die (Buchstaben-) Kodierungen deterministisch und eindeutig zu interpretieren.

Die Idee von Morse spiegelt sich in der Huffman-Kodierung wider; es kommt praktisch nichts Neues mehr dazu. Wer die Morse-Telegraphie verstanden hat, wird bei der Huffman-Kodierung keine Probleme haben.
1) R. M. Fano war der Begründer einer statistischen Theorie der Nachrichtenübertragung.
2) Samuel Finley Breese Morse (1791-1872), amerikanischer Maler und Erfinder, entwickelte seit 1837 den ersten brauchbaren elektromagnetischen Schreibtelegraphen und dazu das Morsealphabet.
Komprimierung
Die Huffman-Kodierung geht bei der Komprimierung einer Nachricht im Prinzip genauso vor wie einst Samuel Morse.
Um allerdings eine bestmögliche Komprimierung für beliebige Daten erreichen zu können, orientiert sich die Huffman-Kodierung nicht an ein statisch vorgegebenes Kodierungsalphabet (wie z. B. das genormte Morsealphabet), sondern errechnet sich zu einer gegebenen Nachricht das dazugehörige Kodierungsalphabet, d. h. das Kodierungsalphabet wird in Abhängigkeit zur gegeben Nachricht erstellt.

Im Wesentlichen besteht die Huffman-Komprimierung aus zwei Schritten:
  1. Ermittlung des Kodierungsalphabets zur gegebenen Nachricht (Details hierzu siehe weiter unten)

    Das Kodierungsalphabet wird Bestandteil des Komprimats (Header-Teil).
  2. Kodierung der gegebenen Nachricht bzgl. des ermittelten Kodierungsalphabets

    Die Nachricht wird neu geschrieben, wobei statt der Werte die entsprechenden Kodierungen des Kodierungsalphabets ausgegeben werden (Body-Teil).
Dekomprimierung
Die Huffman-Dekomprimierung besteht im Wesentlichen ebenfalls nur aus zwei Schritten:
  1. Auslesen des Kodierungsalphabets (Header-Teil)
  2. Dekodierung der kodierten Nachricht (Body-Teil)

    Nur mit diesem ausgelesenen Kodierungsalphabet kann die dazugehörige kodierte Nachricht eindeutig dekodiert werden.
Ermittlung des Kodierungsalphabets
Die Hauptarbeit der Huffman-Kodierung steckt nicht in der Kodierung bzw. Dekodierung, sondern in der Ermittlung des Kodierungsalphabets mit den folgenden Anforderungen:
  • Das Kodierungsalphabet ist praktisch eine adjazente Liste, die jedem Zeichen gegebener Nachricht eine eindeutige, binäre Kodierung unter Einhaltung der Fano-Bedingung zuordnet.
  • Damit allerdings ein Komprimiereffekt zustande kommt, muss den Zeichen, die am häufigsten in der Nachricht vorkommen, jeweils die kürzest mögliche Kodierung zugeordnet werden. Nach dem Motto: Je seltener ein Zeichen, desto länger die Kodierung — je häufiger, desto kürzer!
Wenn das Kodierungsalphabet durch einen Binär-Baum repräsentiert wird, stellt die Erfüllung der beiden genannten Anforderungen kein größeres Problem mehr dar.
Kodierungsalphabet nach Huffman
H = 000
u = 001
f = 01
m = 100
a = 101
n = 11
Die Zeichen gegebener Nachricht sind die Blätter des Binär-Baumes, wobei die Pfade von der Wurzel bis zu den Blättern die jeweils dazugehörigen Kodierungen darstellen. So kann man gewährleisten, dass keine Kodierung der Anfang einer anderen Kodierung ist (Fano-Bedingung).

Zeichen, die in gegebener Nachricht häufiger vorkommen, liegen näher an der Wurzel als seltenere Zeichen. Um allerdings den maximalen Komprimiereffekt garantieren zu können, muss der Binär-Baum gemäß der Häufigkeit der Zeichen aufgebaut werden.

Den Aufbau des Binärbaumes soll anhand des Beispiels SEILSESSEL erläutert werden.
Sei nun das zusammengesetzte Hauptwort SEILSESSEL die Nachricht, die es mit der Huffman-Kodierung zu komprimieren gilt.
Schritt 1: Aufbau des Binär-Baumes am Beispiel SEILSESSEL
Zunächst ermittelt man die Häufigkeit der jeweiligen Zeichen gegebener Nachricht. Je kleiner die Zahl, desto seltener kommt das dazugehörige Zeichen in gegebener Nachricht vor. SEILSESSEL enthält 10 Zeichen davon 4 S, 3 E, 2 L und 1 I.
Schritt 2: Aufbau des Binär-Baumes am Beispiel SEILSESSEL
Es werden die beiden seltensten Zeichen zu einem kleinen Baum zusammengefasst, wobei deren Häufigkeitswerte zu einem neuen Häufigkeitswert zusammenaddiert werden. Der neue Wert wird stellvertretend für die beiden kleinsten Häufigkeitswerte der Liste angefügt.
Schritt 3: Aufbau des Binär-Baumes am Beispiel SEILSESSEL
Es werden wiederum die beiden kleinsten Häufigkeitswerte ermittelt, die wiederum eine Zusammenfassung zur Folge haben. Die Liste mutiert immer mehr zu einem Binär-Baum.
Schritt 4: Aufbau des Binär-Baumes am Beispiel SEILSESSEL
Man erhält das Kodierungsalphabet, wenn die Liste nur noch aus einem einzigen Häufigkeitswert besteht und ein Binär-Baum vorliegt wie hier!

S = 0
E = 10
I = 110
L = 111
Das S kommt am häufigsten in der Nachricht SEILSESSEL vor und erhält deshalb auch die kürzeste Kodierung. Die Kodierung zu SEILSESSEL ergibt folgenden Binär-Code: 0 10 110 111 0 10 0 0 10 111. Diese Kodierung kann tatsächlich als Komprimierung angesehen werden, denn bei einer Textdarstellung beansprucht jedes Zeichen normalerweise genau 8 Bits Speicherplatz.
Ermittlung des Kodierungsalphabets nochmal ganz allgemein!
/* Ermittle die Häufigkeiten H der Zeichen Z gegebener Nachricht N */
while (N.hasNext()) do
  count[Z(N.next())] += 1;

/* Alle Zeichen Z, die in der Nachricht N vorkommen,
   mit der jeweils dazugehörigen Häufigkeit H
   der Min-Priority-Queue minQ hinzufügen. */
for each count[] as (H, Z)
  if (H > 0) minQ.add(H, Z);

/* Aufbau des Binär-Baumes */
while (minQ.length > 1) {
  (leftH, left) = minQ.remove();
  (rightH, right) = minQ.remove();
  minQ.add(leftH + rightH, new Tree(left, right));
}

/* Das Kodierungsalphabet! */
(xH, HuffmanCodeTree) = minQ.remove(); // wobei xH == N.length
⇑ Ermittlung des Kodierungsalphabets nochmal ganz allgemein! ⇑
Details zur Min-Priority-Queue finden Sie unter PriorityQueue.
Implementierung Implementierung: Huffman
Bits statt Bytes
Da es sich bei der Huffman-Kodierung um Kodierungen variabler Länge handelt, ist es erforderlich einzelne Bits lesen bzw. schreiben zu können. Dies ist aber aufgrund der Rechnerarchitektur eines herkömmlichen PC's nicht möglich. Die kleinste Speichereinheit, auf die der Programmierer zugreifen kann, ist das Byte, welches 8 Bits zusammenfasst.
Bindet man allerdings einen Byte-Wert an eine Variable, so können die einzelnen Bit-Werte der Variable genauer betrachtet werden. Deshalb hat man durch entsprechende Pufferung von Byte-Werten die Möglichkeit, das Lesen (BitReader) bzw. Schreiben (BitWriter) von einzelnen Bits zu simulieren.
Hilfsklasse: TBitReader, um einzelne Bits lesen zu können
unit UBitReader;

interface

uses
  Classes;

(* TBitReader:
   Diese Klasse simuliert das Lesen einzelner Bits
   vom gegebenen Stream. *)
type
  TBitReader = class
  private
    FStream: TStream;
    FBuffer: Byte;
    FBitPosition: Byte;
  public
    constructor Create(AStream: TStream);
    procedure Init;
    procedure Finish;
    function ReadBit: Byte; // $00 oder $01
    function ReadByte: Byte; // $00..$FF
  end;

implementation

constructor TBitReader.Create(AStream: TStream);
begin
  inherited Create;
  Self.FStream := AStream;
  Self.Init;
end;

procedure TBitReader.Init;
begin
  Self.FBuffer := 0;
  Self.FBitPosition := 0;
end;

procedure TBitReader.Finish;
begin
  Self.Init;
end;

function TBitReader.ReadBit: Byte;
begin
  { ggf. ein neues Byte aus Stream lesen }
  if (Self.FBitPosition <= 0) then
  begin
    Self.FStream.Read(Self.FBuffer, 1);
    Self.FBitPosition := 8;
  end;
  Result := (Self.FBuffer shr (Self.FBitPosition - 1)) and $01;
  Dec(Self.FBitPosition);
end;

function TBitReader.ReadByte: Byte;
var
  I: Integer;
begin
  Result := $00;
  { Erzeugt das Ergebnis Bit-weise. }
  for I := 1 to 8 do
    Result := (Result shl 1) or Self.ReadBit;
end;

end.
⇑ Hilfsklasse: TBitReader, um einzelne Bits lesen zu können ⇑
Hilfsklasse: TBitWriter, um einzelne Bits schreiben zu können
unit UBitWriter;

interface

uses
  Classes, SysUtils;

(* TBitWriter, das Pendant zu TBitReader!
   Diese Klasse simuliert das Schreiben einzelner Bits
   in den gegebenen Stream. *)
type
  TBitWriter = class
  private
    FStream: TStream;
    FBuffer: Int64;
    FBitPosition: Byte;
    procedure MinimizeBuffer();
  public
    constructor Create(AStream: TStream);
    procedure Init;
    procedure Finish;
    procedure WriteBits(Code: Int64; Size: Byte); // max. 64 Bits
  end;

  EBitWriterError = class(Exception);

implementation

procedure TBitWriter.MinimizeBuffer();
var
  Buffer: Byte;
begin
  { Puffer Byte-weise in den Stream schreiben.
    Nur das letzte unvollständige Byte, falls vorhanden,
    bleibt noch im Puffer. }
  while Self.FBitPosition >= 8 do
  begin
    Buffer := Byte(Self.FBuffer shr (Self.FBitPosition - 8));
    Self.FStream.WriteBuffer(Buffer, 1);
    Dec(Self.FBitPosition, 8);
  end;
end;

constructor TBitWriter.Create(AStream: TStream);
begin
  inherited Create;
  Self.FStream := AStream;
  Self.Init;
end;

procedure TBitWriter.Init;
begin
  Self.FBuffer := 0;
  Self.FBitPosition := 0;
end;

procedure TBitWriter.Finish;
var
  Buffer: Byte;
begin
  Self.MinimizeBuffer(); // Aufräumen des Puffers

  { Das letzte unvollständige Byte, falls vorhanden,
    in den Puffer schreiben,
    der Rest wird mit Nullen oder Einsen versehen (egal). }
  if Self.FBitPosition > 0 then
  begin
    Buffer := Byte(Self.FBuffer shl (8 - Self.FBitPosition));
    Self.FStream.WriteBuffer(Buffer, 1);
    Self.Init;
  end;
end;

procedure TBitWriter.WriteBits(Code: Int64; Size: Byte);
begin
  Self.MinimizeBuffer(); // Aufräumen des Puffers

  if Size > 64 then raise EBitWriterError.Create('Size larger than Code.')
  else if Size > 56 then
  begin
    { Vermeidung eines Überlaufs des Bit-Puffers. }
    Self.FBuffer := (Self.FBuffer shl 8) or (Code and $00000000000000FF);
    Inc(Self.FBitPosition, 8);
    Dec(Size, 8);
    Code := Code shr 8;
    Self.MinimizeBuffer();
  end;

  { Neuer Binärcode der Länge Size wird dem Puffer hinzugefügt. }
  Code := Code shl (64 - Size);
  Code := Code shr (64 - Size);
  Self.FBuffer := (Self.FBuffer shl Size) or Code;
  Inc(Self.FBitPosition, Size);
end;

end.
⇑ Hilfsklasse: TBitWriter, um einzelne Bits schreiben zu können ⇑
Kompression und Dekompression: Huffman
unit UHuffman;

interface

uses
  Classes;

procedure HuffmanCompress(Source, Destination: TMemoryStream);
procedure HuffmanDecompress(Source, Destination: TMemoryStream);

implementation

uses
  UBitReader, UBitWriter;

type
  TCodeCharacter = record // Kodierung variabler Länge
    Size: 0..64;
    Code: Int64;
  end;

  TCodeAlphabet = array[Byte] of TCodeCharacter; // Kodierungsalphabet

  TCharacterCount = array[Byte] of Longword; // Zeichenzähler

  TCharacter = class;
  TTree = class;

  { Abstrakte Basisklasse für Zeichen und Binär-Baum }
  TElement = class(TObject) // TCharacter or TTree
  private
    FParent: TElement;
    FCount: Longword;
    FBit: Byte;
    FBitReader: TBitReader;
    FBitWriter: TBitWriter;
  public
    constructor Create(BitReader: TBitReader; BitWriter: TBitWriter);
    function GetCodeCharacter: TCodeCharacter;
    procedure Read; virtual;
    procedure Write; virtual;
  end;

  TCharacter = class(TElement)
  private
    FValue: Byte;
  public
    constructor Create(Value: Byte; Count: Longword;
                       BitReader: TBitReader; BitWriter: TBitWriter);
    procedure Read; override;
    procedure Write; override;
  end;

  TTree = class(TElement)
  private
    FChildren: array[0..1] of TElement;
  public
    constructor Create(Left, Right: TElement;
                       BitReader: TBitReader; BitWriter: TBitWriter);
    destructor Destroy; override;
    procedure Read; override;
    procedure Write; override;
  end;

  THuffmanQueue = class
  private
    FList: TList;
    FBitReader: TBitReader;
    FBitWriter: TBitWriter;
    FCurrent: TElement;
    FRoot: TTree;
  public
    constructor Create(BitReader: TBitReader; BitWriter: TBitWriter);
    destructor Destroy; override;
    procedure Init(CharacterCount: TCharacterCount); // für Kodierung
    procedure Add(Value: Byte; Count: Longword); overload; // für Zeichen
    procedure Add(Tree: TTree); overload; // für Binär-Baum
    procedure BuildHuffmanCodeTree; // für Kodierung
    function GetRoot: TTree;
    function GetCodeAlphabet: TCodeAlphabet; // für Kodierung
    function TestCharacter(ABit: Byte): Boolean; // für Dekodierung
    procedure Read;
    procedure Write;
  end;

function ElementCompare(Item1, Item2: Pointer): Integer;
begin
  if TElement(Item1).FCount > TElement(Item2).FCount then Result := 1
  else if TElement(Item1).FCount = TElement(Item2).FCount then Result := 0
  else Result := -1;
end;

constructor TElement.Create(BitReader: TBitReader; BitWriter: TBitWriter);
begin
  inherited Create;
  Self.FBitReader := BitReader;
  Self.FBitWriter := BitWriter;
end;

function TElement.GetCodeCharacter: TCodeCharacter;

  procedure GetCodeRec(Element: TElement; var CodeChar: TCodeCharacter);
  begin
    if Element.FParent <> nil then
    begin
      GetCodeRec(Element.FParent, CodeChar);
      Inc(CodeChar.Size);
      CodeChar.Code := (CodeChar.Code shl 1) or (Element.FBit and $01);
    end
    else FillChar(CodeChar, SizeOf(CodeChar), 0); // Code = 0;
  end;

begin
  GetCodeRec(Self, Result);
end;

procedure TElement.Read;
begin
  Self.FBit := Self.FBitReader.ReadBit;
end;

procedure TElement.Write;
begin
  Self.FBitWriter.WriteBits(Self.FBit, 1);
end;

constructor TCharacter.Create(Value: Byte; Count: LongWord;
                       BitReader: TBitReader; BitWriter: TBitWriter);
begin
  inherited Create(BitReader, BitWriter);
  Self.FValue := Value;
  Self.FCount := Count;
end;

procedure TCharacter.Read;
begin
  inherited Read;
  Self.FValue := Self.FBitReader.ReadByte;
end;

procedure TCharacter.Write;
begin
  inherited Write;
  Self.FBitWriter.WriteBits(Self.FValue, 8);
end;

constructor TTree.Create(Left, Right: TElement;
                         BitReader: TBitReader; BitWriter: TBitWriter);
begin
  inherited Create(BitReader, BitWriter);
  if (Left = nil) or (Right = nil) then Exit;
  Self.FChildren[0] := Left;
  Self.FChildren[0].FParent := Self;
  Self.FChildren[0].FBit := $00;
  Self.FChildren[1] := Right;
  Self.FChildren[1].FParent := Self;
  Self.FChildren[1].FBit := $01;
  { Addition der Häufigkeitswerte }
  Self.FCount := Self.FChildren[0].FCount + Self.FChildren[1].FCount;
end;

destructor TTree.Destroy;
begin
  Self.FChildren[0].Free;
  Self.FChildren[1].Free;
  inherited Destroy;
end;

procedure TTree.Read;
var
  Bit: Byte;
begin
  inherited Read;
  Bit := Self.FBitReader.ReadBit;
  if Bit = $01
  then Self.FChildren[0] := TCharacter.Create(0, 0, Self.FBitReader, Self.FBitWriter)
  else Self.FChildren[0] := TTree.Create(nil, nil, Self.FBitReader, Self.FBitWriter);
  Bit := Self.FBitReader.ReadBit;
  if Bit = $01
  then Self.FChildren[1] := TCharacter.Create(0, 0, Self.FBitReader, Self.FBitWriter)
  else Self.FChildren[1] := TTree.Create(nil, nil, Self.FBitReader, Self.FBitWriter);
  Self.FChildren[0].FParent := Self;
  Self.FChildren[1].FParent := Self;
  Self.FChildren[0].Read;
  Self.FChildren[1].Read;
end;

procedure TTree.Write;
begin
  inherited Write;
  if Self.FChildren[0] is TCharacter
  then Self.FBitWriter.WriteBits($01, 1)
  else Self.FBitWriter.WriteBits($00, 1);
  if Self.FChildren[1] is TCharacter
  then Self.FBitWriter.WriteBits($01, 1)
  else Self.FBitWriter.WriteBits($00, 1);
  Self.FChildren[0].Write;
  Self.FChildren[1].Write;
end;

constructor THuffmanQueue.Create(BitReader: TBitReader; BitWriter: TBitWriter);
begin
  inherited Create;
  Self.FList := TList.Create();
  Self.FBitReader := BitReader;
  Self.FBitWriter := BitWriter;
  Self.FCurrent := nil;
end;

destructor THuffmanQueue.Destroy;
begin
  TElement(Self.FList.Items[0]).Free;
  Self.FList.Free;
  inherited Destroy;
end;

procedure THuffmanQueue.Init(CharacterCount: TCharacterCount);
var
  I: Integer;
begin
  for I := 0 to 255 do Self.Add(I, CharacterCount[I]); // ineffizent! (sort)
end;

procedure THuffmanQueue.Add(Value: Byte; Count: Longword);
var
  Elem: TCharacter;
begin
  if Count = 0 then Exit;
  Elem := TCharacter.Create(Value, Count, Self.FBitReader, Self.FBitWriter);
  Self.FList.Add(Elem);
  Self.FList.Sort(ElementCompare);
end;

procedure THuffmanQueue.Add(Tree: TTree);
begin
  if Tree = nil then Exit;
  Self.FList.Add(Tree);
  Self.FList.Sort(ElementCompare);
end;

procedure THuffmanQueue.BuildHuffmanCodeTree;
var
  Left: TElement;
  Right: TElement;
begin
  while Self.FList.Count > 1 do
  begin
    Left := TElement(Self.FList.Items[0]);
    Right := TElement(Self.FList.Items[1]);
    Self.FList.Remove(Left);
    Self.FList.Remove(Right);
    Self.Add(TTree.Create(Left, Right, Self.FBitReader, Self.FBitWriter));
  end;
end;

function THuffmanQueue.GetRoot: TTree;
begin
  Result := TTree(Self.FList.Items[0]);
  Self.FCurrent := Result;
  Self.FRoot := Result;
end;

function THuffmanQueue.GetCodeAlphabet: TCodeAlphabet;

  procedure GetCodeAlphabetRec(Element: TElement);
  begin
    if Element is TTree
      then GetCodeAlphabetRec(TTree(Element).FChildren[0]);
    if Element is TCharacter
      then Result[TCharacter(Element).FValue] := Element.GetCodeCharacter;
    if Element is TTree
      then GetCodeAlphabetRec(TTree(Element).FChildren[1]);
  end;

var
  I: Integer;
begin
  for I := 0 to 255 do
    FillChar(Result[I], SizeOf(Result[I]), 0); // Result[] = 0;
  GetCodeAlphabetRec(TElement(Self.FList.Items[0]));
end;

function THuffmanQueue.TestCharacter(ABit: Byte): Boolean;
begin
  if Self.FCurrent is TCharacter
    then Self.FCurrent := Self.FRoot;
  if Self.FCurrent is TTree
    then Self.FCurrent := TTree(Self.FCurrent).FChildren[ABit];
  Result := Self.FCurrent is TCharacter;
end;

procedure THuffmanQueue.Read;
begin
  Self.FList.Clear;
  Self.FList.Add(TTree.Create(nil, nil, Self.FBitReader, Self.FBitWriter));
  Self.GetRoot.Read;
end;

procedure THuffmanQueue.Write;
begin
  if Self.FList.Items[0] = nil then Exit;
  Self.GetRoot.Write;
end;

(*************************)
(* Huffman-Komprimierung *)
(*************************)
procedure HuffmanCompress(Source, Destination: TMemoryStream);
var
  I: Integer;
  BitWriter: TBitWriter;
  HuffmanQueue: THuffmanQueue;
  Size: Integer;
  Index: Byte;
  CharacterCount: TCharacterCount;
  CodeAlphabet: TCodeAlphabet;
begin
  Source.Position := 0;
  Destination.Clear;

  { Grösse des Datenstroms sichern }
  Size := Source.Size;
  Destination.WriteBuffer(Size, SizeOf(Size));

  { Ermittlung der Häufigkeiten der Zeichen }
  for I := 0 to 255 do CharacterCount[I] := 0; // Init Zeichenzähler
  for I := 0 to Source.Size - 1 do // vollständiger Durchlauf erforderlich
  begin
    Source.ReadBuffer(Index, 1);
    Inc(CharacterCount[Index]);
  end;

  { I. Ermittlung und Sicherung des Kodierungsalphabets }
  Source.Position := 0;
  BitWriter := TBitWriter.Create(Destination);
  HuffmanQueue := THuffmanQueue.Create(nil, BitWriter);
  HuffmanQueue.Init(CharacterCount);
  HuffmanQueue.BuildHuffmanCodeTree; // Aufbau des Binär-Baumes
  HuffmanQueue.Write; // Sicherung des Binär-Baumes in Destination-Stream
  BitWriter.Finish; // Abschluss des Header-Teils

  { II. Kodieren der eigentlichen Nachricht }
  CodeAlphabet := HuffmanQueue.GetCodeAlphabet();
  for I := 0 to Size - 1 do
  begin
    Source.Read(Index, 1);
    BitWriter.WriteBits(CodeAlphabet[Index].Code, CodeAlphabet[Index].Size);
  end;
  BitWriter.Finish; // Abschluss des Body-Teils

  Source.Position := 0;
  Destination.Position := 0;
end;

(***************************)
(* Huffman-Dekomprimierung *)
(***************************)
procedure HuffmanDecompress(Source, Destination: TMemoryStream);
var
  BitReader: TBitReader;
  HuffmanQueue: THuffmanQueue;
  Size: Integer;
begin
  Source.Position := 0;
  Destination.Clear;

  { Auslesen der grösse der Ausgangsnachricht }
  Source.Read(Size, SizeOf(Size));

  { I. Auslesen des Kodierungsalphabets als Binär-Baum }
  BitReader := TBitReader.Create(Source);
  HuffmanQueue := THuffmanQueue.Create(BitReader, nil);
  HuffmanQueue.Read;
  BitReader.Finish; // Abschluss des Header-Teils

  { II. Dekodierung der kodierten Nachricht }
  while Size > 0 do
    if HuffmanQueue.TestCharacter(BitReader.ReadBit) then
    begin
      { Nur wenn die Bitschlange als Zeichen des Kodierungsalphabets
        interpretiert werden kann, wird dieses Zeichen in den Zielstrom
        angefügt und Size um eins dezimiert. }
      Destination.WriteBuffer(TCharacter(HuffmanQueue.FCurrent).FValue, 1);
      Dec(Size);
    end;
  BitReader.Finish; // Abschluss des Body-Teils

  Source.Position := 0;
  Destination.Position := 0;
end;

end.
⇑ Kompression und Dekompression: Huffman ⇑
Beispiele Beispiele zu Huffman
Text-Beispiel (Fischers Fritz)
Das folgende Beispiel ist eine Text-Datei; ein Zungenbrecher. Damit die Huffman-Kodierung zu einer guten Kompression führt, sollten möglichst viele gleiche Zeichen im Text vorkommen. Zungenbrecher sind deshalb recht gute Beispiele zur Demonstration.
Klartext (Text)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
000
016
032
048
064
080
096
112

128
144
 46 69 73 63 68 65 72 73  20 46 72 69 74 7A 20 66
69 73 63 68 74 20 66 72  69 73 63 68 65 20 46 69
73 63 68 65 20 46 72 69  73 63 68 65 20 46 69 73
63 68 65 20 66 69 73 63  68 74 20 46 69 73 63 68
65 72 73 20 46 72 69 74  7A 20 46 69 73 63 68 65
72 73 20 46 72 69 74 7A  20 66 69 73 63 68 74 20
66 72 69 73 63 68 65 20  46 69 73 63 68 65 20 46
72 69 73 63 68 65 20 46  69 73 63 68 65 20 66 69

73 63 68 74 20 46 69 73  63 68 65 72 73 20 46 72
69 74 7A
 Fischers Fritz f
ischt frische Fi
sche Frische Fis
che fischt Fisch
ers Fritz Fische
rs Fritz fischt 
frische Fische F
rische Fische fi

scht Fischers Fr
itz
Komprimat (Text)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
00
16
32
48
64
80
 93 00 00 00 01 91 AD 18  C7 8E 9C F5 66 8C 41 69
C7 3E 65 B9 00 17 23 DF  A0 FA CE 8F B9 16 8F FB
91 E8 2E 47 A0 FB 91 E8  2E 47 A3 EE 45 A0 B9 1E
FD 07 D6 74 17 23 DF A0  FA CE 8F B9 16 8F FB 91
E8 2E 47 A0 FB 91 E8 2E  47 A3 EE 45 A0 B9 1E FD
07 D6 70
 •····••·••••f•Ai
•>e•··#••••••·••
••.G••••.G••E••·
•·•t·#••••••·•••
•.G••••.G••E••·•
·•p
Text-Beispiel (Wiener Waschweiber)
Das folgende Beispiel ist eine Text-Datei; ein weiterer Zungenbrecher.
Klartext (Text)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
000
016
032
048
064
080
096
112

128
144
160
176
192
 57 69 72 20 57 69 65 6E  65 72 20 57 61 73 63 68
65 72 77 65 69 62 65 72  20 77 6F 6C 6C 65 6E 20
77 65 69 26 73 7A 6C 69  67 3B 65 20 57 E4 73 63
68 65 20 77 61 73 63 68  65 6E 20 77 65 6E 6E 20
77 69 72 20 77 FC 73 73  74 65 6E 20 77 6F 20 77
61 72 6D 65 73 20 57 61  73 73 65 72 20 77 E4 72
65 20 77 65 6E 6E 20 77  69 72 20 77 FC 73 73 74
65 6E 20 77 6F 20 77 61  72 6D 65 73 20 57 61 73

73 65 72 20 77 E4 72 65  20 77 FC 72 64 65 6E 20
77 69 72 20 57 69 65 6E  65 72 20 57 61 73 63 68
65 72 77 65 69 62 65 72  20 77 65 69 26 73 7A 6C
69 67 3B 65 20 57 E4 73  63 68 65 20 77 61 73 63
68 65 6E
 Wir Wiener Wasch
erweiber wollen 
wei&szlig;e W•sc
he waschen wenn 
wir w•ssten wo w
armes Wasser w•r
e wenn wir w•sst
en wo warmes Was

ser w•re w•rden 
wir Wiener Wasch
erweiber wei&szl
ig;e W•sche wasc
hen
Komprimat (Text)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
000
016
032
048
064
080
096
112

128
 C3 00 00 00 01 9C AE 78  EF CD D6 98 43 34 58 E3
7E 5B EB 32 4E FC 92 0C  65 84 33 3D B7 9E A4 D6
1A 8D 9C E9 62 AB 80 FB  8B F7 CD 85 FF 4C 61 82
CF EF 0A A5 F3 CC D5 67  E6 79 78 FC 26 EB F9 CC
61 AA E9 8C 33 55 99 AA  71 54 84 FA CD 54 B5 74
71 C6 FF A4 E1 54 E3 55  99 AA 71 54 84 FA CD 54
B5 74 71 C6 FF A4 E1 54  E3 55 20 99 9A A7 17 EF
9B 0B FE 98 C3 05 9F DE  15 67 E6 79 78 FC 26 EB

F9 CC 61 AA E9 8C 33 00
 •····••x••••C4X•
~[•2N••·e•3=••••
·•••b••••••••La•
••·••••g•yx•&•••
a•••3U••qT•••T•t
q••••T•U••qT•••T
•tq••••T•U •••·•
•·•••·••·g•yx•&•

••a•••3·
Unrealistisches Beispiel
Das folgende Beispiel ist eine Text-Datei mit 220 a's gefolgt von 2 Blanks gefolgt von 300 b's gefolgt von 2 Blanks gefolgt von 220 c's.

Dieses Beispiel ist recht unrealistisch; derartige Dateien sind selten!
Klartext (unrealistisch)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
000
016
032
048
064
080
096
112

128
144
160
176
192
208
224
240

256
272
288
304
320
336
352
368

384
400
416
432
448
464
480
496

512
528
544
560
576
592
608
624

640
656
672
688
704
720
736
 61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61

61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 61 61 61 61
61 61 61 61 61 61 61 61  61 61 61 61 20 20 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62

62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62

62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62
62 62 62 62 62 62 62 62  62 62 62 62 62 62 62 62

62 62 62 62 62 62 62 62  62 62 20 20 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63

63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63  63 63 63 63 63 63 63 63
63 63 63 63 63 63 63 63
 aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa

aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaa  bb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb

bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb

bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbb

bbbbbbbbbb  cccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc

cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccccccccccc
cccccccc
Komprimat (unrealistisch)
Zeile 00 01 02 03 04 05 06 07  08 09 10 11 12 13 14 15 Text
000
016
032
048
064
080
096
112

128
144
160
176
 E8 02 00 00 46 2C 61 E2  0B 18 AA AA AA AA AA AA
AA AA AA AA AA AA AA AA  AA AA AA AA AA AA AA AA
AA AA AA AA AA AA AA AA  AA AA AA AA AA AA AA AA
AA AA AA AA AA AA AA AA  AA AA AA AA AA AA AA AA
AA D8 00 00 00 00 00 00  00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 36  FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF  FF FF FF FF FF FF FF FF

FF FF FF FF FF FF FF FF  FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF  FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF  FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF  FF FF F0
 •···F,a•··••••••
••••••••••••••••
••••••••••••••••
••••••••••••••••
••··············
················
·······6••••••••
••••••••••••••••

••••••••••••••••
••••••••••••••••
••••••••••••••••
•••••••••••
Startseite   Sitemap   Downloads   Hilfe   Impressum  
Fußnoten
  1. R. M. Fano war der Begründer einer statistischen Theorie der Nachrichtenübertragung.
  2. Samuel Finley Breese Morse (1791-1872), amerikanischer Maler und Erfinder, entwickelte seit 1837 den ersten brauchbaren elektromagnetischen Schreibtelegraphen und dazu das Morsealphabet.
Quellenangabe
  • [INFODUDEN] Duden Informatik: 1993 Auflage2, Bibliographisches Institut & F. A. Brockhaus AG ISBN 3-411-05232-5 Ein Sachlexikon für Studium und Praxis
Startseite < Informatik < Algorithmen < Sortieren Komprimieren < RLE [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Huffman Lempel-Ziv > Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >