ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4440682
Jetzt (Chat):
20 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-
ZFX - KurzartikelDruckversion

Huffman Codes
Der Kurzartikel von Thomas D. aka spok

© Copyright 2001 [whole tutorial] by Thomas D. aka spok
Die Texte der Tutorials unterliegen dem Copyright und dürfen ohne schriftliche Genehmigung vom Author weder komplett noch auszugsweise vervielfältigt, auf einer anderen Homepage verwendet oder in sonst einer Form veröffentlicht werden. Die zur Verfügung gestellten Quelltexte hingegen stehen zur freien Weiterverwendung in Software Projekten zur Verfügung.
Die Quelltexte dieses Tutorials werden auf einer "as is" Basis bereit gestellt. Der Autor übernimmt keinerlei Garantie für die Lauffähigkeit der Quelltexte. Für eventuelle Schäden die sich aus der Anwendung der Quelltexte ergeben wird keinerlei Haftung übernommen.


Inhalt:


1. Einleitung
2. Theorie
3. Praxis
4. Anmerkungen


1. Einleitung

blablablablup


2. Theorie


Wollte man die Einleitung in eine Datei speichern, so benoetigt man fuer jedes Zeichen 1 Byte (8 Bit). Es sind 13 Zeichen, d.h. man muss 13 Bytes bzw. 104 Bits speichern. Ist das nicht ein wenig viel? Wenn man genauer hinschaut wird man feststellen, dass die Einleitung ja nur aus 5 verschiedenen Zeichen besteht. Um diese zu unterscheiden, muessten 3 Bits genuegen. 2^3 macht naemlich 8 und das ist groesser als 5. Wenn wir also unsere Zeichen wie folgt codieren, dann braeuchten wir für eben diese nur noch 39 Bits (5 Bytes).

b = 000
l = 001
a = 010
u = 011
p = 100

Gehts nicht vielleicht noch besser?
Da war doch noch was. Hamming vielleicht? Neeee Hamming warn doch die fehlerkorrigierenden Dinger.
hmm...............zur Ueberschrift schiel
Richtig son Huffmancode kanns vielleicht besser. Also der Trick besteht darin, die einzelnen Zeichen so zu codieren, dass oft vorkommende weniger Bits bekommen als seltene Zeichen. Dann machen wir das gleich mal.


b=01  kommt 4 mal vor
l=00  kommt 4 mal vor
a=10  kommt 3 mal vor
u=111 kommt 1 mal vor
p=110 kommt 1 mal vor

Es ist wichtig, dabei darauf zu achten, dass keine Bitkombination eines Zeichens der Anfang eines anderen Zeichens ist, damit man das ganze auch wieder decodieren kann. Wenn wir den ganzen Spass also so codieren, kommen wir auf 28 Bits (4 Bytes). Damit ist die Theorie auch schon fast abgehakt. Bleibt nur noch zu klaeren, wie man algorithmisch auf diese Bitkombinationen kommt. Zunaechst einmal muss man zaehlen wie oft ein Zeichen vorkommt. Dann nimmt man sich die zwei Zeichen, die am seltensten vorkommen, fasst sie zusammen, und addiert ihre Haeufigkeiten.

Das macht man jetzt noch ein paar mal bis ein schoener Binaerbaum entsteht.

Um jetzt festzustellen, welche Bits für welches Zeichen stehen, geht man einfach von der Wurzel aus zum Zeichen und liest an den Kanten die Bits ab.
soviel zur Theorie.


3. Praxis


Wie fangen wir jetzt an, das eben Gelernte in c++ Code umzusetzen?
Ganz einfach zuerst mal die Datenstrukturen. Beginnen wir also mit nem Element fuer unseren Binaerbaum.

struct baumElement { baumElement* Bit0; baumElement* Bit1; char Zeichen; bool Blatt; };

Die Pointer sollten eigentlich klar sein. Ins Zeichen kommt das Zeichen welches das Baumelement repraesentieren soll. Das Blatt sagt lediglich, ob es sich bei diesem Element um ein Blatt handelt oder um einen inneren Knoten.
Und weil das grad so lustig ist, bauen wir gleich noch eine sogenannte doppelt verkettete Liste. (eine einfache Liste wuerde es auch tun, aber aktuelle Speicherpreise laden geradezu dazu ein, Speicherplatz zu verschwenden).

struct listenElement
{
  listenElement* next;
  listenElement* last;
  baumElement*   element;
  int anzahl;
};

