This work deals with I/O-optimal suffix array (SA) and longest common prefix (LCP) array construction in external memory. For this purpose, the I/O-optimale DC3 algorithm is enhanced by LCP construction and adapted accordingly to the external memory model. In this context we present a method to construct the required range minimum queries (RMQs) efficiently in external memory. The core of this work is a description and implementation of the resulting external DC3 -LCP algorithm using the Stxxl - the C++ Standard Template Library for Extra Large Data Sets. Experimental results based on realistic, real-world instances rounds off this work.

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.