Kom­pres­si­on

Ein­lei­tung

Be­grif­fe⁷

• In­for­ma­ti­on: In­for­ma­ti­on um­fasst eine Nach­richt zu­sam­men mit ihrer Be­deu­tung für den Emp­fän­ger
• Daten: In­for­ma­tio­nen wer­den in di­gi­ta­le Daten um­ge­wan­delt, um von Ma­schi­nen wei­ter­ver­ar­bei­tet wer­den zu kön­nen.
• Co­die­rung: Wie die In­for­ma­ti­on/Daten dar­ge­stellt wer­den.
• Code: Die (bi­nä­re) Dar­stel­lung der Daten. Ach­tung: nicht zu ver­wech­seln mit Ver­schlüs­se­lung!
• Code-/Wort­län­ge: die (bi­nä­re) Länge eines Codes. Da hier le­dig­lich Texte co­diert wer­den, ist es sinn­voll, den Be­griff „Code­län­ge“ zu ver­wen­den und „Wort(länge)“ kom­plett zu mei­den! Diese Größe wer­den wir als Ver­gleichs­maß bei der Kom­pri­mie­rung ver­wen­den.
• Zei­chen: ein ein­zel­ner Buch­sta­be der Daten, d.h. des zu co­die­ren­den Tex­tes. • Bi­när­baum: eine Baum­struk­tur, bei der jeder Kno­ten genau 2 (Wur­zel- bzw. in­ne­rer Kno­ten) oder 0 (Blatt) Kind­kno­ten hat.
• Ent­zif­fer­bar­keit: Aus einem Code las­sen sich ein­deu­tig wie­der die Daten/In­for­ma­ti­on her­stel­len.
• Prä­fix­frei­heit bzw. Fano-Be­din­gung: kein Code eines be­lie­bi­gen Zei­chens ist der An­fang des Codes eines an­de­ren Zei­chens.

Ziel

• 3.​3.​1.​1 (6) Merk­ma­le von Co­die­run­gen (unter an­de­rem Ent­zif­fer­bar­keit, Prä­fix­frei­heit, feste/va­ria­ble Bit­län­ge) er­läu­tern
• 3.​3.​1.​1 (7) das Huff­man­ver­fah­ren als Bei­spiel für ein ver­lust­frei­es Daten­kom­pres­sions­ver­fahren er­läu­tern und die Co­die­rung durch Er­zeu­gung eines Huff­man­baums sowie De­co­die­rung von Hand durch­füh­ren.

Di­dak­ti­sche An­mer­kun­gen

• Als Ein­stieg ggf. zu­erst einen Schätz­wert ab­ge­ben las­sen, wie viel un­kom­pri­mier­tes Vi­deo­ma­te­ri­al sich auf eine Blu­Ray spei­chern ließe.
• In­for­ma­ti­ons­ge­halt nach Shan­non ist nicht In­halt des Bil­dungs­pla­nes!
• Hier wird das LZW-Ver­fah­ren zu­nächst mit einer fest de­fi­nier­ten Code­län­ge vor­ge­stellt. Es funk­tio­niert auch mit einer va­ria­blen Bit­län­ge, die am Ende als Aus­blick dar­ge­stellt wird.

Ein­füh­rung

Bei den heu­ti­gen Spei­cher­kos­ten könn­te man sich immer mehr fra­gen, ob denn Kom­pres­si­on über­haupt noch not­wen­dig ist. Die Ant­wort lau­tet ganz klar „JA“, denn das lässt sich mit­hil­fe eines ein­fa­chen Re­chen­bei­spiels ganz ein­fach zei­gen:

An­ge­nom­men wir wol­len einen Film auf eine Blu­Ray mit 50GB Spei­cher­platz bren­nen. (Al­ter­na­tiv könn­te man hier auch eine Fest­plat­te mit z.B. 4TB Spei­cher­platz neh­men). Wie lang darf ein Film in 4K-Auf­lö­sung, 24Bit Farb­tie­fe und 60Hz Bild­ra­te dafür höchs­tens sein?

