|
<div class="toccolours" style="width:150px; float: right; text-align: center; margin-left: 20px; margin-right: 5px; margin-bottom: 1em;">
{{Nota disambigua|descrizione=altri significati del termine|titolo=[[stringa]]}}
{{cassetto
|colore=#cccccc
|titolo=<span style="color:black">[[Immagine:CoA civ ITA genova.png|left|14px]]Genovesi</span>
|testo=
<div style="background-color:#FFFFFF; padding: 0.2em;">'''Son zeneize,<br />riso rêo</br />Strenzo i denti<br />e parlo chêo'''
----
<small>[http://it.wikipedia.org/w/index.php?title=Utente:DonPaolo/Genovesi&action=edit Scrivi il tuo nick]</small>
</div>
----
<span style="display:table-cell;{{{style|background:#FFFFFF;border:1px solid #000000}}}">
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.
{{alternate
| [[Image:Genova-OrgoglioZena-3.jpg|145px|Belin!]]
| [[Image:Genova-OrgoglioZena.jpg|145px|Belìn|]]
}}</span>
----
{{cassetto
|colore=#cccccc
|titolo=<span style="color:black">Wiki-Zeneixi</span>
|testo=
<div style="padding: 0.2em;">
*[[Utente:Ab1|Ab1]]
*[[Utente:Bbruno|Bbruno]]
*[[Utente:BMonkey|BMonkey]]
*[[Utente:Carassiti Anna Maria|Carassiti Anna Maria]]
*[[Discussioni utente:Ce|Ce]]
*[[Utente:Cixina|Cixina]]
*[[Utente:Daneelo|Daneelo]]
*[[utente:Davide Ricci|Davide Ricci (Indy)]]
*[[Utente:Dcosta|Dcosta]]
*[[Utente:Dedee|Dedee]]
*[[Utente:Dg|Dg]]
*[[Utente:DonPaolo|DonPaolo]]
*[[Utente:Emiliano Deghenghi|Emiliano Deghenghi]]
*[[utente:Ettorre|Ettorre]]
*[[Utente:f.noceti|f.noceti]]
*[[Utente:FeRR@|FeRR@]]
*[[Utente:Genuae|Genuae]]
*[[Utente:Giampietro Stocco|Giampietro]]
*[[Utente:Goffreder|Goffreder]]
*[[Utente:GrazianoU|GrazianoU]]
*[[Utente:HeavyMezza89|HeavyMezza89]]
*[[Utente:Ilmasco|Ilmasco]]
*[[Utente:Jacklab72|Jacklab72]]
*[[Utente:Klauswiki|Klauswiki]]
*[[Utente:Kronos|KronOS]]
*[[Utente:LordKasko|LordKasko]]
*[[Utente:Lucas|Lucas]]
*[[Utente:Lupo rosso|Lupo rosso]]
*[[Utente:MacLucky|MacLucky]]
*[[Utente:Macmq|Macmq]]
*[[Utente:Maquesta|Maquesta]]
*[[discussioni Utente:Mclsvp|Mclsvp]]
*[[Utente:Murray|Murray]]
*[[Utente:OliverZena|OliverZena]]
*[[Utente:Pabform|Pabform]]
*[[discussioni Utente:Piccardo|Piccardo (utrin)]]
*[[utente:Richzena|Richzena]]
*[[utente:Riverblu|Riverblu]]
*[[Utente:Serre|Serre]]
*[[utente:Sconvolpi74|Sconvolpi74]]
*[[Utente:Sextum|Sextum]]
*[[Utente:Sidvics|Sidvics]]
*[[Utente:Slash89|Slash89]]
*[[Utente:Stefano Lucchi|Stefano Lucchi]]
*[[Utente:Superchilum|Superchilum]]
*[[Utente:Thorin III|Thorin III]]
*[[utente:tommasso|tommasso]]
*[[Utente:Twice25/Personale|Twice25]]
*[[Utente:Ulisse0|Ulisse]]
*[[Utente:Ultra Magnus|Ultra Magnus]]
*[[Utente:Utz|Utz]]
*[[Discussioni utente:Yoggysot|Yoggysot]]
*[[Utente:ZeneizeForesto|ZeneizeForesto]]
*[[Utente:Zolla9|Zolla9]]
*[[Utente:Luckyboy|Luckyboy]]
*[[Utente:Giannilu98|Giannilu98]] ([[Discussioni utente:Giannilu98|msg]])
</div>
}}
----
<small>''[[Ma se ghe penso|Ma se ghe penso<br />aloa mi veddo o mâ...]]''</small>
----
<div style="background-color:#cccccc; padding: 0.2em;"><small>Sostieni e partecipa: </small>
*<big>[[Progetto:Genova|Progetto Genova]]</big>
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).
*<big>[[Portale:Genova|Portale Genova]]</big>
*<big>[[discussioni progetto:Genova|Ostaja zeneize]]</big>
----
*<big>[[Progetto:Liguria|Progetto Liguria]]</big>
*<big>[[Portale:Liguria|Portale Liguria]]</big>
*<big>[[discussioni Progetto:Liguria|Ostaja do Belìn]]</big>
</div>}}
</div><includeonly>[[Categoria:utenti genovesi|{{PAGENAME}}]]</includeonly><noinclude>
----
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]].
*Questo ''template'' è a disposizione di coloro che volessero inserirlo nella propria pagina utente come utenti genovesi o simpatizzanti. Categorizzerà automaticamente la pagina utente in [[:categoria:utenti genovesi]]. Chiunque si senta libero di inserire il proprio nickname se si riconosce in questa tipologia di utenti.
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.
*Sto ''template'' o l'é pe mettilo in sce pagine di zeneixi.
Scrivi {{tl|Genovesi}} nella tua pagina utente e il template apparirà.
== Trattamento formale ==
[[Categoria:Wikipediani]]
</noinclude>
Si inizia con un [[insieme]] [[insieme finito|finito]] [[insieme vuoto|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'' = <tt>topo</tt> e ''t'' = <tt>ragno</tt> allora ''st'' = <tt>toporagno</tt> e ''ts'' = <tt>ragnotopo</tt>.
La concatenazione di stringhe è un'operazione [[associativa]], ma non-[[commutativa]]. Rispetto alla concatenazione, la stringa vuota è l'elemento neutro. In termini [[algebra|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 binaria|relazione]] "è una sottostringa di" definisce una [[relazione d'ordine]] su Σ*, il cui [[minimo]] risulta la stringa vuota.
Se l'alfabeto Σ è [[relazione d'ordine#Ordinamenti ben fondati|ben ordinato]], il cosiddetto [[ordine lessicografico]] costituisce un altro [[insieme totalmente ordinato|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 [[espressione regolare|espressioni regolari]] e dalle [[grammatica formale|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 [[linguaggio di programmazione|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 [[Linguaggio_C_Plus_Plus|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 (linguaggio)|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 (linguaggio)|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
{| cellspacing="0" celpadding="2" border="1" align="center"
|-----
| F || R || A || N || K || <small>NUL</small> || 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:
{| cellspacing="0" celpadding="2" border="1" align="center"
|-----
| <small>length</small> || 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 (computer science)|rope]] (anche dette ''heavyweight string'') può rendere certe operazioni come inserimenti, cancellazioni e concatenazioni più efficienti. [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf]
== 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:
* [[awk]]
* [[Icon programming language|Icon]]
* [[Perl]]
* [[Tcl]]
* [[MUMPS]]
* [[sed]]
* [[SNOBOL]]
Molti programmi di utilità dell'ambito [[Unix|UNIX]] effettuano manipolazioni di stringhe relativamente semplici e possono essere utilizzati per programmare [[algoritmo|algoritmi]] di elaborazione di stringhe piuttosto efficaci. Questi strumenti possono trattare come stringhe anche i files e gli ''stream'' finiti.
I recenti [[linguaggio di scripting|linguaggi di scripting]], come [[Perl]], [[Python programming language|Python]], [[Ruby programming language|Ruby]] e [[Tcl]] si servono di [[espressione regolare|espressioni regolari]] per facilitare le manovre sui testi.
[ [ Categoria:Terminologia del computer ] ] ?
[[Categoria:Linguaggi formali]]
[[en:String (computer science)]]
[[de:Zeichenkette]]
[[fr:Chaîne de caractères]]
[[ru:Строка (тип данных)]]
[[zh:字符串]]
| 