Am Bei­spiel der Co­die­rung des Tex­tes «MIS­SIS­SIP­PI» soll der Huffman-​Algorithmus er­läu­tert wer­den.

Zu­erst zählt man, wie oft jedes Zei­chen im Text vor­kommt und er­stellt eine Häu­fig­keits­ta­bel­le.

Nun geht es darum, einen Co­die­rungs­baum zu er­stel­len. Die Häu­fig­kei­ten der Buch­sta­ben bil­den je einen Kno­ten. Die Häu­fig­keit steht im Kno­ten, der Buch­sta­ben dar­un­ter. Die Kno­ten wer­den nach auf­stei­gen­der Häu­fig­keit sor­tiert:



Nun wer­den die zwei Kno­ten mit den kleins­ten Häu­fig­kei­ten an einen neuen Kno­ten an­ge­hängt. Der neue Kno­ten ent­hält die sum­mier­te Häu­fig­keit der ur­sprüng­li­chen Kno­ten:



Das wird wie­der­holt, bis alle Kno­ten mit­ein­an­der ver­bun­den sind. Wenn zwei Kno­ten die glei­che Häu­fig­keit haben, spielt es keine Rolle, wel­cher ge­wählt wird:





Wenn der Baum fer­tig ist, wer­den alle Äste, wel­che nach links zei­gen, mit einer «0» mar­kiert, alle die nach rechts zei­gen mit einer «1».





Bei der Kom­pres­si­on wird ver­sucht, Daten ef­fi­zi­en­ter ab­zu­spei­chern, so dass we­ni­ger Spei­cher­platz be­legt wird. Ge­ra­de beim Über­tra­gen von Daten – z.B. Streamen eines Films, oder gros­ser Da­tei­en– ist dies enorm wich­tig. Wir un­ter­schei­den zwei grund­sätz­lich un­ter­schied­li­che Arten von Kom­pres­si­on:

Bei der ver­lust­frei­en Kom­pres­si­on, kön­nen die Daten voll­stän­dig re­kon­stru­iert wer­den. D.h. es han­delt sich – wie bei der Co­die­rung – um eine ein­deu­ti­ge und um­kehr­ba­re Ab­bil­dung.



An­wen­dung

Über­all dort, wo kein Ver­lust pas­sie­ren darf – ein Pro­gramm läuft nicht mehr, wenn Be­feh­le feh­len!Bil­der, Audio und Video wäh­rend der Pro­duk­ti­on und Be­ar­bei­tung – sonst würde bei jedem Spei­chern (also Co­die­ren) die Qua­li­tät ab­neh­men.



Bei­spie­le

flac – Sound

zip, rar – Da­tei­en

gif, png, raw, psd, xcf – Gra­fik

Hier wer­den beim Spei­chern Daten ent­fernt. Da­durch kann ent­spre­chend viel Spei­cher ge­won­nen wer­den, al­ler­dings las­sen sich die Original-​Daten nur noch teil­wei­se re­kon­stru­ie­ren. Es wird ver­sucht vor allem nicht wich­ti­ge Daten weg­zu­las­sen.



An­wen­dung

beim Fer­tig­stel­len von Me­di­en, also wenn diese nicht mehr wei­ter be­ar­bei­tet wer­den sol­len



Bei­spie­le

mp3 – Sound

jpg – Gra­fik

mp4, avi, mov – Video

David Huff­man hat 1952 ein Ver­fah­ren ent­wi­ckelt, mit wel­chem Zei­chen platz­spa­ren­der co­diert wer­den kön­nen. Seine Idee ist, dass Zei­chen, wel­che häu­fig im Text vor­kom­men, einen kür­ze­ren Code er­hal­ten, als Zei­chen, wel­che sel­ten im Text vor­kom­men.



Code­baum

Ein Code­baum ist eine Struk­tur mit einem Start­kno­ten. Von die­sem aus geht es ent­we­der nach links oder rechts unten wei­ter. Eine 0 im Code be­deu­tet nach links gehen, eine 1 nach rechts gehen. Wenn ein Kno­ten mit einem Buch­sta­ben er­reicht wird, hat man ein Zei­chen de­co­diert, man be­ginnt wie­der von vorne.

Wie wir be­reits ge­lernt haben, kön­nen Bil­der als Ras­ter be­stehend aus ein­zel­nen Pixel ge­spei­chert wer­den. Das Bild unten be­steht aus 195 Pixel in 13 Zei­len und 15 Spal­ten. Die­ses Bild be­sitzt zwei Farb­wer­te, hell oder dun­kel. Ein Pixel kann in die­sem Fall mit einem Bit, einer Eins oder einer Null ge­spei­chert wer­den. Das Bild kann durch das fol­gen­de Bit­mus­ter be­schrie­ben wer­den:

Eine kom­pak­te­re Art der Co­die­rung ist die Lauflängen-​Methode. Dabei wird ge­zählt wie viele

Pixel der glei­chen Farbe auf­ein­an­der fol­gen. Das obere Bild be­ginnt mit 16 dunk­len Pixel, dann fol­gen 12 helle, da­nach wie­der 4 dunk­le, usw. Eine Lauf­län­gen Co­die­rung des obi­gen Bil­des sieht wie folgt aus:

Zur De­co­die­rung des Codes und für das Zeich­nen des Bil­des wird die An­zahl Spal­ten be­nö­tigt, wel­che das Bild hat. Dies ist der erste Wert der hier ge­wähl­ten Lauf­län­gen Co­die­rung da­nach fol­gen ab­wechs­lungs­wei­se die An­zahl hel­ler und dunk­ler Pixel. In die­sem Fall be­ginnt es mit 0 hel­len Pixel, dann 16 dunk­len Pixel, dann 12 hel­len, u.s.w.

David Huff­man hat 1952 ein Ver­fah­ren ent­wi­ckelt, mit wel­chem Zei­chen platz­spa­ren­der co­diert wer­den kön­nen. Seine Idee ist, dass Zei­chen, wel­che häu­fig im Text vor­kom­men, einen kür­ze­ren Code er­hal­ten, als Zei­chen, wel­che sel­ten im Text vor­kom­men.

Ein Code­baum ist eine Struk­tur mit einem Start­kno­ten. Von die­sem aus geht es ent­we­der nach links oder rechts unten wei­ter. Eine 0 im Code be­deu­tet nach links gehen, eine 1 nach rechts gehen. Wenn ein Kno­ten mit einem Buch­sta­ben er­reicht wird, hat man ein Zei­chen de­co­diert, man be­ginnt wie­der von vorne.