Datenkompressionstutorial?

Häufigkeitstabelle:

1. Schritt - Aus der Datei:
a=4 //a kommt 4 mal vor
b=2 //b kommt 2 mal vor
c=2 //c kommt 2 mal vor

2. Schritt, b und c zusammenfassen zu einem Knoten im Baum.
a=4
(bc)=4 //die Blätter in diesem Teilbaum kommen insgesamt 4 mal vor.

3. Schritt, a und den Teilbaum (bc) zusammenfassen
(a(bc))=8 //die Blätter dieses Teilbaumes (in diesem Fall der komplette Baum) kommen 8 mal im Text vor = (da der Baum schon komplett ist) gesamtzahl der Zeichen
 
wie oben schon erwähnt - ich werde es in pdf giessen. Da ich aber nicht an meinem heimischen PC sitze, sondern auf der Arbeit müssen die Forenbeiträge etwas spartanischer in der Ausstattung ausfallen.

Ich poste das ganze blos im Forum damit ich a) schon etwas habe worauf ich später (zu Hause) zurückgreifen kann und b) ander Leute haben mich darauf hinzuweisen, was noch unklar ist damit das Tutorial nicht nur für mich verständlich ist.
 
Super squeaker. Find ich echt klasse und ein interessantes Thema, auch wenn ich es in der Praxis wohl nie brauchen werde. ;)
 
Vielleicht noch eine Ergänzung zu RLE:

Man kann auch festlegen, dass ein Byte im RLE-Stream nur dann als "Multiplikator" des nächsten Bytes interpretiert werden soll, wenn Bit 7 gesetzt ist.

Beispiel:
Code:
Hex: 00 00 00 01 01 03 0f 0f 78 78 78 78 de
wird zu:
Hex: 83 00    82 01 03 82 0f 84 78       81 de

Die Folgerung davon ist allerdings, dass einzeln für sich stehende Bytes mit Werten >= 0x80 immer noch RLE-codiert zwei Bytes beanspruchen (würde man es unverändert in den RLE-Stream schreiben, würde es als Multiplikator interpretiert werden). Stehen allerdings viele einzelne Bytes mit Werten < 0x80 im zu codierenden Stream, ist diese Methode besser als die ursprüngliche.
 
mit deiner Erlaubnis werde ich das in das pdf mit einfügen.

Besteht interesse an HLA (=High Level Assemby von Randall Hyde) tutorials? Dann würde ich meine Implementierungen kommentiert mit in das Datenkompressionstut schreiben (alles noch in der Entwicklung, also keine Hektik)
 
Zuletzt bearbeitet:
Klar, meine Ergänzung darfst du natürlich einbauen, von mir aus auch kürzen, erweitern, anders erklären o.ä. Gegen eine namentliche Erwähnung hätte ich dann natürlich auch nichts einzuwenden ;)
 
ich bin die nächsten 2 Wochen nicht zuhause - kann also nur über das Forum und ohne Zeichnungen posten, werde dies aber tun und parallel auf dem Laptop (ohne Internet) die Latex-Version weiter schreiben. In 2 Wochen, wenn ich wieder zuhause bin, werde ich das Tut dann zu euch schicken (als pdf)

Updates kommen dann auch nach.
 
Um die Wartezeit nicht zu langweilig zu machen:

eine weitere Version von RLE:

Man leitet Multiplikatorbytes mit einer Escapesequenz (z.B. FF) ein. Beispiel:

01 00 FF 03 04 steht dann für: 01 00 04 04 04

um FF zu schreiben braucht man dann natürlich wieder ein Escape:

FF FF 01 steht dann für FF 01
 
Adaptive Huffman codierung

Das Prinzip der adaptiven Huffman Codierung ist relativ simpel. Statt ein Modell aus der Datei zu gewinnen wird das Modell mit einem einfachen Standardmodell initialisiert und danach je nach Eingabe angepasst.
Es gibt mehrere Methoden, ich werde im folgenden eine beschreiben.

Huffman bildet seinen Baum ja aus einer Tabelle mit den Symbolen und deren Häufigkeiten. Nun wird ein neues Symbol definiert, das ESC-Symbol. Wenn ein ESC-Symbol im Datenstrom steht, werden die Nachfolgenden 8 bit als unkomprimiertes Byte interpretiert.
Die Häufigkeitstabelle wird nun als Tabelle mit 1 Eintrag, ESC mit Häufigkeit 1 initialisiert. Als weitere Besonderheit gilt, dass die Häufigkeit von ESC nicht hochgezählt wird, sondern immer 1 bleibt.
Wird nun das erste unkomprimierte Zeichen gelesen, ist es noch nicht in der Tabelle, d.h. es wird ESC ausgegeben und dann das unkomprimierte Zeichen. Daraufhin wird das Zeichen in die Tabelle eingefügt mit Häufigkeit 1. Bei jedem weiteren unbekannten Zeichen wird genauso vorgegangen. Trifft man auf ein bekanntes Zeichen, so wird das Zeichen gemäß Tabelle codiert und danach dessen Häufigkeit um 1 erhöht.

Bei der Dekompression geht man analog vor. Da die Tabelle stets bekannt ist, kann eindeutig dekomprimiert werden. Mit dem dekomprimierten Zeichen kann dann die Tabelle aktualisiert werden und das nächste Zeichen ist wieder eindeutig definiert.
 

Neue Beiträge

Zurück