Diskussion:Arithmetisches Kodieren

aus Wikipedia, der freien Enzyklopädie

Verweis auf CABAC wäre auch angebracht

CABAC (Context Adaptive Binary Arithmetic Coding) ist praktisch die verbesserte Version der Arithmetischen Kodierung. -- 84.164.43.150 17:00, 30. Mär. 2009 (CEST)

Erfinder

Wer ist jetzt eigentlich der Erfinder der Arithmetische kodierung? Ist es IBM mit ihrem Q-Coder, oder gab es die Idee schon vorher? Irgendiwe scheint das keiner zu wissen...

Auszug aus dem Artikel von Bodden et al. (hier zu finden): ... seit Ende der 70-er Jahre bekannt ... Erste Ansätze ... 1960 von Elias und Abramson ... 1976 [...] Pasco und Rissanen ... 1979 und 1980 erschienen dann fast zeitgleich Artikel von Rubin, Guazzo, Rissanen und Langdon, die einen Algorithmus beschrieben, wie er auch heute noch zur Arithmetischen Kodierung genutzt wird. --77.12.203.253 21:35, 16. Jan. 2009 (CET)

Verständnisfragen

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)

Wenn ich in meiner Vorlesung richtig aufgepasst habe und das Skript korrekt ist, dann ist die Huffman-Codierung nicht nur asymptotisch optimal, sondern sogar kompakt. Es geht also nicht besser. Damit allerdings auch die erwartete Codelänge möglichst nah an der Entropie liegt, muss die Alphabetgröße groß werden, und da liegt das Problem: Bei großen Alphabeten kommt man aufgrund der Wahrscheinlichkeitssortierung bei Huffman nicht unter eine Laufzeit von O(n*log(n)).

Wenn das zutrifft, dann stimmen einige Fakten des Artikels nicht: 1. Huffman ist optimal. 2. Huffman ist bei kleinen Alphabeten oft nicht nah an der Entropie. 3. Huffman ist langsam bei großen Alphabeten. 2 + 3 => Man verwendet Arithmetische Codierung, weil sie schneller ist, und nicht weil sie besser ist.

Oder hab ich was falsch verstanden? --89.57.208.138 00:02, 16. Feb. 2007 (CET)

Spät aber jetzt doch noch eine Antwort: Huffman ist eine optimal mit der Vorraussetzung nur "ganze" Bits zu verwenden. (Genauso wie Quicksort nur optimal ist, wenn man voraussetzt immer nur 2 Werte zu vergleichen).
Das Alphabet sollte möglichst groß sein, damit die Wahrscheinlichkeiten möglichst klein sind und die durch die Entropie erforderliche Bitzahl möglichst groß. Der Fehler wid dann kleiner, da er bei einer Entropie von 0.5bits nun mal 1/2 ist bei einer Entropie von 7.5bits aber nur 15/16.
Huffman ist *nicht* langsam. Das Erstellen des Hufmannbaumes kostet ein wenig Zeit. Diese kann aber bei statischen Entropiemodellen ignoriert werden. Dynamisches updaten des Baumes ist teuer, aber trotzdem relativ schnell zu erledigen. Arithmetisches Codieren ist langsam, weil das codieren eines einzelnen Zeichens teuer ist (komplizierte Multiplikationen und Divisionen, währen bei Huffman alles mit shiften zu erledigen ist)
Arithmetische Codierung ist besser, da sie (theoretisch) die Zeichen mit einer der entropie entsprechenden Bitzahl ablegen kann, während Huffman das nicht kann. Huffman kann nur ganze Bits verwenden.--Andreas.Roever 17:13, 12. Jun. 2007 (CEST)

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)


Ich finde das Verfahren nicht wirklich gut erklärt. Erst diese Information machte überhaupt klar wieso hier rumgerechnet wird: "Gespeichert wird eine beliebige, möglichst kurze Zahl aus dem letzten Intervall, also z. B. 0,336."

Datei:Arithmetische Codierung.png

