Lempel-Ziv Compressed String Dictionaries

  • Forschungsthema:String-Algorithmen
  • Typ:Diplomarbeit
  • Datum:2013
  • Betreuung:

    Johannes Fischer

  • Bearbeitung:

    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