Diskussion:Shannon-Fano-Kodierung

Faszinierend. Erstens: ein Beweis in einem Lexikon - schon schräg. Zweitens: Die Eigenschaft "optimal" (beim Huffman-Kode) wird bewiesen, ohne das "optimal" vorher definiert wird. Wo ist eine Definition für "optimal"? Und wo soll dieser Übergang zu einem Mathebuch hinführen? Trotz der hingebungsvollen Formatierung würd ich das Ganze rausschmeissen (will aber nicht nicht als Vandale auftreten).

--- (nicht signierter Beitrag von 87.187.160.184 (Diskussion | Beiträge) 01:10, 7. Jan. 2010 (CET))

Also solche Kommentare sollten wohl eher nicht in eine Enzyklopaedie. "(Die Suche nach „dynamic Huffman“ liefert einige Ergebnisse.)"

---

Zum Beweis: 1. Warum so aufwändig Lemma 1 bis 3 beweisen? Dies folgt doch alles direkt aus der Konstruktionsanleitung des Huffman-Baumes. 2. Der eigentliche Beweis über Induktion erscheint nicht sehr verständlich?

Zu beweisen, dass der (Huffman-)Baum, den der Algorithmus generiert, optimal ist, indem der Algorithmus als Beweismittel verwendet wird, ist nicht gerade sinnvoll, oder? Dass am Ende von einem "Eigentlichen Beweis" gesprochen wird, halte ich auch für recht unglücklich formuliert, da die Lemmata ja bereits zum Beweis gehören. Da es um den Huffman-Baum und nicht um den Algorithmus zur Erstellung geht, bin ich mir auch nicht sicher, ob ein vollständiger Korrektheitsbeweis des Algorithmus (vollst. Ind.) in die Wikipedia gehört (auch wenn ich einige Studenten wüßte, die außer der Wikipedia keine Quellen zu kennen scheinen und dafür natürlich dankbar wären). --DAD6439C 09:23, 30. Jun 2006 (CEST)

---

Müsste es nicht 1<=i<=n sein?

Von welcher Stelle sprichst Du? Was würdest Du damit ersetzen wollen? --DAD6439C 09:26, 30. Jun 2006 (CEST)

---

Sollte man neben der Kategorie Kompression, diese nicht auch zur Kategorie Veschlüsslung hinzufügen?

Mit welcher Begründung? Die beiden Verfahren haben nichts mit Kryptographie zu tun --DAD6439C 09:30, 30. Jun 2006 (CEST)

---

Warum ist bei der Shannon - Fano Codierung das A nicht mit dem E Zusammengefasst und der Rest bildet eine zweite Gruppe da 15 + 5 = 20 bzw. 6 + 6 + 7 = 19 viel dichter an den Mittelwert 19,5 herankommt ?

Weil der Algorithmus nicht so definiert ist...

Außerdem geht es nicht um den Mittelwert...

Du darfst gerne einen entsprechenden Algorithmus definieren, der dieses berücksichtigt, jedoch bezweifele ich, dass dieser Algorithmus besser ist als der Huffman-Code. Diese beiden Codes gehen davon aus, dass es am besten ist die Zeichen mit der geringsten Häufigkeit mit dem längsten Code zu versehen. Wenn man Dein Beispiel nehmen würde, so würde der folgende Code erzeugt werden:

A -> 00

E -> 01

B -> 10

C -> 110

D -> 111

Die folge wäre eine durchschnittliche Länge des Codes von:

${\frac {2bit*(15+5+7)+3bit*(6+6)}{(15+5+7+6+6)}}\approx 2{,}308bit/Zeichen$

Von daher ist Deine Idee nicht optimal für die Codierung.

--Herr Schroeder 10:38, 12. Mai 2005 (CEST)

Das ist alles schön und gut, aber der Algorithmus teilt nun mal entlang der sortierten Häufigkeiten. Ich habe die Änderungen rückgängig gemacht, die die ganze Partitionierung verdrehen. Vorher hatte ich noch einmal im Buch von Mark Nelson "The Data Compression Book" nachgelesen habe. Die Werte für das Beispiel stammen aus diesem Buch. Außerdem habe ich die entsprechende Sektion aus Shannons Text "Mathematial Theory of Information" gelesen. Das ist dort zwar sehr mathematisch beschrieben scheint aber, nach meinem Verständnis, auch auf ein Sortieren und dann entlang dieser Reihenfolge Zerteilen hinauszulaufen. Zum besseren Verständnis habe ich auch noch einen Satz zur Zerteilung geschrieben. --Andreas.Roever 5. Jul 2005 16:59 (CEST)

Soeben wurde der Vorschlag gemacht, dass der Huffman-Algorithmus das Partitionierungsproblem des Shannon-Algorithmus löst. Das ist falsch, wie man leicht an dem gegebenen Beispiel sehen kann. Die Partitionierung bei diesem Beispiel ist für den Huffman Baum sogar schlechter 15 zu 24 im Gegensatz zu 17 und 22 bei Shannon. Ob ein Baum gut oder Schlecht ist ergibt sich nicht aus der perfekten Partitionierung, sondern wie nahe die sich daraus ergebenden Codelängen an der Entropie liegen. Ein Beispiel: Ein Alphabet mit 4 Zeichen A, B je 50 mal und C und D je 1 mal. Die perfekte Partitionierung führt dazu, dass jedem Zeichen die Codelänge 1 zugewiesen wird, da die erste Partition A und C bzw. B und D zusammen fasst (jeweils 51). Ein bessere Code aber gibt A 1 Bit langen Code, B 2 Bits und C und D je 3 Bits. Es wird also einem der Häufigen Zeichen auf kosten der seltenen ein kürzerer Code zugewiesen -> weniger Bits (156 im Gegensatz zu 204) --Andreas.Roever 7. Jul 2005 17:50 (CEST)

