Computing sparse suffix arrays in deterministic time

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

Photo by Sophie Elvis on Unsplash

Photo by Sophie Elvis on Unsplash

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.

Perspectives