What is it about?

The suffix array storing the ranks of all suffixes of a given string is arguably the most central data structure in string indexing as it provides fast answers to queries for locating or counting the occurrences of a pattern on the indexed string. Sometimes, it is sufficient to store the ranks of suffixes starting at specific positions of the text such as word beginnings or coding regions of the DNA. By doing so, we obtain the sparse suffix array. Here, we provide a solution for constructing the sparse suffix array in deterministic time while using at most as much space as suffix ranks are requested.

Featured Image

Why is it important?

The sparse suffix array can be much smaller than the suffix array itself. This also gives rise to the question whether we can build the sparse suffix array in time sub-linear to the text length if the number of requested suffix ranks is considerably small. We can affirm this question with a construction algorithm, which is also the currently fastest option among all other deterministic algorithms working within the same space limit.


The article highlights a peculiar connection between sparse suffix sorting and grammar compression. It could be interesting to study different grammar compression schemes to improve the here studied solution.

Dominik Köppl

Read the Original

This page is a summary of: Deterministic Sparse Suffix Sorting in the Restore Model, ACM Transactions on Algorithms, October 2020, ACM (Association for Computing Machinery),
DOI: 10.1145/3398681.
You can read the full text:




The following have contributed to this page