Editing Suffix array (section)

== Space efficiency ==

Suffix arrays were introduced by {{harvtxt|Manber|Myers|1990}} in order to improve over the space requirements of [[suffix tree]]s: Suffix arrays store <math>n</math> integers. Assuming an integer requires <math>4</math> bytes, a suffix array requires <math>4n</math> bytes in total. This is significantly less than the <math>20n</math> bytes which are required by a careful suffix tree implementation.{{sfn|Kurtz|1999}}

However, in certain applications, the space requirements of suffix arrays may still be prohibitive. Analyzed in bits, a suffix array requires <math>\mathcal{O}(n \log n)</math> space, whereas the original text over an alphabet of size <math>\sigma</math> only requires <math>\mathcal{O}(n \log \sigma)</math> bits.
For a human genome with <math>\sigma = 4</math> and <math>n = 3.4 \times 10^9</math> the suffix array would therefore occupy about 16 times more memory than the genome itself.

Such discrepancies motivated a trend towards [[compressed suffix array]]s and [[Burrows–Wheeler transform|BWT]]-based compressed full-text indices such as the [[FM-index]]. These data structures require only space within the size of the text or even less.