Florian Kurpicz
Presentation at PSC 2017

Dismantling DivSufSort

This week, I presented our results on longest common prefix (LCP) array construction. Our foundation is DivSufSort, which is the fastest suffix array construction algorithm in practice.

First, we give a detailed explanation of the internal workings of DivSufSort, something that has not been done yet. Then, we extend DivSufSort such that it can also compute the LCP array of the text.

The slides are available as handout and heavily animated, and you can find the paper here (conference website) and here (arXiv).

Slides in Handout Mode

Slide image psc_2017_slides_handout-01.jpg
Slide image psc_2017_slides_handout-02.jpg
Slide image psc_2017_slides_handout-03.jpg
Slide image psc_2017_slides_handout-04.jpg
Slide image psc_2017_slides_handout-05.jpg
Slide image psc_2017_slides_handout-06.jpg
Slide image psc_2017_slides_handout-07.jpg
Slide image psc_2017_slides_handout-08.jpg
Slide image psc_2017_slides_handout-09.jpg
Slide image psc_2017_slides_handout-10.jpg
Slide image psc_2017_slides_handout-11.jpg
Slide image psc_2017_slides_handout-12.jpg
Slide image psc_2017_slides_handout-13.jpg
Slide image psc_2017_slides_handout-14.jpg
Slide image psc_2017_slides_handout-15.jpg
Slide image psc_2017_slides_handout-16.jpg
Slide image psc_2017_slides_handout-17.jpg
Slide image psc_2017_slides_handout-18.jpg
Slide image psc_2017_slides_handout-19.jpg
Slide image psc_2017_slides_handout-20.jpg
Slide image psc_2017_slides_handout-21.jpg

Abstract

We give the first concise description of the fastest known suffix sorting algorithm in main memory, the DivSufSort by Yuta Mori. We then present an extension that also computes the LCP-array, which is competive with the fastest known LCP-array construction algorithm.