« Projekte
Datenkompression mit T-Codes
Projektbearbeiter:
Cristian Calude, Ulrich Speidel, Mark Titchener
Finanzierung:
Fördergeber - Sonstige;
T-Codes sind Präfixcodes variabler Länge, die in den 80er Jahren von MarkTitchener erfunden wurden. Ihre erste "Anwendung" war zunächst dieHuffman-artige Datenkompression für Kommunikationskanäle mit hohenBitfehlerraten, da T-Codes ein ausgeprägt starkes und algorithmischerklärbares Selbstsynchronisationsverhalten zeigen. Wegen der aufwendigenCodierung kamen sie jedoch nur in einigen Einzelanwendungen zum Einsatz. In den90er Jahren verschob sich das Augenmerk dann auf die rekursiveKonstruktionsweise der T-Codes. Es fiel auf, dass die längsten Codewörtereines T-Codes als eindeutiges Identifikationmerkmal für den gesamten Codedienen können. Die führte schliesslich zur Einsicht, dass sich alle endlichenStrings über abzählbaren Alphabeten eineindeutig in T-Codes transformierenlassen - und umgekehrt. Diese String-Code-Dualität eröffnet eine neuePerspektive auf das Konzept des Informationsgehalts von Strings, mitpraktischen Anwendungen z.B. im Bereich Ähnlichkeitsmessung undEreignisdetektion.

Schlagworte

Algorithmen, Datenkompression, Zufallszahlengenerator
Kontakt
Prof. Dr. Ludwig Staiger

Prof. Dr. Ludwig Staiger

Martin-Luther-Universität Halle-Wittenberg

Naturwissenschaftliche Fakultät III

Institut für Informatik

Von-Seckendorff-Platz 1

06120

Halle (Saale)

Tel.+49 345 5524714

Fax:+49 345 5527009

ludwig.staiger(at)informatik.uni-halle.de