COBOL: Huffman

[Gast]

Guten Morgen.

Ich bin Azubi im Bereich Fachinformatik - Anwendungsentwicklung.

Im Betrieb lernen wir COBOL und ich habe eine Aufgabe bekommen das ich Daten komprimieren und wieder Dekomprimieren soll. Im Internet habe ich die Huffman-Codierung gefunden. Leider weis ich nicht genau wie ich das mit COBOL umsetzten soll. Eine einfache Komprimierung und Dekomprimierung habe ich schon geschrieben und diese war auch erfolgreich.

Warum ich jetzt noch Huffman programmieren soll? Meine Ausbilderin sagte Huffman und die Komprimierung nichts. Als ich ihr das dann vorgestellt habe (siehe Präsentation in Anhang), sagte sie das ich es mal ausprobieren sollte und dann vergleichen sollte, welche Datei kleiner ist und ob es auch von der Zeit her effizienter ist.

Kann mir jemand helfen? Ich wäre recht dankbar.

Huffman.pps

[WWetterwachs]

Hi

Kannst Du einen binären Baum codieren? Für Huffman brauchst Du diesen, wie deine Präsentation zeigt.

Huffman lebt davon dass bestimmte Buchstaben ein häufigeres Vorkommen haben als andere. Alle Buchstaben werden in Entscheidungsflags 0 oder 1 - also binär umgewandelt(linker oder rechter Zweig des Baumes). Anhand dieser Logik wird also mit dem gegebenen Text ein binärer Baum aufgebaut.

Grob gesagt wird der Baum in umgekehrter Reigenfolge zum Auftreten der Buchstaben aufgebaut. Buchstaben mit nur einem vorkommen liegen auf unterster Ebene , die mit dem häufigsten vorkommen auf höchster Ebene(Hier tritt die Ersparnis auf, da die höchte Ebene die geringste Zahl an Entscheidungsflags hat). Du kannst dann einfach die Entscheidungsflags speichern, die dann einfach abgearbeitet werden, bis ein Buchstabe(Blatt) gefunden wird. Also in der Präsentation sieht man, daß man 5 Entscheidungen(linker oder rechter Zweig des Baumes)zu treffen hat bis man den ersten Buchstaben findet(das D) und folgend hat man wieder auf der obersten ebene des binären Baume(Wurzel) zu starten.

Wenn Du einen binären Baum codieren kannst, ist es dir möglich das zu codieren. In COBOL auf der I5 fällt mir dazu keine Möglichkeit ein. Ich kenne binäre Bäume nur aus Turbo Pascal und habe sie auch nur in dieser Sprache codiert.

Denke daran das die Kompressionsrate stark vom mehrmaligen Auftreten einzelner Buchstaben abhängt.

[WWetterwachs]

Hi again

Hier findest Du ein paar genauere Infos.

http://zach.in.tu-clausthal.de/teaching/info2_06/folien/09_greedy_2_4up.pdf

Booo ich werde alt.

Stell dir noch mal eben die Frage, wie du nach Huffman wieder de-kompriemieren kannst und welche praktische Anwendung das dann hat.

Bearbeitet 28. Oktober 2011 von WWetterwachs

[Gast]

Hi.

Vielen Dank für deine Infos. Der Link hat mir ein wenig geholfen, aber das Umsetzen wird etwas schwer.

Momentan scheitert es an deiner letzten Frage, wie es mit der Dekomprimierung aussieht. Der Baum muss für die Dekomprimierung mitgegeben werden, ansonsten kann es nie zurück gesetzt werden. Und da der Baum sich jedes Mal ändert von den Häufigkeiten her, ist das ein nicht wirklich erfolgreiches verfahren.

Meine Idee ist jetzt, dass ich ein festes Wörterbuch nehme. Ich gebe ein Beispiel: E ist der am häufigsten vorkommende Buchstabe im Alphabet und Q der seltenste. Ich habe einen Baum von Hand erstellt und habe damit rausbekommen das E durch 111 und Q durch 00000000000 ersetzt wird (die restlichen Buchstaben stehen logischer weise dazwischen). Nur was passiert wenn ich jetzt einen Text habe und dann immer abfrage ist die Buchstabenfolge 111 oder 1110 oder ... Außerdem hat sich nach der Rücksprache mit meiner Ausbilderin ergeben, das in der Datei die ich komprimieren muss recht viele Leerzeichen und auch Zahlen dabei sind. Jetzt müsste ich mein Baum (aus dem Beispiel) etwas umstellen und dafür sorgen, dass das Leerzeichen (soll angeblich das häufigste Zeichen sein) am kleinsten wird. Zahlen (Vertragsnummer, Betrag usw.) sind wohl die zweithäufigsten. Somit müsste mein Baum voll und ganz umstrukturiert werden.

Nun meine Frage, klingt das von der Idee her logisch? Also wäre es sinnvoller sowohl für die Komprimierung als auch für die Dekomprimierung ein festes Wörterbuch zu erstellen? Eine momentan bessere Idee als ein festes Wörterbuch habe ich leider nicht.

Im Anhang befindet sich die Datei wo ich die Buchstaben des Deutschen Alphabets nach der Häufigkeit sortiert und den Baum erstellt habe. Somit wäre das eine Grundlage für ein festes Wörterbuch.

Vielen Dank für die Hilfe!

Huffman_Alphabet.xls

[WWetterwachs]

Hi

Das ist ein Lösungsansatz aber die erste Folie 4 der Präsentation hat alle Infors die du Brauchst um den binären Baum zu bauen.

