Huffman (De-)Codierung

Diskussion zum Thema Programmierung unter DOS (Intel x86)
Antworten
Benutzeravatar
zatzen
DOS-Guru
Beiträge: 518
Registriert: Di 17. Apr 2012, 05:10
Wohnort: bei Köln
Kontaktdaten:

Huffman (De-)Codierung

Beitrag von zatzen »

Hallo!

Wollte hier mal um Rat/Erfahrung bzgl. Huffman Codierung, und Dekodierung fragen.

Ich habe die Kodierung theoretisch bereits bestens verstanden (ist ja auch leicht) und finde im Internet immer
nur wieder diese simple Erklärung, oder aber direkt Umsetzungen in C bzw. Java. Ich suche das dazwischen.


Also, die Theorie wie man den Baum erstellt, die ist mir klar.
Das programmiertechnisch umzusetzen wäre auch wahrscheinlich kein Problem.
Wobei ich das noch nicht gemacht habe, bisher nur Versionen mit rekursiven Routinen gesehen habe,
und das selbst lieber nicht-rekursiv umsetzen möchte.


Mein essentielle Frage ist, welche und wieviele Informationen muss ich bei einem codierten Stream
mitliefern, damit dieser wieder decodiert werden kann.

Ich würde damit vielleicht jeweils ca. 40 Byte codieren wollen, und wenn die Bauminformationen
zu groß sind würde das ja keinen Sinn machen.
mov ax, 13h
int 10h

while vorne_frei do vor;
Benutzeravatar
zatzen
DOS-Guru
Beiträge: 518
Registriert: Di 17. Apr 2012, 05:10
Wohnort: bei Köln
Kontaktdaten:

Re: Huffman (De-)Codierung

Beitrag von zatzen »

Kann es sein, dass die Code-Tabelle genügt?
Sprich, ich habe die Zeichen A B C und dann wäre das so in etwa:

A: 0
B: 10
C: 11


Ich war mir nur nicht sicher ob man da nicht noch mit angeben muss, wie lang der jeweilige Bitcode ist.
Also angenommen ich habe 0001 und speichere diese BItfolge in einem Byte. Dann wäre das ja dasselbe wie 1 ohne
die Nullen... Auch wenn es andersherum ist und man hätte die Folge 1000, wenn man vom LSB ausgeht, wieder 1
und man kann nicht sagen wieviele Nullen dranhängen.

Alternativ wäre noch mögllich, ich definiere in 3 Bit immer vorher, wieviel Bit es sind, also 1, 2 3... oder 8.
Würde bei Codelängen unter 5 Bit sogar Speicherplatz sparen. Aber macht man das so??
mov ax, 13h
int 10h

while vorne_frei do vor;
Benutzeravatar
zatzen
DOS-Guru
Beiträge: 518
Registriert: Di 17. Apr 2012, 05:10
Wohnort: bei Köln
Kontaktdaten:

Re: Huffman (De-)Codierung

Beitrag von zatzen »

Auch wenn das Thema Huffman an sich kein spezielles DOS-Thema ist, halte ich es doch für sinnvoll,
es einmal im Rahmen von DOS und "oldskool" Programmierung zu betrachten. Was man im Internet
an Erklärungen und Beispielen findet sind so gut wie ausschliesslich Betrachtungen innerhalb der
objektorientierten Programmierung, bevorzugt Java, wo man auch überhaupt kein Problem damit
zu haben scheint, für Definitionen in der Codetabelle am Anfang eine 32 Bit "RawInteger Klasse" zu
verwenden, die lediglich einen einstelligen Wertebereich (1 oder 2 :-D ) abdecken muss. Also mal
wieder herzhaft 31 Bit in den Wind geschossen, und das für jeden einzelnen Tabelleneitrag...
Ich komme langsam der Lösung näher und merke dabei, dass meine Idee mit den 3 Bit für die Codewort-Länge
gar nicht so schlecht war - bei dem was ich jetzt gerade lese wird das Codewort grundsätzlich als 1 oder
gar 2 Byte gespeichert, und ein gesetztes Bit umittelbar vor den Anfang des Codeworts gesetzt, um die
Länge abzugrenzen.
Ob ich letztenendes mehr als 8 Bit für die Codewörter benötige wird sich zeigen.

Bleibt die Frage offen wie man jetzt am besten decodiert. Für jedes eingelesene Bit mehr die Codetabelle
vergleichend durchzurattern kann's ja irgendwie nicht sein. Oder doch? Wahrscheinlich wird es eher ein
Herumspringen in der Tabelle.
mov ax, 13h
int 10h

while vorne_frei do vor;
Benutzeravatar
zatzen
DOS-Guru
Beiträge: 518
Registriert: Di 17. Apr 2012, 05:10
Wohnort: bei Köln
Kontaktdaten:

Re: Huffman (De-)Codierung

Beitrag von zatzen »

Nach ausgiebiger Beschäftigung mit diesem Thema komme ich zu dem Schluss, dass
Huffman für meine Zwecke zu aufwändig ist.

Der Thread kann gelöscht werden.

Danke.
mov ax, 13h
int 10h

while vorne_frei do vor;
Antworten