Ohne diese Information war der gesamte Text bis dahin absolut unklar. Diese Information sollte also ganz weit oben hin. Den gesamten Algorithmus kann man, wenn ich ihn richtig verstanden habe, so zusammenfassen: "Die Form der Codierung basiert auf der Idee einen Text beliebiger länge als eine Zahl (x) zu speichern. Diese Zahl stammt aus einem Wertebereich welcher nach einer, dem Kodierer und Dekodierer bekannten, Vorschrift in kleinere Intervalle zerlegt wird. Die gespeicherte Zahl x liegt immer(!) im aktuellen Intervall. Die Position des aktuellen Intervalls repräsentiert ein Zeichen (dieses ist Kodierer und Dekodierer bekannt). Nachdem dieses Zeichen ausgegeben wurde, wird das aktuelle Intervall wieder zerlegt. Diese Dekodierung wird solange fortgesetzt bis eine vorgegebene Menge an zeichen dekodiert wurde." Ich hab das ganze mal als Bild hochgeladen (siehe rechts). Wenn das Bild mal jemand ordentlich ausgestalten und Hochladen könnte, würde das sicher einige Fragen klären. --KFlash 00:14, 5. Feb. 2008 (CET)

Das Bild von KFlash ist super. Damit habe ich es sofort verstanden. Das Bild im Text finde ich bei weitem nicht so anschaulich. Das liegt wahrscheinlich an der einfarbigen, verschachtelten Darstellung. --176.198.29.45 15:43, 1. Jan. 2012 (CET)

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>

Toter Weblink

Bei mehreren automatisierten Botläufen wurde der folgende Weblink als nicht verfügbar erkannt. Bitte überprüfe, ob der Link tatsächlich unerreichbar ist, und korrigiere oder entferne ihn in diesem Fall!

--Zwobot 23:54, 26. Jan. 2007 (CET)

erledigt --Jan Rieke 00:07, 16. Feb. 2007 (CET)

Braucht man wirklich reelle Zahlen?

So wie ich den Algorithmus verstanden habe, kommt er in vielen Fällen auch mit rationalen Zahlen aus. Geht man zum Beispiel von einer statistischen Verteilung aus, ist die Wahrscheinlichkeit für jeden einzelnen Fall immer eine rationale Zahl. Alle weiteren Operationen ergeben wiederum rationale Zahlen.

Ich frage ja nur, weil reale Computer mit rationalen Zahlen im Gegensatz zu reellen Zahlen hervorragend umgehen können.

Woher auch immer diese Behauptung stammt, aber eigentlich können Computer hervorragend mit Integer (Ganzzahlen) umgehen. Bei rationalen Zahlen tritt das selbe Problem wie bei reellen Zahlen auf. Versuchen Sie mal 1/10 binär darzustellen. --84.170.155.108 05:43, 22. Mär. 2019 (CET)

Q-Coder und Patent?

Wie lautet denn die Patentnummer zu diesem Q-Coder Algorithmus? Das sollte man als Quellenangabe in einem Wikipedia Artikel eigentlich schon angeben. --84.59.5.229 00:25, 29. Apr. 2011 (CEST)

Division bei Range-Codierung

Im Artikel wird behauptet, das für jedes Zeichen bei einem Range-Codierer eine Division benötigt wird. Davon findet sich nichts im zugehörigen Hauptartikel und vorher war lediglich von Addition und Multiplikation die Rede. Diese ist zwar auch aufwendig aber trotzdem keine Division. Woher kommt jetzt die Behauptung, der Range-Codierer würde Divisionen benötigen? --84.170.155.108 05:42, 22. Mär. 2019 (CET)

Unnötig kompliziert

Der Artikel ist unnötig umständlich formuliert (ganz zu schweigen vom englischen Pedant). Auch ist die Formel für die Berechnung der nötigen Codewortlänge falsch, da das Minuszeichen ausserhalb der Rundung nach oben steht und man damit ein bzw. zwei Bits zu kurze Längen erhält. Auch ist die Aussage, dass man ein Bit weniger bräuchte, wenn das x genau eine (negative) Zweierpotenz ist im Allgemeinen falsch. Wenn man Pech hat, und der betrachtete Bitstream der die zu decodierende Nachicht codiert enthält in einen weiteren Bitstream eingebettet ist, so dass noch Bits, die aber zu anderen Teil des Gesamtbitstreams gehören, existieren, dann könnte die Summe der nachfolgenden Bits (interpretiert als Teil der Binärdarstellung der Nachrichtenwahrscheinlichkeit) dazu führen, dass die decodierte Wahrscheinlichkeit aus dem ursprünglich gemeinten Wahrscheinlichkeitsintervall rutscht. (nicht signierter Beitrag von 77.1.120.75 (Diskussion) 22:42, 20. Jul. 2019 (CEST))

Abgerufen von „https://de.wikiup.org/index.php?title=Diskussion:Arithmetisches_Kodieren&oldid=190598492“