Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ja, wir waren also bei Huffman-Kodierung stehen geblieben.

Nein, unser Thema ist Kodierung mit variabler Wortlänge, kommafrei.

Haben wir festgestellt, präfixfreie Codes sind super, machen den Job.

Wir haben dann festgestellt über das Theorien von Macmillan, dass es keinen Sinn macht,

wo andere Codes, die kommafrei dekodierbar sind, mit variabler Wortlänge nachzudenken,

weil die kraftsche Ungleichung immer erfüllt sein muss, auch bei jeder Form der eindeutigen

Dekodierbarkeit.

Und wenn die kraftsche Ungleichung erfüllt ist, dann existiert ein präfixfreier Code.

Das haben wir alles nachgewiesen und wir können ihn konstruieren, zum Beispiel nach Schönen

Pfarrer oder wir können ihn konstruieren nach Huffman.

Und bei Huffman kommt der beste raus.

Und der beste Code ist dadurch gegenseitigt, dass die Zwischenknoten im Baum die kleinste

Wahrscheinlichkeit haben, die sie haben können, weil die Summe der Zwischenknotenwahrscheinlichkeiten

die mittlere Codewortlänge ist.

Klar?

Und deshalb konstruieren wir den Huffman Code von den Blättern her und nicht von der Wurzel

und verbinden immer die Knoten, die aktuell die kleinsten Wahrscheinlichkeiten haben,

weil deren Summe ist ja die Zwischenknotenwahrscheinlichkeit.

Und auf diese Weise komme ich zu einem Baum mit der kleinsten Summe von Zwischenknotenwahrscheinlichkeiten

und damit zur kleinstmöglichen mittleren Codewortlänge für einen eindeutig dekodierbaren

Code mit variabler Wortlänge.

Im Binären ist das ganz einfach, da fange ich einfach an, blind und mach das.

Wenn ich aber keine Binärencodesymbole habe, dann muss ich aufpassen, dass ein Baum nicht

alle möglichen Endknoten haben kann, nämlich in einem Ternenbaum zum Beispiel drei, da

hat die Wurzel drei Knoten.

Wenn ich jetzt einen Knoten zum Zwischenknoten degradiere und dort verlängere, gibt es

drei neue Knoten, aber der alte verschwindet, weil der vom End zum Zwischenknoten wird.

Und damit habe ich nur zwei neue Knoten gewonnen und damit gibt es in einem Ternenbaum die

drei, fünf, sieben, neun Knoten.

Im Vierstufigen gibt es vier, sieben, zehn, dreizehn, sechzehn und so weiter.

Im Fünfstufigen Alphabet gibt es dann fünf, neun, dreizehn, siebzehn.

Ist klar, wie ich denke.

Wenn ich jetzt einen Half-Man-Code-Baum konstruiere, dann beginne ich ja an den Endknoten, ganz

am Ende.

Und genau dort muss ich sparen, da darf ich nicht viele Codewörter haben, damit die mittlere

Codewortlänge kurz ist, weil die teuren, die langen, die hauen natürlich richtig rein.

Die muss ich vermeiden.

Deshalb, wenn meine Zahl der Quellenwörter oder Quellensymbole, je nachdem ob ich Einzel-Symbole

oder ganze Wörter kodiere, wenn meine Zahl der Quellenwörter nicht in meine Zahlenreihe

passt von möglichen Endknoten, dann muss ich im allerersten Schritt die Anpassung machen,

weil das dann die größtmögliche Codewortlänge wird.

Klar?

Ist verstanden?

Und das heißt also zum Beispiel in diesem Ternenbäuer, das wir da hatten, mit sechs

Symbolen, aber im Ternenbäuer gibt es eben nur drei, fünf, sieben, dann muss ich die

Anpassung beim allerersten Mal machen, dass ich beim allerersten Mal nur zwei zusammenfasse,

das dritte weglasse, weil das ist ja ein sehr langes Codewort.

Und weil wenn ich jetzt, also ab hier fünf, wenn die zusammengefasst sind, klar, die beiden

sind zusammengefasst, sind fünf, sechs, sieben, eins, zwei, drei, vier, fünf, klar, sind