The suffix array is one of the foundational data structures in bioinformatics,
serving as an index that allows fast substring searches in a large text.
However, in its raw form, the suffix array occupies the space proportional to (and
several times larger than) the original text.
In their paper, Tomasz and Dominik construct a new index, δ-SA, which on the
one hand can be used in the same way (answer the same queries) as the suffix
array and the inverse suffix array, and on the other hand, occupies the space
roughly proportional to the gzip’ed text (or, more precisely, to the measure δ
that they define — hence the name).
Moreover, they mathematically prove that this index is optimal, in the sense
that any index that supports these queries — or even much weaker queries, such
as simply accessing the i-th character of the text — cannot be significantly
smaller (as a function of δ) than δ-SA.
Podden och tillhörande omslagsbild på den här sidan tillhör
Roman Cheplyaka. Innehållet i podden är skapat av Roman Cheplyaka och inte av,
eller tillsammans med, Poddtoppen.
