Diskussion:Tunstall-Kodierung

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 10 Jahren von Wdwd in Abschnitt Fehlerhaft
Zur Navigation springen Zur Suche springen

Fehlerhaft

[Quelltext bearbeiten]

Die Beschreibung des Algorithmus ist fehlerhaft. Es wird behauptet, dass in jedem Iterationsschritt die Wahrscheinlichkeit für die jeweiligen Sequenzen, z.B. ‚ll‘ ‚lo‘ und ‚ld‘ ermittelt wird, was zum einen ziemlich aufwändig wäre, zum anderen die Frage aufwirft, warum man dann überhaupt noch Codewörter für Knoten reserviert, deren Wahrscheinlichkeit gleich null ist, wie z.B. ‚lh‘ und ‚lr‘.

Der Algorithmus ist wesentlich einfacher. Er nimmt für die Knoten als Wahrscheinlichkeit das Produkt der Wahrscheinlichkeiten der einzelnen Zeichen an, womit es niemals Knoten mit der Wahrscheinlichkeit null gibt, aber natürlich die angenommene Wahrscheinlichkeit von der tatsächlichen Häufigkeit abweichen kann. Das ist wahrscheinlich ein Zugeständnis an die Ausführungsgeschwindigkeit.

Würde man dagegen in jedem Iterationsschritt eine Analyse der tatsächlichen Häufigkeit der Blätter durchführen, müsste man eigentlich auch alle anderen Knoten unter Berücksichtigung der Kodierung neu evaluieren. So ist z.B. die Häufigkeit des Zeichens ‚d‘ im Beispiel gleich null, sobald für ‚ld‘ ein eigenes Codewort reserviert wurde, da es alleinstehend gar nicht mehr vorkommt. Aber das wäre ein anderer (wesentlich aufwändigerer) Algorithmus. (nicht signierter Beitrag von 77.185.247.192 (Diskussion) 20:54, 18. Apr. 2013 (CEST))Beantworten

Bin ich auch der Meinung, denn soweit ich lesen kann beschreiben die beiden Quellen (Bossert und MIT) ein Beispiel bei dem nur die Wahrscheinlichkeitsverteilung gegeben ist. Ich verstehe nicht wieso das dann bei einem konkreten Beispiel anders sein sollte und man zusaetzlich die bedingten Wahrscheinlichkeiten zuzieht. (Bevor ich aber Hand anlege, einen ping an den Autor @Wdwd:)
Falls wir aber falsch liegen, wuerde das in meinen Augen bedeuten dass der Tunstall Parser ein Gedaechtnis hat... In beiden Faellen ist eine Ueberarbeitung des Artikels notwendig. --McZusatz (Diskussion) 20:27, 8. Aug. 2014 (CEST)Beantworten
Bitte lege Hand an. Das Beispiel als Versuch einer Darstellung ist an die schon vorhandenen Grafiken der en.wp angelehnt.--wdwd (Diskussion) 22:10, 8. Aug. 2014 (CEST)Beantworten