Nicht der Text ist nötig sondern deine Kumulations.- und Sortierinfos also z.B. deine Excel Tabelle.

[Gast]

Hi.

Also ist ein festes Wörterbuch wie zum Beispiel die Exceltabelle am einfachsten?!

Das erstellen des Baumes ist per Hand auch kein Problem, nur wie sage ich dem Programm das es diesen erstellen soll? Aber ich denke ich werde es erstmal mit dem festen Wert ausprobieren.

Vielen Dank für deine Hilfe. Ich denke vorerst werde ich alleine zurecht kommen. Erst bei der dekomprimierung werde ich vermutlich die ersten Probleme bekommen. Aber bis dahin werde ich mich um die komprimierung kümmern.

[flashpixx]

Ich halte es für äußerst ineffizient eine eigene Implementation von einer Huffman-Codierung zu entwerfen (außerdem hat man damit dann auch direkt wieder Fehleranfälligkeit).

siehe Shannon-Fano-Kodierung die zlib Home Site enthält eine Implementierung der Huffman-Codierung, so dass man sie nur noch verwenden muss.

Zu Übungszwecken kann man es durchaus auch selbst implementieren, d.h. eine Datenstruktur für den Binärbaum entwerfen, für das Wörterbuch und das ganze dann entsprechend füllen und in eine Datei schreiben (Entpacken entsprechend analog)

[WWetterwachs]

Hi

Ein festes Wörterbuch ist am einfachsten aber nicht am besten und erzeugt evtl. sogar eine Vegrößerung des Datenvolumens.

Du willst ja komprimieren.

Du scannst deinen Text/Dokument..... und zählst/speicherst das Vorkommen aller Zeichen(Tabelle 1). Anhand dieses Ergebnisses(quasi der Cheffrierschlüssel) baust du den binären Baum auf und erzeugst das komprimierte Ergebnis.

Zum dekompriemieren kannst du nun Tabelle 1 jederzeit wieder nutzen und den binären Baum erneut aufbauen. Die Tabelle 1/der Decheffrierschlüssel gehört unlösbar zu deinen komprimierten Daten.

Letztlich hast Du den Aufbau des binären Baumes ja bereits beim komprimieren bereits codiert.

[WWetterwachs]

Hi

Oh ja, Ist sicherlich ineffizient aber es bringt Spaß und es ist extrem lehrreich.

Wenn wir nur kopieren und nicht selber "erarbeiten" erzielen wir kaum Fortschritte.

[lilith2k3]

Wobei mir der Sinn eines "allgemeinen Wörterbuchs" nicht einleuchten will.

AFAIK orientiert sich Huffmann an den jeweiligen Klartexten:

sprich, wenn ich einen Text habe in welchem kein µ vorkommt -soll es ja geben- wozu es im Baum hinterlegen?

[WWetterwachs]

Hi

Du hast vollkommen recht.

Ein Allgemeines, also das maximale Wörterbuch würde theoretisch die Loslösung vom komprimierten Text erlauben, zerstört aber den Kompressionserfolg in meinen Augen, da ich ja meinen Baum nicht nach den Buchstabenhäufigkeiten aufbauen kann.

Die De-Kompression war Lion92 etwas unklar. Nicht der Klartext ist zur De-Kompression nötig sondern lediglich die Sortier.- und Häufigkeitstabelle ist zum erneuten Aufbau des binären Baumes nötig und dies sowohl bei der Kompression als auch bei der De-Kompression. Sollte er also die Kompression codiert haben, hat er bereits die De-Kompression zum größten Teil bereits codiert.

Es würde mich immer noch interessieren ob ich ibn COBOL direkt binäre Bäume - analog zu Turbo Pascal(z.B. Pointer) - aufbauen kann.

[WWetterwachs]

Hi again

Ich vergass zu sagen, daß bei sehr langen Texten sich Huffman eh an ein "allgemeines Wörterbuch" annähert. Die Bibel komprimiert dürfte dies exakt abbilden.

[Gast]

Guten Morgen.

Die Idee mit einem festen Wörterbuch habe ich mitlerweile verworfen. Beim aufstellen des Wörterbuchs bzw. des Baumes für ein Wörterbuch habe ich feststellen müssen, das es viel zu groß ist und die Buchstaben eher größer werden als kleiner. Also Idee weg.

Zur Hilfe habe ich dann ein Strukturgramm gemacht. Beim durchsprechen mit der Ausbilderin hatte sie dann eine Idee. Das Stichwort ist Array. Wenn ich das Strukturgramm dazu fertig habe werde ich die Idee weiter erläutern und das Strukturgramm posten.

Vielen Dank für eure Hilfe und guten Ideen.

[WWetterwachs]

Hi

??

Ein ausgewogener binärer Baum mit allen Buchstaben des Alphabetes + Zahlen kann mit 6 Bit verschlüsselt werden. Da nach der durchschnittlichen Häufigkeitsverteilung der binäre Baum aber nicht ausgewogen wäre, wirst Du wohl mit 8 Bit auskommen. Wieso ist der Speicherbedarf da höher?

[Gast]

Guten Morgen und frohes Neues Jahr.

Mit etwas verspätung schicke ich euch die Struktogramme zu der Huffmankomprimierung. Es funktioniert unter COBOL. Es war schwer umzusetzen, aber ich habe es hinbekommen.

Wenn ihr Fragen habt könnt ihr mir eine Nachricht schicken, dann werde ich mich bemühen die Fragen zu beantworten.

Huffman-Kompimierung-und-Dekomprimierung.zip