Diese Liste soll das Anlegen des Huffmanbaumes erleichtern. Jetzt noch ein paar Variablen:

int   haeufigkeiten[256];
int   anzBits;
int   Bits[8];
FILE* lploadFile;
FILE* lpstoreFile;
char  aktuell;
int   bitNummer;
baumElement* Head;

Dabei soll &quothaeufigkeiten[i]" angeben, wie oft i im Quelltext vorkommt. Zu &quotanzBits" und &quotBits" sag ich später noch was. &quotaktuell" ist so ne art Puffer, da man leider nicht bitweise sondern nur byteweise Dateioperationen ausführen kann. &quotbitNummer" zeigt dabei auf die Positon in &quotaktuell" von der das naechste Bit gelesen bzw. auf die das naechste Bit geschrieben werden soll. Und &quotHead" ist wie sollte es auch anders sein, die Wurzel des Huffmanbaums. Jetzt kommen wir auch schon zum ersten Stück ausfuehrbarem Code :-))

//////////////////////////////////////////////////////////////////////
// lese char
//////////////////////////////////////////////////////////////////////
char Huffman::readChar()
{
  baumElement* aktuell = Head;
  while((*aktuell).Blatt==0)
  	if(readBit()) aktuell = (*aktuell).bit1;
	else          aktuell = (*aktuell).bit0;

  return (*aktuell).Zeichen;
}

readChar() soll aus unserem codierten File ein Char lesen. Wie das geht haben wir ja bereits im Therorieteil gesehen. Man geht einfach von der Wurzel, aus liest ein Bit, wenn dieses Bit 1 ist gehen wir die 1 Kante entlang, und wenn es eine 0 ist, nehmen wir halt die 0 Kante. Das machen wir bis wir an nem Blatt angekommen sind und geben dann lediglich das entsprechende Zeichen zurueck.

//////////////////////////////////////////////////////////////////////
// lese Bit
//////////////////////////////////////////////////////////////////////

int Huffman::readBit()
{
  if(bitNummer==8)
  {
    aktuell = getc(lploadFile);
	bitNummer=0;
  }
  int a = aktuell >> bitNummer++; 
  return a&1;
}

readBit() soll lediglich das naechste Bit aus dem loadFile zurueckgeben. bitNummer muss dabei eines aus den 8 Bit in aktuell auswaehlen, zurueckgeben und sich um eins erhoehen. Sollte es dabei vokommen, dass bitNummer auf das 9. Bit zeigt, muss nachgeladen werden.
Nun das gleiche fürs schreiben:

//////////////////////////////////////////////////////////////////////
// schreibe char
//////////////////////////////////////////////////////////////////////

void Huffman::writeChar(char Zeichen)
{
  tiefenSuche(Head, Zeichen, 0);

  for(int i = 0; i&ltanzBits; i++)
    writeBit(Bits[i/32] >> (i%32) );
}

writeChar() bekommt ein char uebergeben, und schreibt dieses huffmancodiert ins storeFile. Wir wissen aber leider nicht, wo das zu schreibende Zeichen im Huffmanbaum steht. Es bleibt uns also nichts anderes uebrig als eben dieses zu suchen. tiefensuche(...) manpuliert dabei das int Array Bits. Dort stehen nach der Tiefensuche die zu codierenden Bits drin. Im schlimmsten Fall koennen das fuer ein Zeichen 255 Bits sein. anzBits sagt wie viele von diesen 255 Bits benoetigt werden.
Auf writeBit will ich nicht weiter eingehen, da es nichts Neues bringt. Kommen wir also gleich zur tiefensuche.

//////////////////////////////////////////////////////////////////////
// char im Baum suchen
//////////////////////////////////////////////////////////////////////

int Huffman::tiefenSuche(baumElement* knoten, char z, int tiefe)
{
  if((*knoten).Blatt)
  {
    if((*knoten).Zeichen==z)     // juhu gefunden :-))
    {
      anzBits = tiefe;
      return 1;
    }
    return 0;                    // das war wohl nix :-(
  }

  if(tiefenSuche((*knoten).bit0, z, tiefe+1))
  {
    int dummy = Bits[tiefe >> 5];// (tiefe%32)tes Bit von Bits[tiefe/32] löschen
    _asm   mov  eax,   dummy
    _asm   mov  ebx,   tiefe
    _asm   and  ebx,   31
    _asm   btr  eax,   ebx
    _asm   mov  dummy, eax
    Bits[tiefe >> 5] = dummy;
    return 1;
  }

  if(tiefenSuche((*knoten).bit1, z, tiefe+1))
  {
    Bits[tiefe >> 5] |= 1 << (tiefe & 31);
    return 1;
  }

  return 0;
}