• 4K-Auf­lö­sung: 3840x2160 = 8.294.400 Pixel
• je­weils 24 Bit: = 24.883.200 Byte = 24300 kiB = 23,73 MiB pro Bild
• 60 Bil­der pro Se­kun­de: = 1.423,83 MiB/s = 1,39 GiB pro Se­kun­de

Das würde be­deu­ten, auf eine Blu­Ray-Disk pas­sen le­dig­lich knapp 36 Se­kun­den un­kom­pri­mier­tes Bild­ma­te­ri­al. Auf eine 4TB-Fest­plat­te le­dig­lich eine drei­vier­tel Stun­de! Ins­be­son­de­re wenn man dann auch Filme über das mo­bi­le Da­ten­netz an­schaut, sieht man an die­ser Rech­nung sehr ein­drück­lich, dass es auch in der heu­ti­gen Zeit noch stark auf gute Kom­pres­si­on an­kommt.

In­for­ma­ti­ons­ge­halt

Der In­for­ma­ti­ons­ge­halt einer Nach­richt ist eine sta­tis­ti­sche Größe. Sie wurde von Clau­de Shan­non erst­mals for­ma­li­siert⁸ . Der In­for­ma­ti­ons­ge­halt eines ein­zel­nen Zei­chens x ist de­fi­niert als:

I(x)=−log_w(p_x)

Wobei p_x die Auf­tritts­wahr­schein­lich­keit des Zei­chens x be­zeich­net und w die Mäch­tig­keit des Ziel­al­pha­bets. Bei einer bi­nä­ren Co­die­rung ist also w = 2.

Ver­ein­facht ge­sagt: je öfter ein Zei­chen auf­tritt, desto we­ni­ger In­for­ma­ti­on steckt ist die­sem.

Bei­spiel: in der deut­schen Spra­che kom­men be­son­ders häu­fig z.B. Vo­ka­le vor. Diese wer­den aber haupt­säch­lich als Bin­de­glie­der zwi­schen Kon­so­nan­ten be­nutzt. Die ei­gent­li­che In­for­ma­ti­on steckt im We­sent­li­chen in den Kon­so­nan­ten. Dies kann man selbst aus­pro­bie­ren, indem man aus einem Text zu­nächst alle häu­fi­gen Buch­sta­ben ent­fernt und im zwei­ten Schritt nur diese übrig lässt. Im Bei­spiel wur­den die Vo­ka­le und zu­sätz­lich die Buch­sta­ben „m“ und „s“ ent­fernt, damit bei bei­den Ver­sio­nen un­ge­fähr ähn­lich viele Buch­sta­ben übrig blei­ben:

Man kann daran sehen, dass beim lin­ken Text kein In­halt er­kenn­bar, der rech­te Text aber mit etwas Mühe les­bar ist. Der Voll­stän­dig­keit hal­ber noch der kom­plet­te Text:

Wer rei­tet so spaet durch Nacht und Wind?
Es ist der Vater mit sei­nem Kind;
Er hat den Kna­ben wohl in dem Arm,
Er fasst ihn si­cher, er hält ihn warm.

Re­duk­ti­on der Da­ten­men­ge bei Er­hal­tung der In­for­ma­ti­on

Ziel der Kom­pres­si­on ist also, die Co­die­rung da­hin­ge­hend an­zu­pas­sen, dass die Da­ten­men­ge ver­klei­nert wird und dabei keine In­for­ma­ti­on ver­lo­ren geht. Das kann auf un­ter­schied­li­che Arten pas­sie­ren:

1. En­tro­pie­co­die­rung: Op­ti­mie­rung, so dass oft vor­kom­men­de Zei­chen we­ni­ger Spei­cher­platz ver­wen­den als we­ni­ger oft vor­kom­men­de Zei­chen. → Huff­man-Co­die­rung
2. Wör­ter­buch­co­die­rung: Wie­der­ho­len­de Zei­chen­fol­gen in einem Wör­ter­buch spei­chern und dar­auf ver­wei­sen. → LZW-Co­die­rung
3. Lau­f­län­gen­co­die­rung: mehr­fach nach­ein­an­der vor­kom­men­de Zei­chen(fol­gen) wer­den ab­ge­kürzt.

