Datenkompressionstutorial?

Ja, mach nur. Hatte auch eigentlich sowas ähnliches vor, aber wenn du schneller fertig wirst, nur zu. :)
Wie man in einem Tutorial den Huffman-Algo erklärt, würde mich auch mal interessieren. Irgendwie hab ich mich bei meiner Erklärung dazu ziemlich verhampelt. :rolleyes: ;)
 
RLE

Na gut, dann fangen wir mal mit etwas einfachem an (ich giesse das dann zuhause noch in pdf oder so - kann das hier leider nicht):

RLE - Run Length Encoding.

Diese sehr einfache Kodierung ist nur für relativ einfach strukturierte Dateien geeignet bei denen sich viele Bytes mehrfach wiederholen. Bei der RLE wird vor jedem Byte noch gespeichert, wie oft es folgt. Beispiel:

00 00 00 01 01 03 würde zu: 03 00 02 01 01 03

zu lesen als: 03 mal 00; 02 mal 01; 01 mal 03.

Dies führt natürlich im worst case zu einer Verdoppelung der Dateigröße. Falls mehr als 255 mal eine Wiederholung vorkommt, wird einfach ein neuer Zähler angebrochen.

Beispiel: für 257 mal 01: 255 01 02 01

an diesem Beispiel sieht man auch den Kompressionseffekt.

Ein Spezialfall tritt auf, wenn nur 2 Werte in der Datei vorkommen bzw. auf Bitebene gespeichert wird (z.B. Schwarz-Weiß Bilder). Dann reicht es aus festzulegen mit welchem Wert begonnen wird, z.B. 1 und dann wird im Wechsel immer nur der Zähler gespeichert.

Beispiel: 03 05 01 07 -> 3 mal 1, 5 mal 0, 1 mal 1, 7 mal 0

Hier muss beim Zählerüberlauf einfach eine 00 für 0 mal nächste Farbe zwischengespeichert werden. Das Beispiel von oben wird damit zu:

255 00 02

Vorteil: Sehr schnell
Nachteil: nur in Spezialfällen gut

Wird bei sw-Bilder verwendet und als Vorstufe für manche Kompressionsverfahren.

Weitere Tuts in Planung:

+Huffman (statisch/adaptiv)
+Arithmetisch
(+LZW/LZ77)
(+BWT - wenn ich sie versteh)
+Was ist ein Modell und wozu brauche ich es?

(das alles nicht zwingend in dieser Reihenfolge)
 
Zuletzt bearbeitet:
Modelle

Modelle werden für Huffman- und Arithmetische Codierung benötigt. Beide Codierungen weisen "unwahrscheinlicheren" Zeichen(folgen) längere Codes zu als "wahrscheinlicheren".

Beispiel: im Morsecode ist das häufigste Zeichen e sehr kurz codiert: mit einem Punkt. Q - was seltener vorkommt ist mit Strich-Strich-Punkt-Strich kodiert.

Was nun diese Algorithmen machen ist aufgrund eines Models jedem Bytewert in der Datei einen Code zuzuweisen, wobei unwahrscheinlichere Bytewerte längere Codes erhalten und wahrscheinlichere erhalten kürzere.
Wenn bestimmte Bytewerte nicht in der Datei erscheinen, so werden sie auch nicht in die Betrachtung mit einbezogen.

Als Ordnung eines Modells bezeichnet man die Anzahl der vorhergehenden Zeichen die mit in die Wahrscheinlichkeitsberechnung mit eingehen.
Als eingängistes Beispiel für den Sinn einer solchen Betrachtung: u alleine hat eine geringe Wahrscheinlichkeit in geschriebenem Text, nach einem q ist die Wahrscheinlichkeit aber fast 100%. Ein Order-0 Modell würde diese Tatsache nicht berücksichtigen, ab einem Order-1 Modell ginge sie mit in die Berechnung ein.

Statisch/Adaptiv
Statische Modelle sind Modelle die entweder fest im Encoder/Decoder verdrahtet sind oder bei jeder Datei neu gebildet werden und für den Decoder abgespeichert werden damit dieser die Datei wiederherstellen kann.
Adaptive Modelle sind Modelle, die von einem definierten Grundzustand ausgehen und diesen nachträglich an die Datei anpassen, d.h. die Wahrscheinlichkeiten für die einzelnen Bytewerte nachträglich anpassen. Diese modifizierung geschieht nach definierten Regeln, so dass der Decoder beim Entpacken das Modell ebenfalls on-the-fly erstellt.

P.S.: Überall wo Bytewert steht bzw. Byte kann natürlich auch jede andere Größe stehen, Byte ist einfach das gebräuchlichste.
 
Huffman

So, nun wird's etwas komplizierter. Voraussetzung für Huffman: man muss einzelne Bits schreiben können, da die erzeugten Codes variable Bitlänge haben (siehe Modelle oben).

Huffman codiert die einzelnen Zeichen anhand einer Baumstruktur. In dieser Baumstruktur sind die zu kodierenden Zeichen in den Blättern, der Weg zum Blatt gibt den Code an, wobei der Baum ein Binärbaum ist, d.h. jeder Knoten hat maximal 2 Söhne. Der Code wird gebildet indem jedem linken Sohn das Bit 1 und jedem rechten Sohn das Bit 0 zugeordnet wird.
Beispiel:

/\
/\ a
b c

In diesem recht einfachen Beispiel werde

a=0
b=11
c=10

codiert.

Die Decodierung erfolgt genauso einfach. Man liest die Datei Bitweise und startet einfach von der Wurzel aus - 0 heisst rechter Sohn, 1 heisst linker Sohn. Wenn man im Blatt ankommt, so schreibt man das Zeichen im Blatt und fängt wieder bei der Wurzel an.

Wie kommt man zum Baum?
Zuerst liest man die Datei komplett und zählt wie oft jeder Bytewert vorkommt. Diese Tabelle (bytewert, Häufigkeit) wird nach Häufigkeit sortiert.
Nun werden die beiden Werte mit der geringsten Häufigkeit zu einem Knoten zusammengefasst, die ursprünglichen werte gelöscht und der neue Knoten in der Tabelle einsortiert. Die Häufigkeit des Knotens ist die Summe der Häufigkeiten der Söhne.
Dies macht man solange bis nur noch 1 Knoten in der Liste steht, dies ist die Wurzel.

Beispiel: aabacabc
a=4, b=2, c=2

a=4 a=4 (a(bc))=8
b=2 (bc)=4
c=2

gibt den Baum:

/\
a /\
b c

gibt die codes: a=1 b=01 c=00

der String aabacabc wird nun als 11010010100 codiert
Orginalstring: 8*8 bit (ASCII) = 64bit
Orginalstring mit 2bit pro Zeichen: 8*2bit= 16bit
Huffman: 11 bit

Noch fragen?
 
Squeaker, bitte benutz doch die Code-Tags der Forensoftware, um die Baumstrukturen deutlicher zu machen. Oder noch besser: Zeichne diese als simple Grafiken, das sollte ja kein allzu großer Aufwand sein. :)

gibt den Baum:

/\
a /\
b c

gibt die codes: a=1 b=01 c=00
Vielleicht solltest du auch noch erklären, dass du genau auf diese Codes kommst, weil du für jeden Pfad nach links eine 1 und für jeden Pfad nach rechts eine 0 vergibst. ;)

der folgende Teilst ist mir etwas unklar

a=4 a=4 (a(bc))=8
b=2 (bc)=4
c=2
Was genau ist dir daran unklar? :)
 

Neue Beiträge

Zurück