Wenn man ein wenig mit Baeumen herumspielt, wird man schnell feststellen, dass man mit ihnen sehr schoene rekursive Programme schreiben kann (ich verweise hier auf die noch folgende Methode loesche()). Also was passiet? Wir bekommen einen Knoten, ein Zeichen und die aktuelle Baumtiefe uebergeben. Wenn unser Knoten das zu suchende Zeichen bereits enthaelt bleibt nichts weiter zu tun als anzBits mit unserer tiefe zu belegen. Dann fragen wir uns selber, ob sich das zu suchende Zeichen im Bit0-Zweig befindet. Ist das der Fall, so wissen wir, dass das Bit an der Stelle tiefe eine 0 ist. Also loeschen wir noch dieses Bit, und wir koennen zurueck gehen. (an der Stelle sei mir das bisschen asm verziehen. Ich habs wirklich ohne versucht. Leider ohne Erfolg. Der ! Operator scheint irgendwie nur aufs niederwertigste Bit zu wirken) Die gleiche Ueberlegung macht man noch fuer den Bit1-Zweig und schon ist die naechste Methode fertig.
Noch ne Methode um unseren Baum komplett zu loeschen:

//////////////////////////////////////////////////////////////////////
// Datenstruktur löschen!!!
//////////////////////////////////////////////////////////////////////

void Huffman::loesche(baumElement* kopf)
{
  if(!(*kopf).Blatt)
  {
    loesche((*kopf).bit0);
    loesche((*kopf).bit1);
  }
  delete kopf;
  kopf = NULL;
}

Das sieht doch jetzt wirklich elegant aus, oder?
Wenn wir kein Blatt sind, loeschen wir einfach den Bit0-Zweig, dann den Bit1-Zweig und schliesslich uns selber. Wer jetzt glaubt wir haetten vieleicht ein paar Elemente vergessen, der sollte sich ruhig mal ein Blatt Papier nehmen und nen kleinen Baum von Hand loeschen.
Was fehlt uns jetzt eigentlich noch fuer uneren Huffmancode?
Stimmt, wir haben den HuffmanBaum ja noch gar nicht aufgebaut.

bool Huffman::baueBaum()
{
  if(Head) loesche(Head);

  listenElement* kopf       = NULL;
  listenElement* alt        = NULL;
  listenElement* kleinster1 = NULL;
  listenElement* kleinster2 = NULL;
  baumElement* Element = NULL;

  listenElement* neul  = NULL;
  baumElement* neub = NULL;
  for(int i=0; i<256; i++)           // liste erzeugen
  {
    if(haeufigkeiten[i]!=0)
    {
      neub = new baumElement;
      neul = new listenElement;

      (*neub).Zeichen = (char) i;
      (*neub).Blatt = 1;

      (*neul).anzahl  = haeufigkeiten[i];
      (*neul).element = neub;

      if(kopf==NULL)
      {
        kopf = neul;
        (*neul).next = kopf;
	(*neul).last = kopf;
      }
      else{
        (*neul).next = kopf;
        (*neul).last = (*kopf).last;

	(*(*kopf).last).next = neul;
	(*kopf).last = neul;
      }
    }
  }

  while((*kopf).next!=kopf)    // baue Baum endlich!
  {
    alt = kopf ;
    if((*kopf).anzahl < (*(*kopf).next).anzahl)
    {
	  kleinster1 = kopf;  kleinster2 = (*kopf).next;
    }
    else
    {
      kleinster2 = kopf;  kleinster1 = (*kopf).next;
    }

    do                          // die zwei kleinsten elemente suchen!!!
    {
      alt = (*alt).next;
      if( (*alt).anzahl < (*kleinster1).anzahl )
      {
	kleinster2 = kleinster1;
	kleinster1 = alt;
      }
    }while(alt!=kopf);

    neub = new baumElement;

    (*neub).bit0 = (*kleinster1).element;
    (*neub).bit1 = (*kleinster2).element;
    (*neub).Blatt = 0;
    (*kleinster1).anzahl += (*kleinster2).anzahl;
    (*kleinster1).element = neub;

    if(kleinster2==kopf) kopf = kleinster1;

    (*(*kleinster2).last).next = (*kleinster2).next;
    (*(*kleinster2).next).last = (*kleinster2).last;

    delete kleinster2;
    kleinster2 = NULL;
  }

  Head = (*kopf).element;

  delete kopf;
  return 1;
}

