Stringa (linguaggi formali)
In varie discipline della matematica e dell'informatica, per stringa si intende una sequenza composta da un certo numero di oggetti che ci si aspetta venga sottoposta ad elaborazioni come analisi, composizioni e trasformazioni in altre stringhe o strutture discrete come grafi o configurazioni numeriche, senza modificare gli oggetti componenti.
semplici (come bits, caratteri o simboli) o da trattare come se fossero semplici (come parole, espressioni, frammenti di testo o contrassegni di oggetti compositi ma che non si vogliono analizzare o decomporre).
Dal punto di vista della costituzione si distinguono innanzi tutto le stringhe di oggetti semplici: stringhe di bit (stringhe binarie), stringhe composte da caratteri (stringhe letterali), stringhe di simboli (stringhe simboliche). Tra le stringhe di oggetti compositi si collocano le stringhe composte da unità lessicali (dette anche token), i frammenti di testo (come i titoli dei paragrafi o le citazioni bibliografiche) e le stringhe che rappresentano molecole dotate di struttura complessiva filamentosa, come quelle che rappresentano una proteina o una struttura di DNA.
Tra gli strumenti che possono sottoporre le stringhe ad elaborazioni si distinguono quelli formali, come gli automi, le macchine di Turing, le grammatiche formali o altri sistemi di riscrittura e quelli più concreti costituiti da programmi o routines di sistemi software. In linea di principio gli strumenti del secondo genere si possono considerare implementazioni dei primi.
Trattamento formale
Si inizia con un insieme finito non-vuoto Σ chiamato alfabeto. Gli elementi di questo alfabeto sono chiamati caratteri. Una stringa (o parola) in Σ è una qualsiasi sequenza finita di caratteri di Σ.
Una stringa di importanza particolare è la sequenza composta da nessun carattere, chiamata stringa vuota. La stringa vuota è spesso indicata con ε o λ. Le sequenze infinite non sono considerate stringhe.
Per esempio, se Σ = {0, 1}, le stringhe in Σ sono nella forma
- ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …
L'insieme di tutte le stringhe in Σ è indicato come Σ*. Si può definire un'operazione binaria in Σ* chiamata concatenazione di stringhe. Se s e t sono due stringhe, la loro concatenazione, indicata come st, è definita come la sequenza di caratteri in s seguita dalla sequenza di caratteri in t.
Per esempio, se s = topo e t = ragno allora st = toporagno e ts = ragnotopo.
La concatenazione di stringhe è un'operazione associativa, ma non-commutativa. Rispetto alla concatenazione, la stringa vuota è l'elemento neutro. In termini algebrici, l'insieme Σ* costituisce un monoide rispetto alla concatenazione di stringhe. In effetti, Σ* è il monoide libero generato da Σ.
La lunghezza di una stringa è data dal numero di caratteri che la compongono, e può essere un qualsiasi numero naturale. La lunghezza della stringa vuota è 0. Da un punto di vista algebrico, la funzione lunghezza definisce un omomorfismo da Σ* a N (l'insieme dei numeri interi non negativi con l'addizione).
Una stringa s si dice sottostringa o fattore di t se esistono due stringhe u e v tali che t = usv. Si noti che u e/o v possono essere vuote. La relazione "è una sottostringa di" definisce una relazione d'ordine su Σ*, il cui minimo risulta la stringa vuota.
Se l'alfabeto Σ è ben ordinato, il cosiddetto ordine lessicografico costituisce un altro ordinamento totale su Σ*, di frequente utilizzo per le applicazioni informatiche.
Un insieme di stringhe su Σ (cioè un sottoinsieme di Σ*) è anche detto linguaggio formale su Σ. Si noti che nonostante l'alfabeto sia finito ed ogni stringa abbia lunghezza finita, nulla vieta che un linguaggio formale contenga un numero infinito di stringhe. In effetti, Σ* stesso è sempre un linguaggio infinito. Esempi notevoli di linguaggi formali sono forniti dalle espressioni regolari e dalle grammatiche formali.
Tipi di dati stringa
Un tipo di dati stringa è un tipo di dati modellato sull'idea di una stringa formale. Le stringhe sono un tipo di dati talmente importante e utile che fanno parte di quasi tutti i linguaggi di programmazione. In alcuni linguaggi sono disponibili sono tipi primitivi e in altri come tipi compositi.
Mentre le stringhe formali possono avere una lunghezza arbitraria (ma finita), le stringhe dei linguaggi di programmazione hanno lunghezza limitata. In generale, ci sono due categorie di tipi di dati stringa: le stringhe a lunghezza fissa, che hanno una lunghezza massima prefissata, e le stringhe a lunghezza variabile, la cui lunghezza può essere modificata con apposite istruzioni. La maggior parte delle stringhe nei moderni linguaggi di programmazione sono a lunghezza variabile. Nonostante il nome, anche le stringhe a lunghezza variabile hanno un limite di lunghezza; tuttavia, in generale, il limite dipende solamente dalla quantità di memoria disponibile nel computer.
I tipi di dato stringa differiscono anche in base all'alfabeto su cui sono definite. Alcune stringhe sono progettate per funzionare su un singolo alfabeto prefissato (come l'alfabeto latino o come i caratteri rappresentabili dal codice ASCII) e altre su un alfabeto arbitrario. Per esempio, nella libreria standard del C++ le stringhe sono parametrizzate dall'alfabeto dei caratteri.
Rappresentazioni
La rappresentazione delle stringhe dipende principalmente dalla scelta dei set di caratteri da usare (come alfabeto) ed il metodo di codifica dei caratteri (vedere character encoding). Le vecchie implementazioni delle stringhe erano studiate per lavorare con set di caratteri e codifiche definite dall'ASCII, od estensioni più recenti come la serie[ISO 8859]]. Le implementazioni moderne usano spesso l'ampio set di caratteri definito come Unicode insieme con una varietà di complesse codifiche come l'UTF-8 e l'UTF-16.
La gran parte delle implementazioni delle stringhe somigliano ad array i cui elementi contengono i codici corrispondenti ai caratteri nel corrispondente set di caratteri. La principale differenza è che in alcune codifiche l'equivalente di un singolo carattere logico può necessitare di più elementi dell'array. Un esempio in questo senso è la codifica UTF-8 in cui un singolo carattere logico può richiedere fino a quattro byte. In questi casi la lunghezza logica della stringa differisce da quella dell'array.
La lunghezza di una stringa può essere memorizzata implicitamente utilizzando uno speciale carattere di terminazione. Questo carattere è spesso il carattere nullo (null character o NULL) avente codice zero, convenzione questa usata e perpetuata dal popolare linguaggio di programmazione C. La lunghezza di una stringa può anche venir memorizzata esplicitamente, ad esempio attaccando alla stringa un prefisso con un valore intero, convenzione questa usata ad esempio in Pascal. Si noti che nel caso delle stringhe terminate il carattere di terminazione non sarà mai ammissibile come contenuto di una stringa.
Qui si ha un esempio di una stringa zero-terminata (o null-terminated) memorizzata in un buffer di 10 byte, assieme alla sua rappresentazione ASCII
| F | R | A | N | K | NUL | k | e | f | w |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 65 | 66 | 77 |
La lunghezza della stringa è in questo esempio di 5 caratteri, essa occupa tuttaiva 6 byte. I caratteri dopo la terminazione (6B 65 66 77, rispettivamente k e f w in ASCII) non sono parte della stringa, potrebbero essere parte di un'altra stringa come semplicemente rifiuti.
La stringa equivalente in Pascal:
| length | F | R | A | N | K | k | f | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
A fianco di queste comuni rappresentazioni altre sono possibili.
L'utilizzo delle rope (anche dette heavyweight string) può rendere certe operazioni come inserimenti, cancellazioni e concatenazioni più efficienti. [1]
Algoritmi per le stringhe
Sono stati studiati molti algoritmi per la manipolazione delle stringhe i quali si distinguono per finalità e per diverse scelte di compromesso di fronte ad esigenze contrastanti come l'ampiezza della portata e la efficienza.
Questi algoritmi vengono collocati a categorie come le seguenti:
- algoritmi di ricerca di stringhe aventi il compito di trovare una data sottostringa o una data configurazione di caratteri,
- algoritmi di ordinamento (sorting),
- algoritmi per espressioni regolari,
- scansori e parser di stringhhe.
Gli algoritmi più avanzati per l'elaborazione di stringhe spesso impiegano elaborati meccanismi formali e complesse strutture di dati: tra questi ricordiamo gli alberi di suffissi e le macchine a stati finiti.
Linguaggi e programmi di utilità orientati all'elaborazione di stringhe
Le stringhe costituiscono un tipo di dati tanto ampiamente utilizzato da indurre lo sviluppo di numerosi linguaggi finalizzati alla facilitazione delle elaborazioni delle stringhe più richieste dalle applicazioni. Tra questi vi sono:
Molti programmi di utilità dell'ambito UNIX effettuano manipolazioni di stringhe relativamente semplici e possono essere utilizzati per programmare algoritmi di elaborazione di stringhe piuttosto efficaci. Questi strumenti possono trattare come stringhe anche i files e gli stream finiti.
I recenti linguaggi di scripting, come Perl, Python, Ruby e Tcl si servono di espressioni regolari per facilitare le manovre sui testi.
[ [ Categoria:Terminologia del computer ] ] ?