Implementation of Suffix Array Construction Algorithms

The SDSL (Succinct Data Structure Library) has various implementations of string indices based on suffix arrays. It is currently using third-party algorithms for suffix array construction. This thesis aims at designing an interface for choosing between different construction algorithms and implementing two differnet algorithms.

  • The first algorithm (parallelized radix in-place sorting algorithm) is already implemented in SeqAn2 and has to be adapted to the SDSL
  • The second algorithm can be a state-of-the-art algorithm of the students choice (in consultation with the advisor)

Both algorithms will have to be tested and evaluated (also against the third-party construction algorithm of the SDSL)

For questions, please contact christopher.pockrandt@fu-berlin.de (Takustr. 9, Room 010). This topic can also be handed out for a Bachelor thesis (implementing only one algorithm)

Links

https://github.com/xxsds/sdsl-lite

Comments

 
Topic revision: r1 - 30 May 2018, ChristopherPockrandt
 
  • Printable version of this topic (p) Printable version of this topic (p)