Diskussion:Arithmetisches Kodieren

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 ${\frac {43}{2^{7}}}$, 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 ${\frac {3^{6}}{2^{18}}}$ 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)

Ich habe den Artikel umgeschrieben, die Beispiele arbeiten jetzt ausschließlich mit Bruchzahlen, da Dezimalbrüche in der Tat verwirrend waren und dadurch die Argumentation verwässert haben. --RolandIllig (Diskussion) 01:14, 9. Mär. 2023 (CET)

Dieser Abschnitt kann archiviert werden. RolandIllig (Diskussion) 01:14, 9. Mär. 2023 (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)