c:huffman

Diskussionen zu Tutorials, Änderungs- und Erweiterungswünsche
Antworten
Iluya
Beiträge: 8
Registriert: So Mai 10, 2009 10:29 pm

c:huffman

Beitrag von Iluya » Mo Mai 11, 2009 7:17 pm

Diskussionsthread zur Huffman-Kodierung

Ich hab das Thema zuerst genommen, weil ich es gerade noch sehr präsent habe und eine Anwendung von binären Bäumen darstellt. Desweiteren halte ich es für ein interessantes Thema, da diese Codierung Speichernutzung, Binärbäume und Rekursion vertieft. Es führt zudem dem Tutorial-Benutzer vor Augen, das er doch täglich solche Algorithmen benutzt: Jede JPG wird mit Huffman kodiert :)

Denke, das ich den non-Code-Teil im Laufe der Woche fertig schreiben werde.

Kritik ist gerne gesehen.
Anwendungsfähig: [Delphi/FOP:Gut] | [HTML/JS/CSS: Mittel-Gut] | [PHP+MySQL: Gut] | [AutoIt(AHK): Gut];
Lernphase: [C:privat] | [C++:Uni];
Irgendwann geplant: [asm] | [Fortran];
There cannot be a crisis next week, my scedule is already full!

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: c:huffman

Beitrag von Xin » Mo Mai 11, 2009 7:58 pm

2 Fragen:

Frage 1: Warum packst Du den Huffmann unter die Bäume, wählst Du eine Implementierung mit Hilfe von Bäumen?
Frage 2: Ich finde es klasse, dass Du hier reinkommst und Dich gleich mit engagiert. Solche Leute brauchen wir. Wenn Du Dich hier dauerhaft engagieren magst, wäre es schön, wenn Du Dich im Brett Uservorstellung einmal vorstellen würdest, so dass wir eine Vorstellung haben, wer Du bist. Ansonsten steht Dir auch der Namensraum user:iluya: im Wiki zur Verfügung, um Dich vorzustellen.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Iluya
Beiträge: 8
Registriert: So Mai 10, 2009 10:29 pm

Re: c:huffman

Beitrag von Iluya » Mo Mai 11, 2009 9:00 pm

Zu 1: Ja.
Der Code wird als Baum aufgebaut: erst Wald = nur Wurzeln; und die jeweils geringsten Häufigkeiten werden verbunden...bis Wald = 1 Wurzel.
(De-) Codieren kann man gut zusammen mit Rekursivem Durchlaufen des Baums lösen. Daher hinter "rekursiv" als direkte Vertiefung.

Ich kenne auch nur diese Art Huffman aufzubauen. (Wie hier)
Wahrscheinlich kann man auch Hashtables sinnvoll einsetzen: Aber ich habe mich noch nie groß damit auseinandergesetzt.

Zu 2: Werde ich gleich machen...
Xin hat geschrieben: Ich finde es klasse, dass Du hier reinkommst und Dich gleich mit engagiert.
Ist auch ein wenig Hilfe zur Selbsthilfe: Möchte aktuell C verstehen und das geht durch selbst Anwenden am Besten. Hier habe ich die Möglichkeit mein vorhandenes Wissen durch andere direkt auf C übertragen zu lassen und so direkt Unterschiede/Gemeinsamkeiten zu sehen.
Desweiteren ist es einfach schön zu sehen, wie sich so eine Wissenssammlung erweitert. Der Umgangston in diesem Forum ist ein weiterer Pluspunkt und alles andere als selbstverständlich!

Edit: Link hinzugefügt
Anwendungsfähig: [Delphi/FOP:Gut] | [HTML/JS/CSS: Mittel-Gut] | [PHP+MySQL: Gut] | [AutoIt(AHK): Gut];
Lernphase: [C:privat] | [C++:Uni];
Irgendwann geplant: [asm] | [Fortran];
There cannot be a crisis next week, my scedule is already full!

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: c:huffman

Beitrag von Xin » Mo Mai 11, 2009 9:24 pm

Iluya hat geschrieben:Ich kenne auch nur diese Art Huffman aufzubauen. (Wie hier)
Wahrscheinlich kann man auch Hashtables sinnvoll einsetzen: Aber ich habe mich noch nie groß damit auseinandergesetzt.
Ich hatte ihn mal einem Array implementiert, das anschließend sortiert wurde.
Iluya hat geschrieben:Zu 2: Werde ich gleich machen...
Dann bin ich mal gespannt.
Iluya hat geschrieben:Desweiteren ist es einfach schön zu sehen, wie sich so eine Wissenssammlung erweitert. Der Umgangston in diesem Forum ist ein weiterer Pluspunkt und alles andere als selbstverständlich!
Das macht mir inzwischen auch Spaß, zumal ich als Informatiker inzwischen proggen.org als Referenz im Beruf verwenden kann. Mich begeistert es jedenfalls gelegentlich durch's Wiki zu surfen und zu sehen, wie es wächst. :-)