Ent­zif­fer­bar­keit, Fano-Be­din­gung, Prä­fix­frei­heit

Eine Co­die­rung heißt ein­deu­tig ent­zif­fer­bar, wenn für jeden Code nur eine ein­deu­ti­ge Nach­richt exis­tiert. Das be­deu­tet, aus einem Code darf – auch ohne Zu­hil­fe­nah­me von Se­man­tik und Kon­text – le­dig­lich eine mög­li­che Nach­richt ent­ste­hen.

Bei­spiel für nicht ein­deu­tig ent­zif­fer­bar: Mor­se­co­de:

• ∙ − − ∙ ∙ ∙ − ∙ − ∙ = ABC
• ∙ − − ∙ ∙ ∙ − ∙ − ∙ = EGFN

Bei Mor­se­co­de be­nö­tigt man des­halb neben den bei­den Zei­chen kurz und lang auch noch die Pause, um ein­zel­ne Buch­sta­ben von­ein­an­der ab­gren­zen zu kön­nen.

Das Pro­blem hier­bei lässt sich di­rekt er­ken­nen, da schon die Co­die­rung für A = ∙ − be­reits eine Zu­sam­men­set­zung aus E = ∙ und T = − sein könn­te. Der Be­ginn der Co­die­rung für A ent­spricht der Co­die­rung von E.

Ver­all­ge­mei­nert kann man des­halb sagen: damit eine Co­die­rung ent­zif­fer­bar ist, darf kein Code eines Zei­chens iden­tisch mit dem An­fang des Codes eines an­de­ren Zei­chens sein. Man spricht des­halb auch von Prä­fix­frei­heit, bzw. der so­gen­nann­ten Fano-Be­din­gung.

Huff­man-Co­die­rung: Ein­füh­rung⁹

Die Huff­man-Co­die­rung funk­tio­niert prin­zi­pi­ell auch mit Bi­när­da­ten, zum bes­se­ren Ver­ständ­nis bzw. Über­sicht­lich­keit wird das Ver­fah­ren hier le­dig­lich mit Tex­ten vor­ge­stellt.

For­mal han­tie­ren wir also mit:

• Die Länge des Tex­tes um­fasst M Zei­chen, davon n un­ter­schied­li­che Zei­chen.
• Ein­zel­ne Buch­sta­ben des Tex­tes. All­ge­mein nennt man diese „Sym­bo­le“ und be­zeich­net diese mit s₁, s₂,...,s_n, Man be­trach­tet dabei nur Sym­bo­le, die im Text wirk­lich auf­tre­ten. Bei Bi­när­da­ten würde man z.B. ein­zel­ne Bytes als Sym­bo­le nut­zen.
• Die Wahr­schein­lich­keit pi eines Sym­bols im Text be­rech­net man mit
  
• Die Wort­län­ge eines Sym­bols si wird mit l_i be­zeich­net.
• Die durch­schnitt­li­che Wort­län­ge er­gibt sich dann aus
  

Ziel der Kom­pres­si­on ist, diese durch­schnitt­li­che Wort­län­ge zu mi­ni­mie­ren. Man kann so­fort er­ken­nen, dass die­ses Op­ti­mum genau dann er­reicht wird, wenn die häu­fi­ger vor­kom­men­den Buch­sta­ben (p_i also grö­ßer) eine kür­ze­re Wort­län­ge be­kom­men (l_i also klei­ner).

Sor­tiert man die Sym­bo­le s₁, s₂,...,s_n auf­stei­gend nach Häu­fig­keit, dann gilt p₁≤ p₂≤ ... ≤ p_n. Dann soll gel­ten l₁≥ l₂≥ ... ≥ l_n.

