Sottostringa

Da Wikipedia, l'enciclopedia libera.

Una sottostringa, sottosequenza, prefisso o suffisso di una stringa è un sottoinsieme di simboli in una stringa, in cui l'ordine degli elementi è preservato. In questo contesto, i termini stringa e sequenza assumono lo stesso significato.

Sottosuccessioni[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Sottosuccessione.

Una sottosequenza di una stringa T = t_1 t_2 \dots t_n è una stringa \hat T = t_{i_1} \dots t_{i_m} tale che i_1 < \dots < i_m, dove m \leq n. La sottosuccessione è una generalizzazione del concetto di sottostringa, suffisso e prefisso. Trovare la stringa più lunga uguale a una sottosequenza di due o più stringhe è noto come il problema della massima sottosequenza comune.

Esempio: la stringa anna è una sottosequenza della stringa banana:

banana
 || ||
 an na

Contando la sottosequenza vuota, il numero di sottosequenze di una stringa lunga n dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero 2^n.

Sottostringa[modifica | modifica wikitesto]

Una sottostringa (o fattore) di una stringa T = t_1 \dots t_n è una stringa \hat T = t_{1+i} \dots t_{m+i}, dove 0 \leq i e m + i \leq n. Una sottostringa di una stringa è un prefisso di un suffisso della stringa o, in modo equivalente, un suffisso di un prefisso della stringa. Se \hat T è una sottostringa di T, essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern P, è possibile trovarne le occorrenze in una strina T mediante un algoritmo di pattern matching su stringhe. Trovare la stringa più lunga uguale a una sottostringa di due o più stringhe è noto come il problema della massima sottostringa comune.

Esempio: La stringa ana è una sottostringa (e sottosequenza) di banana in due posizioni differenti:

banana
 |||||
 ana||
   |||
   ana

Nella letteratura matematica, le sottostringhe sono anche chiamate subwords (in America) o fattori (in Europa).

Non contando la sottostringa vuota, il numero di sottostringhe di una stringa lunga n dove i simboli compaiono solo una volta è uguale al numero di modi in cui si possono scegliere due "punti" distinti, ognuno posto tra due simboli adiacenti, per marcare rispettivamente l'inizio e la fine della sottostringa. Includendo il punto che precede il primo carattere della stringa e quello che segue l'ultimo, ci sono un totale di n+1 punti. Per cui esistono \tbinom{n+1}{2} = \tfrac{n(n+1)}{2} sottostringhe non vuote.

Prefisso[modifica | modifica wikitesto]

Un prefisso di una stringa T = t_1 \dots t_n è una stringa \widehat T = t_1 \dots t_{m}, dove m \leq n. Un prefisso proprio di una stringa ha lunghezza inferiore rispetto alla stessa (0 \leq m < n) [1]; alcune definizioni[2] in aggiunta richiedono che un prefisso proprio sia non vuoto (0 < m < n). Un prefisso può essere visto come un caso speciale di una sottostringa.

Esempio: La stringa ban è un prefisso (e sottostringa e sottosequenza) della stringa banana:

banana
|||
ban

Il simbolo di sottoinsieme quadrato è a volte utilizzato per indicare un prefisso, così \widehat T \sqsubseteq T denota che \widehat T è un prefisso di T, definendo una relazione binaria su stringhe, chiamata la relazione prefisso.

Nella teoria dei linguaggi formali il termine prefisso di una stringa viene inteso comunemente anche come l'insieme di tutti i prefissi di una stringa rispetto a quel linguaggio.

Suffisso[modifica | modifica wikitesto]

Un suffisso di una stringa T = t_1 \dots t_n è una stringa \hat T = t_{n-m+1} \dots t_{n}, dove m \leq n. Un suffisso proprio di una stringa è di lunghezza inferiore alla stessa (0 < m \leq n); di nuovo, un'interpretazione più restrittiva impone che il suffisso proprio sia non vuoto [2] (0 < m < n). Un suffisso può essere visto come un caso speciale di una sottostringa.

Esempio: La stringa nana è un suffisso (e una sottostringa e sottosequenza) della stringa banana:

banana
  ||||
  nana

Un albero dei suffissi di una stringa è una struttura dati trie-like che rappresenta tutti i suoi suffissi. Gli alberi dei suffissi hanno un gran numero di applicazioni negli algoritmi su stringhe. L'array dei suffissi è una versione semplificata di questa struttura dati che elenca le posizioni di partenza dei suffissi in ordine alfabetico; condivide molte delle stesse applicazioni.

Bordo[modifica | modifica wikitesto]

Una sottostringa si dice bordo quando è contemporaneamente suffisso e prefisso della stessa stringa, ad esempio "bab" è un bordo di "babab".

Superstringa[modifica | modifica wikitesto]

Dato un insieme di k stringhe P = \{s_1,s_2,s_3,\dots s_k\}, una superstringa dell'insieme P è una singola stringa che contiene tutti gli elementi di P come sottostringhe. Per esempio, una concatenazione degli elementi di P in un ordine qualsiasi produce una superstringa banale di P. Per un esempio più interessante, sia P = \{\text{abcc}, \text{efab}, \text{bccla}\}. Si ha che \text{bcclabccefab} è una superstringa di P, ma \text{efabccla} è una superstringa più corta.

Riferimenti bibliografici[modifica | modifica wikitesto]

  1. ^ (EN) Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press.
  2. ^ a b (EN) Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.