Home | deutsch  | Legals | Sitemap | KIT

Masterarbeit: Advanced Top Tree Compression

Masterarbeit: Advanced Top Tree Compression
Type:Masterarbeit
Supervisor:

Lorenz Hübschle-Schneider und Dr. Simon Gog

Beschreibung

  Top Tree Compression ist ein Kompressionsverfahren für geordnete Bäume mit Knotenlabels, das darauf basiert den Eingabebaum in einen sogenannten Top Tree zu überführen.  Der minimale dazu äquivalente DAG, genannt Top DAG, wird gespeichert.  Ein Top Tree ist eine hierarchische Dekomposition des Eingabebaums in zusammenhängende Teilgraphen des Eingabebaums, die sich durch zwei "Schnitte" abtrennen lassen. Durch diese Konstruktion werden strukturelle Redundanzen der Eingabe als identische Teilbäume im Top Tree repräsentiert.  Diese lassen sich dann gut komprimieren.
 
  Top Trees wurden bereits im Bereich der XML-Kompression untersucht, es gibt aber noch einige offene Fragen, beispielsweise zur Codierung des Top DAGs.  In dieser Arbeit soll daher eine komprimierte Repräsentation entwickelt und implementiert werden, die Navigation ohne Dekomprimierung zulässt.  Zudem bieten sich Top Trees auch für eine Reihe weiterer Einsatzgebiete an, die in dieser Arbeit ebenfalls untersucht werden können.
 
  Der Suffix Tree etwa ist eine mächtige Indexstruktur welche es ermöglicht viele Probleme -- etwa Pattern Matching -- in optimaler Zeit zu lösen. Deshalb findet die Struktur in vielen Bereichen Anwendung, u.a. in der Bioinformatik, dem Information Retrieval und Natural Language Processing.  Da die klassiche, zeigerbasierte Repräsentation aber sehr viel Platz erfordert, sind komprimierte Suffix Trees erforderlich um große Datenmengen zu verarbeiten.  Dazu gibt es verschiedene Ansätze; im Rahmen dieser Arbeit wäre es daher denkbar, den Suffix Tree mithilfe von Top Trees zu komprimieren.
 

Thema der Arbeit

Ziel der Arbeit ist es, Top Tree Compression so zu erweitern, dass sie zur Kompression von Suffix Trees verwendbar ist.  Hierzu müssen in einem ersten Schritt eine geeignete Codierung des Top DAGs entwickelt werden, und die auf dem Top DAG verfügbaren Navigationsoperationen um Subtree Size erweitert werden. Anschließend bestehen mehrere Möglichkeiten, beispielsweise Kompression von Suffix Trees oder eine Verbesserung der Analyse von Top Tree Compression.  Code zur Erstellung von Suffix Trees und Top DAGs ist dabei bereits vorhanden.
 

Voraussetzungen

  • Interesse an und solide Kenntisse von Algorithmen und Datenstrukturen
  • Gute Programmierkenntnisse in C++, optimalerweise Erfahrung mit SDSL
  • Wünschenswert: Besuch der Vorlesung "Textindizierung"

Gebotenes

  • Mitarbeit an einem echten Forschungsthema
  • Einblick in Succinct Data Structures