Datenkompressionstutorial?

[Dudadida]

@squeaker: Hab Huffman selbst nie angewendet (oder mich damit beschäftigt), deshalb mal ne Frage:

11010010100

Wenn ich den Text so kodiert habe, wie komme ich wieder auf das Original? Denn wenn a=1 b=01 c=00, dann gibt's ja durchaus verschiedene Möglichkeiten die Bits zu werten. Soll heißen, woher weiß ich beim Decodieren, wann ich im Blatt bin?

 

[squeaker]

Der Code ist Präfixfrei, soll heisen kein Code für ein Symbol ist Präfix für den Code eines anderen Symbols.

Beispiel: a=1, b=11 -> nicht präfixfrei, da die erste 1 in b der Code für a ist.

Beispiel: a=1, b=01, c=00 -> präfixfrei. Wenn der Code mit 1 beginnt, ist es ein a, wenn er mit 0 beginnt ist er etweder ein b oder ein c.

Man muss beim Decodieren natürlich von vorne Anfangen. Wahlfreier Zugriff auf beliebige Zeichen ist nicht möglich.

Um deine Frage direkt zu beantworten: du ließt bitweise den Datenstrom aus und folgst folgenden Regeln:

-Starte in der Wurzel.
-Wenn du eine 1 ziehst gehe links, sonst rechts (bzw. umgekehrt wenn andersherum codiert wurde).
-Wenn du nicht mehr gehen kannst, bist du in einem Blatt, schreibst das Symbol in den Ausgabestrom und startest wieder in der Wurzel.

Da der Baum vorliegt (vorliegen muss) ist die Regel eindeutig. Da der Weg eindeutig ist zu jedem Blatt, kann keine zweideutige dekodiervorschrift entstehen.

 

[Dudadida]

Ok, danke squeaker, ich glaub ich hab's.

 

[squeaker]

spassig wird's erst bei der arithmetischen Kodierung. Da kann es sein, dass ein Symbol mit weniger als 1 bit codiert wird *G*. Ich hoffe dieses WE reiche ich das Tut ein (ist eigentlich noch der Contest?).