External Memory Suffix Array
Construction
November 2004
Diploma thesis, Department
of Computer Science, Saarland
University
supervisor: Prof. Dr. Peter Sanders, University
Karlsruhe
Abstract
In the recent years, a lot of theoretical work has been done on suffix
tree and suffix array construction. In 2000, it was shown that suffix
trees and thereby suffix arrays (converted from the suffix trees) over
an integer alphabet, can be constructed in linear time. In 2003, three
linear suffix array construction algorithms were published which do not
require suffix trees. We have adapted one of these algorithms to
external memory and applied several improvements to it and other
external memory suffix array construction algorithms. One of these
improvement is called pipelining which reduces the I/Os of the
algorithms, significantly.
Documents
Implementation
Reference Manual (incl. Source Browsing)
Evaluation