Home | english  | Impressum | Sitemap | KIT

External Batched Range Minimum Queries and LCP Construction

External Batched Range Minimum Queries and LCP Construction
Typ:Bachelorarbeit
Datum:2013-04-11
Betreuer:

Timo Bingmann

Bearbeiter:

Daniel Feist

Links:PDF

Zusammenfassung

Diese Arbeit befasst sich mit I/O-optimaler Suffix Array- (SA) und Longest Common Prefix (LCP ) Array-Konstruktion im externen Speicher. Dazu wird der I/O-optimale DC3 -Algorithmus um die LCP -Konstruktion erweitert und anschließend entsprechend angepasst, um in das externe Speichermodell übertragen werden zu können. In diesem Zusammenhang stellen wir eine Methode vor, um die dafür benötigten Range Minimum Queries (RMQs) effizient im externen Speicher zu berechnen. Kern dieser Arbeit stellt die Beschreibung und Implementierung des hieraus resultierenden externen DC3 -LCP-Algorithmus mithilfe der Stxxl - der C++ Standard Template Library for Extra Large Data Sets - dar. Experimentelle Ergebnisse auf Basis realistischer Eingabeinstanzen runden diese Arbeit ab.