Sottostringa

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

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

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

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

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

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

Superstringa

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.

Note

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

Altri progetti

Wikimedia Commons contiene immagini o altri file su sottostringa

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[Kel95-1] (EN) Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press.

[Gus97-2] (EN) Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.

[1]

[2]