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