Diskussion:Arithmetisches Kodieren

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Verständnisfragen 1.1 Vergleich mit Huffman-Codierung 1.2 Verfahren 2 Kodierung vs. Komprimierung

[Bearbeiten] Verständnisfragen

[Bearbeiten] Vergleich mit Huffman-Codierung

Hallo! was mir nicht klar ist, wie ermittelt wird, das "0,336" in etwa 8 oder 9 bit entsprechen.

Entropie eines Zeichens aus einem Alphabet von 10 = ld 10 = 3.3219... multipliziert mit 2.5 (2 ganze Zeichen, beim letzten hat man eine größere Auswahl, also verwende ich in der Abschätzung ein paar bits weniger) ergibt 8.305.... Bit, also zwischen 8 und 9 Bits --Andreas.Roever 18:11, 6. Jan 2006 (CET)

Weder die Berechnung des Aufwands für die Huffman-Codierung noch die für die arithmetische Codierung sind exakt, obwohl sie eine gute Vorstellung von der Asymptotik liefern:

1. Huffman-Codierung: Zusätzlich zu den 10 bit für die Darstellung der drei Zeichen muß man bei der statischen Variante noch die Decodierungstabelle übertragen - bei dem kurzen Textbeispiel ist das eine erhebliche Verschlechterung. Bei der dynamischen Variante könnte dagegen das erste A noch nicht mit einem einzigen bit dargestellt werden, weil die globale Buchstabenverteilung noch nicht bekannt ist.

2. Arithmetische Codierung: Die kürzeste Binärzahl, die im gegebenen Intervall liegt, ist , kann also mit 7 bit codiert werden; zusätzlich muß die Länge der Binärzahl angegeben werden. Die Wahl von "0,336" im Text halte ich für etwas irreführend, weil für die Codierung dieser speziellen Dezimalzahl deutlich mehr bits benötigt werden.

Sicherlich wäre es verwirrend, all diese Kleinigkeiten im Text zu erwähnen. Andererseits ist der Text hier etwas unpräzise; vielleicht könnte man das ausräumen, indem man den Codierungs-Aufwand für eine millionenfache Wiederholung der Zeichenkette angäbe? --FRR 19:09, 6. Jan 2006 (CET)

zu 1: diese Tabelle muß sowohl bei Huffman als auch beim arithmetischen Kodierer übertragen werden. Allerdings läßt sie sich bei Huffman durch übertragen der fertigen Huffmancodes (siehe ende des Huffmanartikels) effizienter übertragen. Der arithmetische Kodierer würde eine vollständige Wahrscheinlichkeittabelle benötigen. Andererseits sind das Probleme des Kodier-Modells (siehe Artikel Entropie Kodierung). Bei der Betrachtung des Kodierers wird das Modell stets vernachlässigt.

zu 2: Das ganze Beispiel ist dezimal gerechnet, dashalb wollte ich nicht für die Berechnung der Bits binär werden. Die Länge der Bitzahl wird normalerweise explizit nicht mit angegeben, da alle Entropiekodierer sie benötigen würden, um das Ende des Bitstroms zu erkennen. Das Ende des Bitstroms wird normalerweise über das Betriebssystem geregelt, indem z.B. die Größe der Datei begrenzt ist. Die eventuell bis zu 7 zusätzlichen Bit können vernachlässigt werden, so lange nur alle signifikanten Bits ausgegeben wurden. --Andreas.Roever 10:40, 7. Jan 2006 (CET)

zu 1: Die Notwendigkeit der Übertragung einer statischen Tabelle im arithmetischen Modell hatte ich übersehen. --FRR 11:04, 7. Jan 2006 (CET)

M.E. verträgt sich die Auswahl einer Beispielzahl aus dem Intervall nicht gut mit einer rein asymptotischen Betrachtungsweise, weil der asymptotische Aufwand nur von der Länge des Intervalls abhängt: Läge im Intervall "zufällig" die mit einem Bit codierbare Beispielzahl 1/2, so würde die arithmetische Codierung nur ein Bit benötigen (selbst wenn man sie dezimal als 0,5 darstellt, braucht man nach der obigen Darstellung nur ld 10 Bits), aber das Ergebnis ist nicht verallgemeinerbar.

Wenn man im Beispiel Binärzahlen verwenden würde, wäre es nicht mehr nötig, die oben gestellte Frage zu beantworten, in welchem Sinne eine "Dezimalzahl, bei der man in der letzten Dezimalstelle Auswahl hat" eine bestimmte Anzahl von Bits (dann doch wieder in Binärdarstellung?) benötigt. Sogar die Länge des Intervalls im Beispiel ist binär eher übersichtlicher als dezimal, und wenn man die binären Intervallgrenzen konkret angibt, vermeidet man die Notwendigkeit einer Berechnung. --FRR 11:52, 7. Jan 2006 (CET)

[Bearbeiten] Verfahren

