Parallel Suffix Array and Tree Construction
This library implements a distributed-memory parallel algorithm for the
construction of suffix arrays, LCP arrays, and suffix trees. The algorithm is implemented in
The algorithm implemented by this codebase is described in the following peer-reviewed publication. Please cite this paper, when using our code for academic purposes:
Flick, Patrick, and Srinivas Aluru. "Parallel distributed memory construction of suffix and longest common prefix arrays." Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ACM, 2015.
include/contains the implementation of our algorithms in form of C++ template header files (a header-only library).
src/contains the sources for binaries, which make use of the implementations in
testcontains unit tests for the components of the library.
ext/contains external, third-party dependencies/libraries. See the README for details on the third-party libraries used.
cmakeversion >= 2.6
- C++11 compatible compiler (tested with gcc and clang)
- external (third-party) dependencies are included in the
To compile the executables and tests via cmake run the following:
mkdir build cd build cmake -D CMAKE_BUILD_TYPE=Release ../ make
After compiling, there will a multiple binaries available in the
--help on them will give more detailed usage information.
Here's a short overview over the different binaries and their function:
psacis our main executable. This will construct the suffix and LCP array of a given input file. Run with
mpirunfor parallel execution.
benchmark_sacbenchmarks multiple of our methods. Run with
dssis a wrapper around
libdivsufsortthat follows the same command line usage as our other binaries. This is a sequential program. No mpirun needed.
psac-vs-dssruns both our suffix array construction and
libdivsufsort, verifies the results against each other and outputs run-times of both.
test_*various test executables, testing a variety of our internal methods.
Our code is licensed under the
Apache License 2.0 (see
The licensing does not apply to the
ext folder, which contains external
dependencies which are under their own licensing terms.