Definizione: Una struttura di indicizzazione è una struttura dati che riorganizza un testo in maniera da rendere facile ed efficiente un compito che compiuto sul testo originale risulta essere difficile e inefficiente.
Si effettua quindi il preprocessing del testo.
Prima di tutto bisogna fissare un ordinamento dei simboli dell’alfabeto $\Sigma$ e si fissa l’ordinamento lessicografico. Esempio si ha $a < c < g < t$.
Bisogna estendere $\Sigma$ con un simbolo sentinella lessicograficamente minore dei simboli dell’alfabeto e usiamo il $\$$, avendo $\$<a<c<g<t$. Tale sentinella è posto a fine testo e non compare in altri punti del testo.
Definizione: Si definisce il suffisso di indice $j$ come il suffisso che inizia in $j$ di $T$ (bisogna specificare che inizia in $j$):
$$ T[j, |T|] $$
il suffisso di indice iniziale pari a quello di $\$$ è nullo.
Posso stabilire quindi l’ordinamento dei suffissi di un testo $T$. Per ordinare due suffissi $s_1$ e $s_2$ si ha la regola:
In altri termini è il modo in cui cerco le parole in un vocabolario. Terminando con il $\$$ non posso avere suffissi uguali e non avere che un suffisso sia suffisso dell’altro (visto che $\$$ non può trovarsi nel testo).
Definizione: Definiamo la rotazione di indice $j$ come la concatenazione del suffisso $T[j,|T|]$ con il suffisso $T[1,j-1]$. La rotazione con $j$ pari all’indice del carattere $\$$ coincide con lo spostare il dollaro dalla fine all’inizio.
Definizione: Il Suffix Array (SA) di un testo $T$ $\$$-terminato di lunghezza $n$ è un array $S$ di $n$ interi tale che $S[i] = j$ sse il suffisso di indice $j$ è l’$i$-esimo suffisso nell’ordinamento lessicografico dei suffissi di $T$, avendo $T[S[i], n]$ come $i$-esimo suffisso di $T$.
Se ho $i < i'$ allora:
$$ T[S[i], n] < T[S[i'], n] $$
Si vede che in spazio si ha:
$$ O(n \log n) $$
avendo $n$ valori interi di lunghezza a scalare da $1$ a $n$.