392121 Datenkompression (BS) (SoSe 2012)

Vorstellung von Methoden wie Prediction by Partial Matching (PPM),
Context Tree Weighting (CTW) und deren Derivate.
Zunächst wird die Frage behandelt: “Was ist Datenkompression?”
Dazu nähern wir uns dem Problem in 6 Schritten:

1. Betrachtung verschiedener Codes
2. Codieren auf Symbolen
3. Codieren auf Sequenzen von Symbolen
4. Codieren mit unbekannten Verteilungen
5. Codieren mit unbekannten Abhängigkeiten
6. Die Varianten PPM und CTW

1. Verschiedene Codes

• Wann haben wir gut komprimiert?

• Grundlegende Definitionen
– Symbole, Sequenzen, Bäume, Codes

• Eigenschaften verschiedener Codes
– Blockcodes, singuläre Codes, eindeutig dekodierbare Codes,
sofort dekodierbare Codes

– Prefixcodes, Huffman-Codes, fixfree-Codes, Shannon-Fano-Codes,
alphabetic Codes

• Existenz von Codes
– Kraftungleichung Prefix Codes, Kraftungleichung UDC, 3/4 -Vermutung

2. Codieren auf Symbolen

• Wahrscheinlichkeitsverteilung auf Symbolen

• durchschnittliche Codewortlänge

• Messen der Ungewissheit

– Shannon-Entropy,
I-Divergenz (Kullback-Leibler-Information), Renyi-Entropy

• Noiseless Coding Theorem (NCT)

3. Codieren auf Sequenzen

• Finalisierung Codieren auf Symbolen

– Codieren als injektive Abbildung, NCT mit Renyi-Entropy, Schranken
Symbolcodierung auf Sequenzen

• Shannon-Fano-Codes, arithmetic coding

• Verallgemeinerung der bisherigen Schranken z.b. H∞

4. unbekannte Verteilung

• Schätztheorie
– Krichevski-Trofimov estimator,
α-ary Dirichlet estimator

• Schranken mit geschätzter WV

5. unbekannte Abhängigkeiten

• Definition verschiedener Quellen
– i.i.d,
stationär ergodisch, Markov-Ketten,
CT-Sources, FSMX-Sources

• Konvergenzgeschwindigkeit der Schätzungen bei verschiedenen Quellen

6. Die Varianten PPM und CTW

• PPM auf Markov-Sources

• Die Varianten A, B, C, D, X

• CTW

• eine weitere Quellenbetrachtung

• PPMZ