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.