Succinct Suffix Array
The Succinct Suffix Array (SSA) is a wavelet tree FM-index that gives to the wavelet tree the shape of the Huffman tree of the text.
The size of the index built on a string is bounded by bits, where is the 0-th order empirical entropy of .
Using the SSA, the counting of the occurrences of an arbitrary pattern as a substring of takes on average time.
ImplementationVeli Mäkinen, R. González
free_text: The text will be freed immediately after using it.
samplerate=<number>: The index marks one text position every <number> entries. The default value is 64.
Mäkinen, V. and Navarro, G. New search algorithms and time/space tradeoffs for succinct suffix arrays. Technical Report C-2004-20 (April), University of Helsinki, Finland.
V. Mäkinen and G. Navarro. Succinct suffix arrays based on run-length encoding. Nordic Journal of Computing 12(1):40-66, 2005.