Zuerst erstellen wir uns dazu eine doppelt verkettete Liste. Das passiert in der ersten for Schleife. Dabei werden fuer jedes Zeichen, welches in unserer Quelle vorkommt, ein baumElement und ein listenElement angelegt. Ins listenElement kommt die Haeufigkeit des Zeichens. Und der Pointer &quotelement" wird aufs baumElement gelenkt. Dieses widerum bekommt hier lediglich gesagt fuer welches Zeichen es steht. Alle uebrigen Anweisungen verzeigern unsere Liste so, dass zum Schluss eine schoene doppelt verkettete cirkulaere Liste dabei entsteht.
Jetzt muessen wir jeweils die zwei seltensten Elemente suchen und zusammenfuegen. Das macht die folgende while Schleife. Wir definieren uns also zwei listenElemente kleinster1 und kleinster2, lassen einen von ihnen auf den Kopf zeigen, und den anderen auf seinen Nachfolger next. Die Reihenfolge ist dabei wichtig, weil wir sonst nach der Suche nicht garantieren koennten, das kleinster1 und kleinster2 auf zwei verschieden Elemente zeigen. Ein zusaetzlicher Zeiger &quotalt" laeuft jetzt einmal durch die gesamte Liste, und belegt kleinster1 bzw. kleinster2 neu wenn er ein selteneres Element findet. Was machen wir jetzt mit den seltensten Elementen? Richtig, wir fuehren ein neues Baumelement ein, welches natuerlich kein Blatt ist. Dann belegen wir seine Pointer mit den elementen von kleinster1 bzw. kleinster2. Jetzt ist eines der beiden listenElemente ueberfluessig geworden. Also fuegen wir es aus der Liste aus und loeschen es. Dem anderen muessen wir noch sagen, dass das neue baumElement sein neues element ist. Da in jedem Schleifendurchlauf die Liste um genau ein Element kleiner wird, koennen wir sicher sein, das irgendwann nur noch der Kopf uebrig bleibt.
In meiner Klasse gibt es jetzt noch ein paar weitere Methoden. Ich werde jetzt nicht mehr auf deren Implementierung eingehen. Schaut sie euch einfach an. Aber deren Funktionalitaet will ich noch kurz erwaehnen.
Da sind zunaechst die zwei Methoden readHeader() und writeHeader() diese sollen einen &quotHeader" in eine Datei schreiben bzw. lesen. In diesen Header kommt die Haeufigkeitsverteilung und die Anzahl der zu speichernden Bits.
Dann gibts da noch die Methoden writeFile(char File[], char* daten, anzahle) bzw. char* readFile(char File[], int* anzahl). Erstere soll anzahl bytes aus daten huffmancodiert in die Datei File schreiben.
Zweitere geht genau umgekehrt vor.
Zu guter letzt noch encode(char quelle[], char ziel[]) bzw. decode(char quelle[], char ziel[]) diese lesen von der Datei quelle und schreiben in die Datei ziel. Dabei wird (de)codiert.

quellcode           :-))


4. Anmerkungen

Was bringt der Huffman jetzt eigentlich?

Die Kompressionsraten des Huffmancode haengen natuerlich stark vom Einsatzgebiet ab. Text sollte sich im allgemeinen recht gut komprimieren lassen. Mit ner zip-Datei wird man wohl weniger Glueck haben. Die Kompressionsraten werden besser je weiter man von einer Gleichverteilung der bytes wegkommt. Die Huffmancodierte Datei hat im besten Fall noch 1/8 der Orginaldatei.

Als letztes sei noch erwaehnt, dass der hier vorgestellte Code alles andere als optimal ist. Wenn man naemlich z.B. auf die Tiefensuche verzichtet, spart man ein Vielfaches an Rechenzeit. Wie das geht, sollte sich der Leser selber klar machen.

Ich hoffe, ich konnte ein wenig Licht ins Dunkle bringen.

cu
ThomasD

Feedback: udq0@rz.uni-karlsruhe.de

Informationen: " ); ?> " ); ?> " ); ?> " ); ?>
WWW :$wwwtitel
Data:Projektdateien
Mail:$author ($email)
Nick:$nick