Home | english  | Impressum | Sitemap | KIT

Lempel-Ziv Compressed String Dictionaries

Lempel-Ziv Compressed String Dictionaries
Forschungsthema:String-Algorithmen
Typ:Diplomarbeit
Datum:2013
Betreuer:

Johannes Fischer

Bearbeiter:

Julian Arz

Ein String-Dictionary ist eine Datenstruktur, in der eine Menge von String-Identifier-Paaren so abgespeichert wird, dass die folgenden 2 Operationen effizient unterstützt werden:

  • Lookup(string S): gib Identifier von String S zurück
  • Access(integer i): gib String mit identifier i zurück

In der Praxis treten sehr großer Datenmengen auf (mehrere Gigabyte Text); insofern sind platzsparende (komprimierte) Datenstrukturen erwünscht. In dieser Arbeit soll untersucht werden, welche Gewinne die Lempel-Ziv-Datenkompression für dieses Problem bringt.

Voraussetzungen

Mindestens 2 der folgenden 4 Voraussetzungen sollten erfüllt sein.

  • gute Kenntnisse in C++
  • Interesse am Algorithm Engineering
  • Spaß an kombinatorischen Problemen und algorithmischen Fragestellungen
  • Besuch der VL Text-Indexierung

Gebotenes

  • Einarbeitung in die wichtigsten Techniken der Text-Indexierung
  • Möglichkeit an der Mitentwicklung einer Datenstrukturen-Bibliothek
  • Forschung an aktuellen Fragestellungen