Cloud with rain
.:G
G:.
0 and 1 serie, black on white
pulled card
myjsp.feelinglinux.com
ver. 1.1.9-4
Hallo, welcome to my world.
Here you can find some stuff about computer science.
<<< Enjoy your visit! >>>
0 and 1 serie, white on black

Riconoscimento di testo con automi: teoria ed esempio in C

        Scritto: Giansante Gabriele, 2001     

Cos'e'un Automa?
Come si puo' intuire dal nome, e' un qualcosa che ci permette di automatizzare un procedimento. Nel caso di questo documento, si parlera' di automi a stati finiti per il riconoscimento di testi, senza passare per la definizione di grammatica e linguaggio. Non e' intenzione di questo documento approfondire troppo l'argomento del riconoscimento dei testi.

Il concetto di automa e' molto potente e facilmente implementabile, almeno ad un livello senza particolari ottimizzazioni.
Idealmente, possiamo immaginare un automa a stati finiti come una macchina che legge un testo un carattere alla volta. A seconda del carattere letto, puo' effettuare le seguenti operazioni:

  1. Avanzare di una posizione per leggere il carattere successivo;
  2. Terminare il proprio lavoro.
Come fa l'automa a muoversi lungo la stringa di input? Interviene il concetto di stato. Uno stato non e' altro che la fotografia di un istante, di una situazione ben precisa.
Ad esempio, vediamo un caso pratico come l'accensione di una autovettura. Alcuni stati che si possono individuare sono:
  1. motore spento, chiave non inserita;
  2. motore spento, chiave inserita ma non girata;
  3. motore acceso, chiave inserita e girata;
  4. motore spento, chiave inserita e girata.
Pubblicita'
Diciamo che questi stati sono la memoria usata per il processo di accensione della macchina.
Da uno stato all'altro e' possibile passare compiendo un'azione. Ad esempio, per passare dallo stato (2) allo stato (3), si puo' compiere l'azione di girare la chiave di avviamento.

Tornando all'automa per il riconoscimento del testo, e' facile vedere a questo punto come si possa procedere alla scansione di una stringa: anticipando un po' il discorso, abbiamo gli stati formati dal carattere letto e dalla posizione raggiunta nella lettura del testo; le azioni possibili saranno due, ovvero quelle indicate in precedenza.

Formalmente, un automa a stati finiti e' una quintupla (insieme ordinato di 5 elementi) del tipo

A=(Alfabeto, Stati, Funzione di transizione, Stato iniziale, Stati finali)
L'alfabeto e' un insieme di simboli possibili (nel nostro caso un set di caratteri), cioe' tutti i simboli che si possono incontrare nella stringa di ingresso (input).
Gli stati, in accordo con quanto gia' spiegato, sono un insieme di simboli (S1, S2, S3, ecc.) che identificano la situazione in cui si e' arrivati durante la lettura del testo: hanno informazione della posizione in cui si e' arrivati a leggere e quindi di tutta la storia passata per arrivare allo stato stesso.
La funzione di transizione, nel riconoscimento del testo, e' una funzione che associa ad ogni stato "Si" un altro stato "Sj" a seconda del carattere letto alla posizione associata ad "Si". Ad esempio, se "F" e' la funzione, potrebbe esserci una regola del tipo
F(S1,"d")=S5
In pratica, la funzione di transizione identifica le azioni da compiere per passare da uno stato ad un altro.
Fig. ALo stato iniziale e' lo stato da cui si parte, cioe' la condizione iniziale: ogni automa prevede uno stato iniziale.
Gli stati finali sono un insieme di stati dal significato particolare. Quando l'automa raggiunge un stato finale durante la propria elaborazione, significa che il riconoscimento e' avvenuto con successo. Che accade se l'automa termina la lettura del testo e si trova in uno stato che non e' finale? In una situazione del genere, l'automa termina la propria esecuzione con una condizione di errore (che puo' essere un valore booleano falso in una implementazione software).

Riassumendo, un automa a stati finiti, per il riconoscimento di un testo, legge un carattere alla volta, passando da uno stato ad un altro nel modo specificato dalla funzione di transizione. Al termine della scansione, si trovera' in uno stato finale (successo) o in un altro stato (insuccesso).

Per implementare via software un automa, e' bene costruirlo prima graficamente. Nella figura A viene mostrato un automa per il riconoscimento di tutte le stringhe che contengono la coppia di lettere "ci" (es. "facciamo", "facile", "bacino", "fucina").
Costruire un automa graficamente non e' difficile. Basta scegliere uno stato di partenza e tracciare il flusso delle azioni, carattere per carattere, seguendo l'esempio nella costruzione seguente:
 
 


1) Prendiamo uno stato iniziale.

2) Abbiamo un primo pezzo formato da qualsiasi sequenza di caratteri non contenente una "c".

3) Dobbiamo riconoscere una "c" ed andare in un altro stato.

4) Quello che dobbiamo riconoscere, a questo punto, e' una "i". Se NON abbiamo una "i", allora dobbiamo tornare allo stato iniziale per cominciare di nuovo a cercare una "c", a partire dalla posizione in cui siamo arrivati. Se invece la "i" e' stata trovata, passiamo ad un nuovo stato in modo da poter agire di conseguenza.

5) Se arriviamo nello stato 2, significa che la sottostringa "ci" e' stata riconosciuta e siamo arrivati ad una stringa letta del tipo "*ci" (dove * significa qualsiasi sequenza di caratteri).
Qunidi, il nostro lavoro e' terminato. Tutti i caratteri successivi non sono influenti per il risultato finale del riconoscimento. Per questo motivo dobbiamo inserire un arco che torna allo stato 2 (finale) per qualsiasi carattere.
6) Mettendo insieme i pezzi, otteniamo lo schema mostrato nella figura A.
Notare che se la richiesta fosse stata di riconoscere tutte le parole che terminano con "ci", l'arco di loop sullo stato 2, avrebbe avuto termine sullo stato 0 invece che sul 2, perche' qualsiasi carattere successivo alla sottostringa "ci" avrebbe determinato un temporaneo risultato negativo (stringa non riconosciuta).

 