Was den Umgangston im Forum angeht: Ich halte das für selbstverständlich und zwar für so selbstverständlich, dass ich eher auf einen professionellen Antwortgeber verzichte, als dass hier irgendjemand von oben herab reden dürfte. Programmieren ist auch Spaß und darum geht es hier vorrangig. Also erwarte ich auch einen gewissen Humor und eine gewisse Gelassenheit im Forum.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Iluya
Beiträge: 8
Registriert: So Mai 10, 2009 10:29 pm

Re: c:huffman

Beitrag von Iluya » Mo Mai 11, 2009 9:36 pm

Xin hat geschrieben:Was den Umgangston im Forum angeht: Ich halte das für selbstverständlich und zwar für so selbstverständlich, dass ich eher auf einen professionellen Antwortgeber verzichte, als dass hier irgendjemand von oben herab reden dürfte. Programmieren ist auch Spaß und darum geht es hier vorrangig. Also erwarte ich auch einen gewissen Humor und eine gewisse Gelassenheit im Forum.
Naja: Für selbstverständlich halten und das es selbstverständlich ist sind LEIDER zwei verschiedene Sachen... Für mich ist die Netiquette selbstverständlich und auch Interpunktion und Rechtschreibung haben in Foren Daseinsberechtigung. (natürlich nicht Bewerbungs-Perfekt). Hmm...merke grad das es OT wird :)

Wie berechnest du denn dann für dein Array die jeweiligen Bitfolgen? Oder baust du dafür den Baum auf und speicherst dann die Werte in einem Array? Würde beim (De-)Codieren wahrscheinlich mächtig Zeit einsparen :idea:
Anwendungsfähig: [Delphi/FOP:Gut] | [HTML/JS/CSS: Mittel-Gut] | [PHP+MySQL: Gut] | [AutoIt(AHK): Gut];
Lernphase: [C:privat] | [C++:Uni];
Irgendwann geplant: [asm] | [Fortran];
There cannot be a crisis next week, my scedule is already full!

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: c:huffman

Beitrag von Xin » Mo Mai 11, 2009 10:26 pm

Iluya hat geschrieben:Naja: Für selbstverständlich halten und das es selbstverständlich ist sind LEIDER zwei verschiedene Sachen... Für mich ist die Netiquette selbstverständlich und auch Interpunktion und Rechtschreibung haben in Foren Daseinsberechtigung. (natürlich nicht Bewerbungs-Perfekt). Hmm...merke grad das es OT wird :)
Das ist hier ebenfalls gewünscht.
Iluya hat geschrieben:Wie berechnest du denn dann für dein Array die jeweiligen Bitfolgen? Oder baust du dafür den Baum auf und speicherst dann die Werte in einem Array? Würde beim (De-)Codieren wahrscheinlich mächtig Zeit einsparen :idea:
Naja, es ist eigentlich nur ein halber Huffman, der sich in erster Linie daraus kennzeichnete, dass es nur zwei Bitmusterlängen gab: 7 und 14 Bit.
Aufgrund dieser Tatsache war es einfacher und schneller mit einem Array als Bäume aufzubauen.
Die Aufgabe war einen Algorithmus zu finden, der besser komprimiert als UUEncode oder Base64, ohne Binärdaten zu verwenden.

Damit brauche ich grundsätzlich 7-Bitzeichen. Wenn ich also einen 8 Bit-Zeichen speichern musste, bauchte ich ein Zielzeichen + 1 Bit benötigte. das Ziel war also nicht, auf möglichst kurze Bitfolgen zu kürzen, sondern zunächst eine Abbildung zu finden: ein Byte wird auf zwei Zielzeichen abgebildet, je ein Nibble auf einem Zielzeichen. Dabei werden von 128 Möglichkeiten des Zielzeichens 16 verbraten. Heißt: es bleiben 112 Zeichen über, die verschwendet werden. Abzüglich der Binärzeichen bleiben 80 über. Nun zähle ich die Zeichen und damit die Häufigkeit. Anschließend sortiere ich die Zeichen und weise den häufigen Zeichen eins von den 80 Einzelzeichen zu, so dass eine 1:1 Abbildung entsteht. Das entspricht dem Huffmann der statt einem binären Zahlensytem ein 128er Zahlensystem verwendet, wo die Frage ist, ob man zwei Ziffern braucht, oder mit einer auskommt.
Während base64 eine konstate Rate von 3:4 hat, kommt mein Algorithmus im Idealfall auf annähernd 1:1.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: c:huffman

Beitrag von Xin » Mo Jul 23, 2012 11:37 am

Hier spült sich die Seite im Rahmen der Wiki-FIXME-Bekämpfungsaktion wieder nach oben.

Nachdem Iluya nun schon einige Zeit nicht mehr online war, gehe ich davon aus, dass hier auch nix mehr kommt und der Artikel auf die globale Todo-Liste wandert?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten