String Processing and Compression
Vorlesung im Wintersemester 2015/2016
Inhalt
Daten in lange Zeichenketten (Strings) sind allgegenwärtig in vielen Bereichen der Informatik. Zum Beispiel Web Programme nutzen Verschlüsselungen als Zeichenketten um Daten auszutauschen, und der größte Teil der Daten in der Bioinformatik, wie DNA Sequenzieren, sind Zeichenketten. Die Vorlesung stellt Algorithmen und Datenstrukturen vor die massgeschneidert sind, um zeichenkettenformatierte Daten zu verarbeiten. Das beinhaltet das Problem Muster in Zeichenketten zu erkennen und Sequenzen anzupassen, als auch Zeichenketten zu sortieren und zu durchsuchen.
Die Komprimierung von Daten ist wichtig um Resourcen, wie Speicherplatz oder Kommunikationskanäle, zu schonen. Die Vorlesung beginnt mit der Einführung des informations-theoretischen Hintergrunds der Komprimierungstechniken. Basierend auf dieser Einführung stellt die Vorlesung die verlustfreie Komprimierungstechnik von Zeichenketten vor.
Themen
Zeichenketten-verarbeitende Algorithmen
- Radix Bäume
- Radix Sorts
- Mustervergleich
- approximierter Mustervergleich
- probabilistischer Mustervergleich
- Suffix Bäume
- Suffix Reihen
- Zeichenkettengruppierung
- Schwierige String Probleme
Daten-Komprimierungs Techniken
- Kodierungstheorie
- Informationstheorie
- Wörterbuchbasierte Kompression
- Kontextbasierte Kompression
- Gramatikbasierte Kompression
Organisation
Vortragssprache in Englisch.
Dozent
Michael Elberfeld