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.