Huff­man-Co­die­rung: Al­go­rith­mus

Um diese Be­din­gun­gen zu er­rei­chen baut man den Code für die ein­zel­nen Zei­chen von hin­ten her auf. Man fasst immer die zwei Sym­bo­le mit der ge­rings­ten Häu­fig­keit zu einem neuen Sym­bol zu­sam­men. Gra­fisch kann man sich das als Bi­när­baum vor­stel­len, der von den Blät­tern her zur Wur­zel „wächst“.

Bei­spiel:¹⁰ Wir be­trach­ten die Buch­sta­ben-/Sym­bol­fol­ge „ADBCB­DBCBD“

1. Wir zäh­len die ein­zel­nen Sym­bo­le:

2. Die zwei Sym­bo­le mit den we­nigs­ten Vor­kom­men („A“ und „C“) fas­sen wir zu einer Grup­pe zu­sam­men:

3. Die neue Grup­pe hat also eine ab­so­lu­te Häu­fig­keit von 3 und wird als ge­sam­tes wie­der in die Sym­bol­lis­te auf­ge­nom­men. Im fol­gen­den wer­den also nur die blau­en Sym­bo­le bzw. Sym­bol­grup­pen be­trach­tet.
4. Er­neut neh­men wir die zwei (blau­en) Sym­bo­le mit der kleins­ten Häu­fig­keit (die eben er­zeug­te Grup­pe „AC“ sowie „D“)

5. Wie­der­ho­le den Vor­gang so oft, bis nur noch eine ein­zel­ne Grup­pe mit allen vor­han­de­nen Sym­bo­len exis­tiert:

6. Er­zeu­ge den Bi­när­code für jedes ein­zel­ne Sym­bol, indem der Pfad von oben nach unten durch­ge­gan­gen wird. Für jeden Weg in die eine Rich­tung hänge eine „0“ an den Pfad an, für jeden Weg in die an­de­re Rich­tung eine „1“¹¹ . Dar­aus er­gibt sich:

Da­durch, dass nur an den Blät­tern des Bi­när­baums die Sym­bo­le vor­kom­men, ist da­durch auch die Prä­fix­frei­heit des Codes ge­ge­ben. Au­ßer­dem sieht man daran di­rekt, dass durch den Baum auch das Op­ti­mum für die Code­län­ge ge­ge­ben ist, denn den we­ni­ger oft vor­kom­men­den Sym­bo­len wer­den au­to­ma­tisch län­ge­re Bi­när­codes zu­ge­wie­sen.

Für die Co­die­rung des Tex­tes „ADBCB­DBCBD“ wer­den die Bi­när­codes jedes ein­zel­nen Sym­bols hin­ter­ein­an­der­ge­setzt und man er­hält:

0000110011011001101

Bei der De­co­die­rung geht man ent­spre­chend den Bits den Weg aus­ge­hend von der Wur­zel ent­lang des Bau­mes. Ist man an einem Blatt mit einem Sym­bol an­ge­kom­men, so be­ginnt man wie­der von vorne:

Wör­ter­buch­ver­fah­ren: Ein­füh­rung

Wör­ter­buch­ver­fah­ren nut­zen zur Kom­pres­si­on Red­un­danz aus. Sich oft wie­der­ho­len­de Wör­ter und Sym­bol­fol­gen wer­den in einem Wör­ter­buch ge­spei­chert und bei der Co­die­rung auf diese Ein­trä­ge re­fe­ren­ziert. Man un­ter­schei­det dabei zwi­schen Ver­fah­ren mit sta­ti­schen und sol­chen mit dy­na­misch er­zeug­ten Wör­ter­bü­chern. Bei dy­na­mi­schen Ver­fah­ren wird das Wör­ter­buch bei der Kom­pres­si­on bzw. De­kom­pres­si­on au­to­ma­tisch be­füllt, wo­durch man die­ses nicht se­pa­rat spei­chern muss und damit wei­te­rer Spei­cher­platz ein­ge­spart wer­den kann.