Una volta pronto lo schema grafico, la realizzazione software e' immediata. Verra' qui usato il C ("gcc" di Linux).

Consideriamo due funzioni C: Transizione ed Automa. La prima si occupa dell'indicazione del prossimo stato, dipendentemente dal carattere e dallo stato ricevuti in ingresso: restituisce un numero intero positivo simboleggiante lo stato a cui passare (es. 0=S0, 1=S1, ecc.). La seconda funzione, "Automa", e' l'implementazione dell'automa: restituisce "0" in caso di successo, "-1" in caso di insuccesso.
L'insieme di stati verra' rappresentato come un array di interi, il cui indice sono gli stati stessi ed il cui valore puo' assumere due valori: 0="stato normale", 1="stato finale".
Vediamo il codice generale per la funzione "Automa":

int Automa(char testo[], int numero_caratteri, int stati[], int numero_stati)
{
  int i;
  //Lo stato iniziale di solito e' S0.
  int stato=0;
  //Scandisco tutti i caratteri. In realta', non sempre e' necessario
  //leggere tutti i caratteri.
  for (i=0; i<numero_caratteri; i++)
  {
    //Applico la funzione di transizione allo stato corrente per
    //passare allo stato successivo.
    stato=Transizione(stato, testo[i]);
  }
  if (stato==-1) return -1; //Errore nella funzione di transizione
  if ((stato<numero_stati)&&(stati[stato]==0)) return -1;
  else  return 0;
}
La funzione e' semplicissima: scandisce tutto il testo chiamando la funzione Transizione per passare da un testo ad un altro. Alla fine controlla se lo stato raggiunto e' uno stato finale e restituisce il risultato opportuno.
Vediamo quindi la funzione "Transizione":
int Transizione(int stato, char carattere)
{
  //Vedo qual'e' lo stato a cui sono arrivato, in modo da agire di conseguenza.
  switch (stato)
  {
    //Stato 0 (di solito e' quello iniziale)
    case 0: switch (carattere) //Il carattere letto mi determina il prossimo stato.
            {
              case 'a': return ... //Ci va il numero dello stato secondo le indicazioni
                                   //dello schema grafico preparato a mano.
              case 'b': return ...
              ...
              default: return -1;  //Errore: carattere non previsto.
            }
            break;
    //Stato 1
    case 1: ...
    ...
    //Uno stato non valido
    default: return -1;  //Errore: stato non previsto.
  }
}
La struttura della funzione "Transizione" e' di comprensione immediata. Ovviamente, invece di usare ogni volta tutti gli stati possibili (0,1,2,...) e tutti i caratteri possibili (a,b,c,...), si terra' conto solo di quelli effettivamente impiegati nello schema grafico. Un'altra osservazione da fare e' che, in caso di errore (stato o carattere non previsti dallo schema), viene restituito uno stato di errore (simboleggiato dall'intero "-1").

Ecco il codice della funzione "Transizione" nel caso dell'esempio mostrato nelle figure precedenti (la funziona "Automa" non cambia):

int Transizione(int stato, char carattere)
{
  switch (stato)
  {
    case 0: switch (carattere)
            {
              case 'c': return 1;
              default: return 0;  //A differenza del codice generale mostrato sopra,
                                  //a noi serve individuare l'informazione
                                  //"tutti i caratteri tranne". Lo si fa usando il caso di
                                  //default: non ho un errore per carattere sconosciuto.
            }
            break;
    case 1: switch (carattere)
            {
              case 'i': return 2;
              default: return 0;  //Vedi commento precedente
            }
            break;
    case 2: return 2;  //Non mi interessa piu' quali caratteri leggo, tanto ho gia' capito
                       //che il testo di ingresso contiene la sillaba "ci", e quindi il 
                       //riconoscimento e' andato a buon fine.
    default: return -1;
  }
}
L'automa puo' essere lanciato nel seguente modo:
//Usata per contenere il responso dell'automa.
int riconosciuto;
//Numero dei caratteri utili del testo.
int num_caratt=34;
//Testo (l'array e' sovradimensionato per evidenziare l'uso del
//parametro "numero di caratteri").
//Il testo dovrebbe essere riconosciuto per la presenza di "ci"
//nella parola "riuscira". La frase puo' essere modificata a piacere.
char frase[255]="Questa e' una prova. Ci riuscira'?";
//Numero degli stati usati.
int num_stati=3;
//Insieme degli stati.
int stati[255];
stati[0]=0;
stati[1]=0;
//Lo stato 2 e' finale.
stati[2]=1;
//Avvio l'automa.
riconosciuto=Automa(frase, num_caratt, stati, num_stati);
if (riconosciuto==0) printf("Testo valido.\n");
else printf("Testo non valido.\n");

Hai trovato utile questo articolo?
Aiutami a condividerlo o metti un "mi piace".
Grazie mille!


Gli strumenti di condivisione (Google+, Facebook) sono visibili in alto a destra solo dopo aver accettato la policy di utilizzo dei cookie per questo sito.
FAQ - Come faccio a cambiare la mia scelta?

 

Strumenti (myjsp.feelinglinux.com)
Gioco: allenamento con la tastiera Strumenti di codifica/decodifica URI (%-encoding) e Base64 Strumenti di calcolo online per IP e Reti
QUIZ GAME
Quiz game

Cerca @myjsp.feelinglinux.com

Pubblicita'