Aufsplittung

Ich bin für die Aufsplittung dieses Artikels in die Artikel Shannon-Fano-Kodierung und Huffman-Kodierung (derzeit redirect des zweiten zum ersten). --Abdull 18:17, 9. Mär 2006 (CET)

Ich hatte die beiden Algorithmen zusammen beschrieben, weil beide die gleiche Idee, auf einem binären Baum basierend zu arbeiten, benutzen. Der Unterschied ist ja nur, wie der Baum genau erstellt wird.

Wenn man den Artikel aufsplittet, dann muß der Vorspann, der die Sache mit dem Baum erläutert, theoretisch in beiden Artikeln vorhanden sein. --Andreas.Roever 13:00, 10. Mär 2006 (CET)

Es würde ein einem der Artikel ein kurzer Abschnitt mit einer entsprechenden Referenz reichen. Grundsätzlich halte ich eine Aufteilung auch für sinnvoll (zumal in der Praxis heute (fast) nur Huffman angewendet wird und sich die hieran interessierten Menschen so in einem recht langen Artikel zurechtfinden müssen) --DAD6439C 09:30, 30. Jun 2006 (CEST)

Trotz der Ähnlichkeit (die letzdenendes allen Entropiekodierungen inne wohnt) bin ich doch auch sehr für ein aufteilen in zwei Artikel, vor allem da (a) die Fachwelt diese Methoden auch als zwei unterschiedliche behandelt, (b) jedes der beiden Themen von seiner Beschreibungslänge her einen eigenen Artikel wert ist und nicht zuletzt (c) auch ausserhalb der Fachkreise der Begriff Huffman-Kodierung weite Bekanntheit errungen hat, Shannon-Fano-Kodierung jedoch weniger und mir daher "nur" eine Umleitung für die Huffman-Kodierung unangemessen erscheint. (Und natürlich gibt es dann noch Argument (d), dass die anderen internationalen Wikipedias dies wohl auch getrennt zu behandeln scheinen.) --MRA 10:26, 14. Sep 2006 (CEST)

Lange Diskussion, aber kein Ergebnis, warum wird es nicht endlich gespalten?--84.60.238.49 12:28, 13. Okt. 2006 (CEST)

Ich werde den Artikel spalten, sobald ich die Informatik-Klausur geschrieben habe. Was die redundante Beschreibung angeht: Eine gewisse Redundanz gibt es doch in jeder Enzyklopädie, und schließlich liegt es in der Macht des Autors, unnötige Wiederholungen durch die Verwendung von Links zu vermeiden...--Leonhardt 14:26, 21. Jan. 2007 (CET)

„Spalter! Spalter!“

;-)--Speck-Made 21:28, 7. Dez. 2007 (CET)

Beschleunigungsalgorithmen

„Die zeiteffiziente Implementation scheitert oft an ...

Es gibt aber effiziente Algorithmen, um diese Prozesse zu beschleunigen (siehe zlib Bibliothek: [Verweis auf zlib-Website])“

– war im Artikel zu lesen. Was ist denn hier gemeint? Wegen welcher Informationen war dieser externe Verweis denn hier drin?
Ich hab' den entfernt, da es jetzt mittlerweile zlib einen eigenen Artikel hat, auf den ich stattdessen verwiesen hab.
Könnte jemand™ diese unbekannten Informationen über diese Beschleunigungsalgorithmen vielleicht in den zlib-Artikel einbringen?--Speck-Made 21:28, 7. Dez. 2007 (CET)

Shannon-Fano nicht optimal

Sollte man vielleicht erwähnen, gerade da Huffman ideal ist. Wir haben sogar schon das richtige Beispiel im Artikel. Ein Bit für A und drei für die anderen Zeichen ergibt 2.23 Bits/Zeichen, was besser ist. --mfb (Diskussion) 14:46, 2. Feb. 2016 (CET)

Das sollte man auf alle Fälle erwähnen! So wie es jetzt da steht, suggeriert der erste Teil des Artikels, dass die Shannon-Fano-Codierung optimal ist: "Das ... Problem ist es, einen solchen Baum zu erstellen, bei dem die durchschnittliche Anzahl der Fragen ... im Mittel möglichst klein ist... Shannon-Fano-Kodierung und Huffman-Kodierung sind zwei unterschiedliche Algorithmen zur Konstruktion dieser Bäume."

Kitaktus 194.31.198.72 10:05, 10. Jan. 2017 (CET)

Gar nicht mehr an diesen Abschnitt gedacht. Ist jetzt eingebaut. --mfb (Diskussion) 14:53, 10. Jan. 2017 (CET)

Beispiel fehlerhaft ?

Unter Beispiel wird die erste Aufspaltung so beschrieben:

"Die Hälfte der Wahrscheinlichkeitssumme ist 19,5. 15 ist 4,5 unter diesem Halbwert, 15+7 hingegen nur 2,5 darüber – eine bessere Partitionierung gibt es nicht."

Ist nicht A,E=20 und B,C,D=19 die ideale Aufspaltung ? --93.214.200.253 14:33, 3. Jul. 2016 (CEST)

Das widerspricht der Regel "teile sie entlang dieser Reihenfolge in zwei Gruppen". A,E gäbe eine bessere erste Gruppe, aber dann verliert man später - wenn nämlich der Unterschied zwischen "A" und dem viel selteneren "E" immer ein Bit benötigt. --mfb (Diskussion) 14:55, 10. Jan. 2017 (CET)