Lightweight external memory suffix array construction algorithm

[back to the main page]

We present a C++ implementation of the lightweight algorithm for suffix array construction. For more information, see README provided with the package.

News

• 2016-01-07: SAscan is currently actively developed under the name pSAscan -- an implementation of SAscan that takes the full advantage of multi-core CPUs.
• 2014-08-24: New version (0.1.1) available [changelog].

Downloads

• SAscan 0.1.1 (current version)
• SAscan 0.1.0

Implemented by

• Juha Kärkkäinen
• Dominik Kempa

See also

• Parallel external memory suffix array construction
• Better external memory (P)LCP array construction
• LCP array construction in external memory
• String sorting algorithms

References

1. Juha Kärkkäinen, Dominik Kempa. Engineering a Lightweight External Memory Suffix Array Construction Algorithm.
   In Proc. 2nd International Conference on Algorithms for Big Data (ICABD 2014), CEUR, 2014, pp. 53-60.
   [CEUR]
2. Juha Kärkkäinen, Dominik Kempa. Engineering a Lightweight External Memory Suffix Array Construction Algorithm.
   Mathematics in Computer Science, Volume 11(2), 2017, pp. 137-149.
   [Springer]