Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Huffman-Codierung verstehen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Huffman-Codierung verstehen
Informatiklehrer
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 31.03.2020
Mitteilungen: 1
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-03-31


Hallo zusammen,
ich nehme mit meinen Schülern gerade die Huffman-Codierung durch. Mir ist aufgefallen, dass unterschiedliche Internetquellen den Algorithmus zum Codieren anders formulieren.

Überall heißt es:
1) Ordne die Zeichen nach ihrer Auftrittswahrscheinlichkeit.
2) Verschmelze rekursiv die beiden Zeichen bzw. Bäume mit geringster Auftrittswahrscheinlichkeit zu einem neuen Baum.

Jetzt habe ich in einigen wenigen Quellen bei Schritt zwei den Zusatz gefunden: Wenn es mehrere Möglichkeiten gibt, erzeuge einen Baum mit minimaler Höhe.

Meine Frage jetzt: Wie lautet die "echte" Huffman-Codierung? Gehört diese Erweiterung dazu oder nicht? Ich möchte meinen Schülern ja nichts falsches lernen.

(Ist das verständlich, oder soll ich noch ein Beispiel posten?)

Vielen Dank!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5874
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-03-31


Hallo Informatiklehrer,

willkommen auf dem Matheplaneten!

Hier findet man die Originalarbeit von Huffman. Oben auf Seite 3 ist ein Beispiel angegeben. In Spalte 5 werden zwei Knoten mit den W'keiten 0,08 und 0,1 verschmolzen. Für den Knoten mit der W'keit 0,1 gibt es dabei vier Wahlmöglichkeiten. Es wird nun aber nicht ein Knoten mit minimaler Höhe gewählt, sondern im Gegenteil der Knoten mit maximaler Höhe.

Der Zusatz ist also, wenn ich alles richtig verstanden habe, kein Bestandteil der "echten" Huffman-Codierung.

Grüße
StrgAltEntf

PS: Das Wort heißt "lehren" 🙃



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
traveller
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 08.04.2008
Mitteilungen: 2508
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-03-31


Hallo und herzlich willkommen im Forum.

Die Frage kann ich dir nicht beantworten, finde sie aber auch recht seltsam und unnötig.

Üblicherweise will man doch, dass ein Algorithmus ein eindeutiges Resultat ausgibt. Offenbar reichen dazu diese beiden Schritte nicht aus. Also braucht man irgendeine Auswahlregel. Wieso man gerade einen Baum mit minimaler Höhe auswählen soll und was, wenn mehrere Bäume minimale Höhe haben, weiss ich nicht.

2020-03-31 18:09 - Informatiklehrer im Themenstart schreibt:
Meine Frage jetzt: Wie lautet die "echte" Huffman-Codierung? Gehört diese Erweiterung dazu oder nicht? Ich möchte meinen Schülern ja nichts falsches lernen.
Inwiefern kann dies "falsch" sein, ob mit oder ohne den Zusatz? Wenn es unbedingt sein muss, kannst du ja Huffmans originale Veröffentlichung suchen. Da er diese aber wohl kaum selbst "Huffman-Codierung" genannt hat, sondern erst spätere Autoren mit Verweis auf ihn, muss diese nicht exakt der heutigen Verwendung derselben entsprechen.
Übrigens willst du wohl eher deinen Schülern nichts Falsches lehren.

Willst du deine Schüler echte Texte bearbeiten lassen (z.B. als Programmieraufgabe), dürften solche Mehrdeutigkeiten wohl sowieso nur äusserst selten vorkommen und ich würde den Zusatz zwecks besserer Klarheit weglassen. Es dürfte auch gar nicht mal so einfach sein, ein Programm zu schreiben, das alle Möglichkeiten findet, und schlussendlich würde dies doch den Fokus auf Unwesentliches legen. Sollte die Frage dann doch kommen, kann man es immer noch mündlich beantworten.

[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 10768
Aus: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-04-01


Hallo Informatiklehrer,
herzlich willkommen auf dem Matheplaneten!

Im Buch Information Theory, Inference and Learning Algorithms von David J. C. MacKay wird erklärt, dass man im Fall gleicher Wahrscheinlichkeiten eine willkürliche Wahl treffen kann, ohne dass sich etwas an den Eigenschaften des Codes ändert.

Servus,
Roland



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Informatiklehrer hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]