Seminar über Algorithmen: Datenkompression

Sommersemester 2014 - Günter Rote

Inhalt

Es gab schon eine erste Vorbesprechung am Dienstag, den 18. März 2014 um 14 Uhr, im Seminarraum 053. Bei diesem Termin können die ersten Themen vergeben werden. Diese Vorbesprechung ist nicht verpflichtend.

Ablauf

Wenn dieser Termin nicht eingehalten wird, wird der Vortrag abgesagt und kein Leistungsnachweis vergeben.

Die regelmäßige Teilnahme gehört selbstverständlich ebenfalls zu den Teilnahmebedingungen.

Generelle Literatur:

• David Salomon and Giovanni Motta (with a contribution by David Bryant): Handbook of Data Compression, 5th edition, Springer-Verlag (2009). ISBN 978-1-84882-902-2, insbesondere Kapitel 11: Other Methods. Wird unten als Handbook zitiert.

Themen

1. Anisa Al-Hafeedh, Maxime Crochemore, Lucian Ilie, Evguenia Kopylova, W. F. Smyth, German Tischler & Munina Yusufu, A comparison of indexed-based Lempel-Ziv LZ77 factorization algorithms, ACM Computing Surveys 45-1 (2013) 5:1-5:17.
2. Length-limited Huffman coding, optimale längenbeschränkte Kodes: der Paare-Verschmelze-Algorithmus von Hirschberg und Larmore. Literatur:
   • Lawrence L. Larmore, Daniel S. Hirschberg: A Fast Algorithm for Optimal Length-Limited Huffman Codes. J. ACM 37(3): 464-473 (1990), doi:10.1145/79147.79150
   • Witten, Moffat, Bell: Managing Gigabytes, Kapitel 9.1
3. Quasi-greedy
4. Kodes variabler Länge: Tunstall-Kodes, Schalkwijk-Kodes, Tjalkens-Willems-Kodes (Handbook, Kapitel 2.6–2.8; siehe auch: Sayood: Introduction to Data Compression, Kapitel 3.7.)
5. Automatic language recognition and authorship attribution
   D. Benedetto, E. Cagliotti, and V. Loreto. Language trees and zipping. Physical Review Letters, 88, January 2002. DOI: 10.1103/PhysRevLett.88.048702, sowie Kommentar und Entgegnung dazu.
6. Converting suffix-array into suffix tree:
   Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. A. Amir and G.M. Landau (Eds.): CPM 2001, LNCS 2089, pp. 181-192, 2001.
7. State-of-the-art in detecting academic plagiarism, Norman Meuschke, Bela Gipp. International Journal for Educational Integrity, Vol. 9, No. 1 (2013)
8. A. Puglisi, D. Benedetto, E. Caglioti, V. Loreto, A. Vulpiani. Data compression and learning in time sequences analysis. http://arxiv.org/abs/cond-mat/0207321. Journal reference: Physica D 180, 92 (2003), DOI: 10.1016/S0167-2789(03)00047-2
9. Remote File Synchronization:
   • Handbook, Kapitel 11.14
   • Sayood (ed.) Lossless Compression Handbook, Kapitel 13
10. Die beiden ursprünglichen Ziv-Lempel-Arbeiten:
    Jacob Ziv, Abraham Lempel: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory (TIT) 23(3):337-343 (1977). DOI:10.1109/TIT.1977.1055714
11. Jacob Ziv, Abraham Lempel: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory (TIT) 24(5):530-536 (1978). DOI:10.1109/TIT.1978.1055934
12. TMW - a New Method for Lossless Image Compression, Bernd Meyer, Peter Tischer, International Picture Coding Symposium PCS97 conference proceedings, September 1997
    Extending TMW for near lossless compression of greyscale images, Bernd Meyer, Peter Tischer, Data Compression Conference, 1998. DOI:10.1109/DCC.1998.672194
13. Kompression von geometrischen Daten (triangulierten Oberflächen). (Es gibt dazu auch einen Überblicksartikel von Gotsman, Gumhold und Kobbelt.)
    
    • Kodierung und Kompression von Triangulierungen. Das Edgebreaker-Verfahren (Handbook, Kapitel 11.11)
14. Kompression von geometrischen Daten:
    • Kodierung und Kompression von Polygongittern. Das Face-Fixer-Verfahren (Video und Demo-Programm)
15. Kompression von Delaunay-Triangulierungen.
    Bettina Speckmann, Jack Snoeyink: Easy triangle strips for TIN terrain models. International Journal of Geographical Information Science 15(4): 379-386 (2001) DOI: 10.1080/136588101300304070. (Java-applet zur Veranschaulichung)
16. FHM Kurvenkompression. Handbook, Kapitel 11.9, und dortige Referenzen.
17. Iterierte Funktionssysteme (IFS) zur Bildkompression (Handbook, Kapitel 7.39)
18. Bildkompression mit endlichen Automaten (Handbook, Kapitel 7.38)
19. Textkompression mit kontexfreien Grammatiken, Sequitur (Handbook, Kapitel 11.11 und dortige Referenzen)
20. Redundancy-Feedback (RF) Kodierung, Handbook, Kapitel 2.9–2.11.
21. Präfixkodes in beide Richtungen, Handbook, Kapitel 4.5
22. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, Slashing the Time for BWT Inversion. 2012 Data Compression Conference, DOI 10.1109/DCC.2012.18

Programm