Lem­pel-Ziv-Welch: LZW-Ver­fah­ren

Um ein dy­na­mi­sches Wör­ter­buch zu er­zeu­gen und dar­auf re­fe­ren­zie­ren zu kön­nen, be­nö­tigt man pro Sym­bol bzw. Re­fe­renz mehr als 8 Bit. Üb­li­cher­wei­se ver­wen­det man 12 Bit. Das Wör­ter­buch um­fasst also ma­xi­mal 2¹²=4096 Ein­trä­ge, wovon die ers­ten 256 Sym­bo­le den Bytes selbst von 00₁₆ bis FF₁₆ ent­spre­chen.

Die zu kom­pri­mie­ren­den Daten kön­nen hier­bei be­lie­bi­ge Bi­när­da­ten sein, zur bes­se­ren Ver­ständ­lich­keit und Über­sicht­lich­keit ver­wen­den wir hier le­dig­lich Text.

Soll ein Text (oder an­de­re Daten) kom­pri­miert wer­den, so sucht man – aus­ge­hend von der je­weils ak­tu­el­len Stel­le – die längst­mög­li­che Sym­bol­fol­ge im Wör­ter­buch. Zu Be­ginn ist das je­weils nur ein ein­zel­ner Buch­sta­be. An­schlie­ßend wird die ge­fun­de­nen Sym­bol­fol­ge und das nach­fol­gen­de Sym­bol als neuer Ein­trag in das Wör­ter­buch ein­ge­tra­gen.

Bei­spiel: Der Text „BA­BAA­BAAA“ soll mit­hil­fe des LZW-Ver­fah­rens kom­pri­miert wer­den. Man star­tet mit einem Wör­ter­buch, in dem le­dig­lich die Sym­bo­le von 0 bis 255 be­legt sind.

Die Zei­chen­fol­ge wird also zur Bit­fol­ge (He­xa­de­zi­mal): 042041100101041104

LZW: De­kom­pres­si­on

Bei der De­kom­pres­si­on wer­den je­weils 12Bit-Blö­cke ein­ge­le­sen. Das Wör­ter­buch er­gibt sich aus dem ers­ten Zei­chens des ak­tu­el­len Ein­trags, wel­cher an den zu­letzt ge­fun­de­nen Ein­trag an­ge­hängt wird:

Ein Son­der­fall er­gibt sich bei der De­kom­pres­si­on im letz­ten Schritt. Wenn eine Zei­chen­fol­ge mehr­fach hin­ter­ein­an­der im Ur­sprungs­text auf­tritt, so kann es vor­kom­men, dass bei der De­kom­pres­si­on auf einen Wör­ter­buch­ein­trag ver­wie­sen wird, der noch nicht exis­tiert. Dann gilt: der „ge­fun­de­ne“ Ein­trag ent­spricht dem vor­he­ri­gen Ein­trag + dem ers­ten Buch­sta­ben des vor­he­ri­gen Ein­trags.

Es emp­fiehlt sich, die­sen Son­der­fall an­fangs in der Schu­le zu mei­den.

 

⁷ Vgl. Auf­bau­kurs In­for­ma­tik

⁸ Der ma­the­ma­ti­sche In­for­ma­ti­ons­ge­halt nach Shan­non ist nicht Teil des Bil­dungs­pla­nes.

⁹ Nach https://​www.​swis­se­duc.​ch/​in­for­ma­tik/​daten/​huff­man­n_​kom­pres­si­on/​docs/​huff­man.​pdf

¹⁰https://​peop­le.​ok.​ubc.​ca/​ylu­cet/​DS/​Huff­man.​html

¹¹ An­mer­kung: hier wurde ein­heit­lich für die Wege nach links die „0“, nach rechts die „1“ ge­wählt. Man muss dies je­doch in­ner­halb des Bau­mes nicht ein­heit­lich ma­chen!

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][1 MB]

 

Wei­ter zu Ha­shing