Irgendwie werd ich aus der Beschreibung nicht schlau, wie genau diese Kodierung funktioniert. :-( Ich würd ja gern den Ausdruck hier und da verbessern, aber ohne das Verfahren zu verstehen, bastele ich da nichts größeres an dem Text herum.

Auch sollte zwischen Kodierung und Komprimierung unterschieden werden. Denn nicht immer ist die Arithmetische Kodierung auch eine Komprimierung, oder? (da ein Algorithmus, der jede Bitfolge komprimieren kann, ist ja bekanntermaßen nicht möglich ;-)) --RokerHRO 16:48, 12. Sep 2004 (CEST)

Hm, das mit der Unterscheidung ist ein bisschen schwierig: jede (verlustfreihe) Komprimierung ist eine Kodierung, und für jede Komprimierung gibt es patologische Fälle, bei denen das Ergebnis nicht kleiner (und manchmal sogar grösser) als die Ausgangsdaten sind. Komprimierungen lassen sich formal nicht von Kodierungen unterscheiden - dass eine bestimmte Kodierung relativ effizient ist, ist ein Erfahrungswert. Kodierungen, die aus diesen Grund verwendet werden, werden eben als Komprimierung bezeichnet, besonders dann, wenn sie sich auf amorphe Datenmengen anwenden lassen, ohne den sematischen Kontext zu kennen (was allerdings bei der Bildkompression nicht gegeben ist, und vorallem nicht bei verlustbehafteten Kompressionsverfahren). Die Arithmetische Kodierung ist halt eine recht effiziente Kodierung, und wird deshalb auch als Komprimierung bezeichnet. (Verstanden habe ich das Verfahren aber auch nicht) -- D. Düsentrieb (?!) 16:55, 12. Sep 2004 (CEST)

ok ich hab's verzapft :-) An könnt ihr mir sagen, an welcher Stelle der Verständnis verloren geht? Bei der Sachen mit Kodieren und Komprimieren stimme ich mit D. Düsentrieb überein. Wenn es um Komprimieralgorithmen geht sollte es erlaubt sein komprimieren mit kodieren gleich zu setzen, auch wenn nicht jede Kodierung wirklich ein Erfolg ist. --Andreas.Roever 17:00, 12. Sep 2004 (CEST)

Erst mal danke für einen ausführlichen Artikel zu einem komplexen Algorithmus. Ich versuche mal ein paar Kritikpunkte aufzulisten. Mit dem Beispiel und vorallem dem Diagramm (danke!) hab' ich mir das Konzept ungefähr zusammenreimen könne, aber:

• Die abstrakte Erläuterung ist sehr kurz und wenig strukturiert. Der Begriff Zeichen taucht dort aus dem nichts auf. Die wiederholte verwendung von x hilft auch nicht wirklich.
• Die Dekodierung wird vor der Kodierung erläutert - das verwirrt
• Ich kann mir noch immer nicht vorstellen, wie die Dekodierung funktioniert. Ein Beispiel wäre prima.
• Es wird nicht klar, wie das ohne die Verwendung beliebig genauer Zahlen funktioniert - so, wie es da steht, funktioniert das nur wenn man nur zwei Zeichen zu kodieren hat, die eingabe also bitweise liest... macht das sinn?
• Es wird nicht klar warum das Funktioniert, oder warum das eine bessere Kompression als die Huffman-Kodierung ist.
• Es wäre interessant zu erfahren, warum das in der Praxis wenig anwendung findet.

Ich hoffe, das hilft... -- D. Düsentrieb (?!) 18:38, 12. Sep 2004 (CEST)

ok, ich habe mal versucht die Punkte zu verbessern. Zur Implementation kann man eigentlich lauter eigene Artikel für die einzelnen Kodierer schreiben. Ich habe nur versucht zu erläutern, wie die auftretenden Probleme gelöst werden. Es kann jetzt also weiter kritisiert werden.

Ich bin gewillt den Inhalt so lange zu bearbeiten, bis es verständlich wird. Ausdruck und Grammatik sind leider nicht meine Stärken :-( --Andreas.Roever 17:57, 13. Sep 2004 (CEST)

So, ich bin da jetzt nochmal drüber gegangen - von mir aus kanns so bleiben. Vielen lieben Dank! -- D. Düsentrieb (?!) 18:54, 13. Sep 2004 (CEST)

Immernoch Dekodierung vor Kodierung. Eventuell kann der Teil des Algorithmusses, den Kodierer und Dekodierer ausführen, davor geschrieben werden.

Des Weiteren ist der Ausdruck ist etwas ... umgangssprachlich: "erstmachen wir das, dann kommt das, doch zunächst das". Die Anzahl der Vorwätsverweise sollte ebenfalls reduziert werden; es ist klar, dass nicht alles am Anfang behandelt und erklärt werden kann, sondern dass das nacheinander geschieht. ;-)

