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 Lo stesso argomento in dettaglio: Sottosuccessione.

Una sottosequenza di una stringa è una stringa tale che , dove . 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 dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero .

Sottostringa[modifica | modifica wikitesto]

Una sottostringa (o fattore) di una stringa è una stringa , dove e . Una sottostringa di una stringa è un prefisso di un suffisso della stringa o, in modo equivalente, un suffisso di un prefisso della stringa. Se è una sottostringa di , essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern , è possibile trovarne le occorrenze in una strina 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 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 punti. Per cui esistono sottostringhe non vuote.

Prefisso[modifica | modifica wikitesto]

Un prefisso di una stringa è una stringa , dove . Un prefisso proprio di una stringa ha lunghezza inferiore rispetto alla stessa () [1]; alcune definizioni[2] in aggiunta richiedono che un prefisso proprio sia non vuoto (). 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ì denota che è un prefisso di , 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 è una stringa , dove . Un suffisso proprio di una stringa è di lunghezza inferiore alla stessa (); di nuovo, un'interpretazione più restrittiva impone che il suffisso proprio sia non vuoto [2] (). 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 stringhe , una superstringa dell'insieme è una singola stringa che contiene tutti gli elementi di come sottostringhe. Per esempio, una concatenazione degli elementi di in un ordine qualsiasi produce una superstringa banale di . Per un esempio più interessante, sia . Si ha che è una superstringa di , ma è 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.