Vorwärts- / rückwärts-dynamische Entropiekodierung

[Meflin]

Moin moin,

Entropiekodierung (statistische Kodierung) ist ja erstmal relativ leicht nachzuvollziehen, solange man sich das statische Modell anschaut. Man muss ja nur die Zeichen zählen und entsprechend ihrer Häufigkeit kürzer oder länger kodieren.

Jetzt gibts ja aber auch das dynamische Modell, bzw. gleich deren zwei, nämlich die vorwärts-dynamische und die rückwärts-dynamische Entropiekodierung. Und da verstehe ich jetzt irgendwie überhauptnichtmehr was abgeht

1) Wo besteht der Unterschied zwischen vorwärts-dynamisch und statisch? Wenn beim vorwärts-dynamischen nach dem Kodieren eines Zeichens dessen Häufigkeit erhöht wird, wo liegt dann im Endeffekt der unterschied zum statischen (die Zähler für jedes Zeichen müssen ja dann am Schluss gleich sein!)? Und insbesondere verstehe ich nicht, wieso die Statistiken beim vorwärts-dynamischen Modell nicht mit übertragen werden müssen.

2) Wo liegt der Unterschied zwischen dem rückwärts-dynamischen und dem statischen Modell? Hier werden ja genau wie beim statischen vor dem Kodieren alle Zeichen gezählt, und dann während dem Kodieren wird beim Vorkommen eines Zeichens dessen Zähler verringert. Wieso? Was soll das bringen?


Nuja, ich hoffe es kann jemand etwas Licht in mein Dunkel bringen

[Satty67]

ich vermute mal...

bei der statischen Kodierung hast Du ja die Zuordnung der Zeichen zum Code über das ganze Dokument fest. Dadurch ergibt sich nur über das ganze Dokument eine optimale Kodierung.

Die dynamische Kodierung prüft permanent bei den verbleibenden Zeichen die Häufigkeit und ordnet die Zeichen neuem Code zu und bleibt so auch für Teilbereiche bei der optimalen Kodierung.

[Meflin]

Jo, aber wie soll man sich das konkret vorstellen?

Wenn man das mal am Beispiel "HELLOWORLD" durchexerzieren würde... Statisch wäre das ja dann z.B.

Code:

L    3    0
O    2    1
H    1    00
E    1    01
W    1    10
R    1    11
D    1    000

Also quasi kodiert

Code:

00  01  0  0  1  10  1  11  0  000

Aber wie sollte man jetzt da vorwärts- und rückwärtsdynamisch vorgehen?

[alzaimar]

Wir fangen mit einem bestimmten Kodierungsmuster mit irgendwelchen willkürlichen 'Häufigkeiten' an. Diese Anfangskodierung wird empirisch ermittelt.

Nun wird ein Zeichen kodiert. Anschließend erhöht man die Häufigkeit und passt das Kodierungsmuster an*.

Beim Dekodieren liest man den ersten Code, dekodiert das Zeichen und passt wieder das (De-)kodierungsmuster an.

Wo der unterschied zwischen Vorwärts und Rückwärts ist, weiss ich aber nicht.


*In der Realität wird man nicht jedes mal das Kodierungsmuster anpassen, weil das etwas zu lange dauern würde, denke ich.

[himitsu]

http://de.wikipedia.org/wiki/Entropiekodierung

wenn ich das richtig versteh, dann wird praktisch "Blockweise" Kodiert und ...

vorwärts dynamisch: ... praktisch die Verteilung über breits kodierte Zeichen/Blöcke bestimmt
(sozusagen in den vorherigen Blöcken, bzw. dem vorherigen Block, wärend des Kodierens mitgezählt und das Zählergebnis im nächsten Block zum Kodieren verwendet)

rückwärts dynamisch: ... erstmal der Block angesehn und vor der Kodierung dieser Block analysiert

statisch: ... vorher alle Daten analysiert und dann kodiert.



rückwärts dynamisch wäre dann sozusagen alles in blöcke aufgeteilt und dann jeder Block einzeln sozusagen statisch kodiert


@Meflin:

HELLOWORLDBYHIMITSU > HELLO + WORLD + BYHIM + ITSU

rückwärts dynamisch:
- HELLO analysieren
- und anhand der Analyse kodieren
- WORLD analysieren
- und anhand der Analyse kodieren
- BYHIM analysieren
- und anhand der Analyse kodieren
- ITSU analysieren
- und anhand der Analyse kodieren

vorwärts dynamisch:
- irgendwelche Standardwerte als Analyse laden (oder den ersten Block gegen die Definition analysieren)
- HELLO und anhand der Analyse kodieren
und währenddessen/parallel die Zeichen von HELLO mitzählen/analysieren
- WORLD und anhand der letzen Analyse kodieren
und währenddessen/parallel die Zeichen von WORLD mitzählen/analysieren
- BYHIM und anhand der letzen Analyse kodieren
und währenddessen/parallel die Zeichen von BYHIM mitzählen/analysieren
- ITSU und anhand der letzen Analyse kodieren
[und währenddessen/parallel die Zeichen von ITSU mitzählen/analysieren]


ich würde die Vor-/Nachteile dann so definieren:
statisch:
+ ein Wörterbuch (welches Zeichen wie kodiert wurde)
- wenn sich die verteilung über die gesamten Daten "öfters" mal ändert, ist es insgesamt zwar optimal kodiert, aber nicht in Bezug auf einzelne Blöcke

vorwärts dynamisch:
+ sind mehrere Blöcke nacheinander mit gleicher Verteilung, dann wären die nachfolgenden Blöcke gut kodiert
- der erste Block (nach Verteilungsveränderung) wäre nicht optimal kodiert
+ man benötigt aber nur ein oder garkein (wenn man zum Anfang ein Standardwörterbuch läd) Wörterbuch
(beim Standardwörterbuch könnte man ja anhand des Dateitypes schonmal ein "möglichst" Optimales auswählen)

rückwärts dynamisch:
+ jeder Block wird optimal kodiert
- aber für jeden Block wäre ein Wörterbuch notwendig

[Meflin]

@Himitsu: Den Wiki-Artikel kenne ich, finde ihn aber nicht sehr hilfreich. wie sicher biste dir denn bei deinen ausführungen ?

[himitsu]

Zitat von Meflin:

wie sicher biste dir denn bei deinen ausführungen ?

0,000005%

nja, so hab ich das halt verstanden und irgendwie klingts och logisch so

[Meflin]

Zitat von himitsu:

nja, so hab ich das halt verstanden und irgendwie klingts och logisch so

Hm, naja, das mit der rückwärts-dynamischen kann ich nicht so recht glauben. Das wäre ja ein eklatanter Datenoverhead (die ganzen Statistiken für jeden Block die ja alle mit übertragen werden müssen) und damit eigentlich genau das, was man durch die Kodierung entfernen wollte

[himitsu]

wenn der Block und der Kodierungsgewinn größer als die Statistik sind, dann hat man ja dennoch was gewonnen