Sag Bescheid, wenn du das nicht machen willst, kümmere ich mich darum. Aber ich denke, man sollte dem Originalauthor Gelegenheit geben, seinen Artikel zu verbessern, ehe man ihn ungefragt "verhackstückt" ;-)

--RokerHRO 19:12, 13. Sep 2004 (CEST)

Ich bin der Meinung Dekodierer vor Kodierer ist besser, wenn Du aber denkst, das anderherum besser ist... ich werde Deine Änderung nicht rückgängig machen. Ich weiss nicht, wie man es besser begreifen kann. Es passt hier zwar nicht ganz, aber manche Kodierer so designt, dass erst der Dekodierer entwickelt wird und dann ein Algorithmus der einen passenden Datenstrom für diesen Dekodierer. In dieses Fällen ist der Dekodierer oft extrem einfach und hier ist es besser den Dekodierer zuerst zu beschreiben. Ich denke ein ähnlicher Fall ist das hier.

zum Ausdruck: Wollen schon, aber ich befürchte, das ich dabei nur "verschlimmbessere". Ganz besonders bei eigenen Texten werde ich extrem blind für enthaltenen Blödsinn. Mach also, wenn Du willst. Falls inhaltliche Fehler auftreten behebe ich die schon wieder. --Andreas.Roever 19:35, 13. Sep 2004 (CEST)

Also, in diesem speziellen Fall würde ich auch sagen, dass der Dekodierer vor dem Kodierer stehen sollte, weil sonst das "warum" beim Kodieren nicht klar ist. In der alten version war das verwirrend, jetzt finde ich es OK weil das Vorgehen erläutert wird. -- D. Düsentrieb (?!) 20:16, 13. Sep 2004 (CEST)

[Bearbeiten] Kodierung vs. Komprimierung

Nunja, ich hab z.B. auch die Huffman-Kodierung als "Kodierung" kennen gelernt. Dass der Zweck dieser Kodierung der ist, dass dadurch bei typischen Eingabedaten eine Komprimierung erreicht wird, ist ja ganz nett, ändert aber nichts an dem Algorithmus und seiner Funktionsweise, welcher einer (umkehrbar eindeutige) Abbildung (a.k.a. Kodierung) darstellt. Darum heißt der Artikel ja auch "Arithmetische Kodierung" :-)

Allenfalls bei dem "Warum" wird es interessant, also warum diese Kodierung eben typische Eingabedaten in der Regel komprimiert (und aus diesem Grunde ja überhaupt erst angewendet wird.)

Im Übrigen: Alle Komprimierungsverfahren vergrößern die Datenmenge für die meisten der möglichen Eingabedaten. Aber für typische Eingabedaten (welche nur einen Bruchteil der möglichen Eingabedaten ausmachen) erreichen sie eine Reduktion der Datenmenge. Es wäre somit bei der Arithmetischen Kodierung interessant zu erfahren, welche Arten von Eingabedaten sie gut/schlecht/gar nicht komprimieren kann.

--RokerHRO 19:04, 13. Sep 2004 (CEST)

Jawoll Kodierung ist einfach nur den Text in eine andere Darstellungform zu überführen. Wenn es Dich beruhigt können alle Referenzen zum komprimieren entfernt werden, auch wenn ich denke, dass es kein Problem ist die beiden Begriffe hier als Sysnonym zu verwenden.

Das Warum und was muss hier nicht beschrieben werden. Das muss bei den Entropiekodierung beschrieben werden. Das ist übrigends auch ein von mir verbrochener Artikel. Schätzungsweise ähnlich unverständlich (oder eher noch schlimmer)

Was ist aber einfach: Texte, bei denen die Wahrscheinlichkeiten für die einzelne Zeichen zu jedem Zeitpunkt möglichst ungleichmäßig ist, also ein oder einige wenige Zeichen sehr wahrscheinlich, andere dagegen sehr unwahrscheinlich sind, lassen sich gut komprimieren. Texte bei denen alle Zeichen gleich wahrscheinlich sind nicht.

Das Warum? lässt sich mit Mittelwertberechnungen zeigen. --Andreas.Roever 19:26, 13. Sep 2004 (CEST)

schreibs in den Artikel rein. ;-) --RokerHRO 20:40, 13. Sep 2004 (CEST)

Las Kodieren vs. Komprimieren angeht: lass es so, wie es ist. Es ist ein Kodierer (bzw. eine Kodierung), die zur Kompression eingesetzt wird. Korrekt. -- D. Düsentrieb (?!) 20:14, 13. Sep 2004 (CEST)

Sehe ich auch so. :-) --RokerHRO 20:37, 13. Sep 2004 (CEST)

Sollte es nicht Kodierung statt Kodieren heißen? Stern !? 11:08, 14. Sep 2004 (CEST)

Arithmetische Kodierung ist ein Redirect auf diesen Artikel. Oder meinst du im Text? -- D. Düsentrieb (?!) 14:10, 14. Sep 2004 (CEST)</math>