RICONOSCIMENTO DI
SEQUENZE DI EVENTI
Il problema
Realizzare un algoritmo per identificare in una
sequenza di caratteri provenienti da un
dispositivo d’input e di lunghezza non nota a
priori la parola SUN, in qualunque contesto si
trovi.
Una soluzione
Il problema potrebbe essere ricondotto al
riconoscimento di stringhe:
• si memorizza in un vettore di caratteri una
parte della sequenza d’input e poi,
• a partire dalla prima posizione del vettore, si
effettua il confronto tra una sottostringa lunga
3 caratteri e la parola di riferimento (SUN).
• Se sono uguali si dichiara di aver trovato la
parola cercata.
• Si procede così di seguito, avanzando ogni
volta di una posizione, finché ci sono
abbastanza caratteri nel vettore.
• Esauriti i caratteri del vettore di supporto, se
ne caricano altri dal dispositivo di input.
• Prima però si devono trasferire in testa al
vettore gli ultimi due caratteri della sequenza
precedente: potrebbero infatti contenere
l’inizio della parola.
Si preferisce adottare un altro approccio,
comune a tutti i casi in cui occorre riconoscere
sequenze di eventi.
La macchina a stati
• L’idea è quella di analizzare un elemento per volta (in
questo caso, un carattere per volta) e di memorizzare
in una apposita variabile, denominata stato_corrente,
la condizione in cui ci si trova.
• Si svolge l’analisi di quanto può succedere aiutandosi
con un disegno (diagramma a stati o pallogramma) e
con una sequenza di caratteri qualsiasi, ideata in
modo da contemplare tutti i casi possibili, come la
seguente:
“QUESTO E’ UN TESTO DI COLLAUDO,
CONTIENE SUN MA ANCHE SU E SSUN
E ANCORA SUSUN NONCHE’ SUNSUN,
CIOE’ DUE STRINGHE SUN
CONSECUTIVE”.
• All’inizio si suppone di essere in uno stato chiamato
stato_iniz, e si analizzano i caratteri uno per volta,
man mano che arrivano.
• Fin quando si ricevono caratteri diversi da ‘S’, si resta
nello stesso stato stato_iniz.
• Quando arriva il carattere ‘S’, si passa ad un nuovo
stato chiamato stato_s.
ALTRI CARATTERI
‘S’
START
STATO_INIZ
STATO_S
• In stato_s, si verifica se arriva il carattere ‘U’, nel
qual caso si passa allo stato stato_u.
• Se il carattere che arriva non è ‘U’, controllo che non
sia ‘S’, nel qual caso si resta in stato_s (ci si trova in
una situazione del tipo ...SSUN...).
• In tutti gli altri casi si è trattato di un falso allarme e si
torna a stato_iniz.
ALTRI CARATTERI
‘S’
‘S’
‘U’
START
STATO_INIZ
STATO_S
ALTRI CARATTERI
STATO_U
• In stato_u, se arriva ‘N’, si va in stato_fin, in cui si
dichiara di aver riconosciuto la parola SUN;
• se invece arriva ‘S’, si torna in stato_s (situazione del
tipo ...SUSUN...),
• mentre in tutti gli altri casi si torna a stato_iniz e si
continua l’analisi fino all’esaurimento dei caratteri in
input.
ALTRI CARATTERI
‘S’
‘S’
‘U’
‘N’
START
STATO_INIZ
STATO_S
ALTRI CARATTERI
ALTRI CARATTERI
STATO_U
‘S’
STATO_FIN
• Se interessa riconoscere la parola SUN una
sola volta, quando si raggiunge stato_fin si
termina;
• altrimenti si fa coincidere stato_fin con
stato_iniz e si continua.
ALTRI CARATTERI
‘S’
‘S’
‘U’
START
STATO_INIZ
STATO_S
ALTRI CARATTERI
STATO_U
‘S’
ALTRI CARATTERI
‘N’ : PAROLA RICONOSCIUTA
• Si considera quest’ultimo caso, in modo che
l’algoritmo tratti correttamente situazioni come
...SUNSUN..., identificando due occorrenze della
stringa SUN.
• Nella realizzazione dell’algoritmo, si utilizza il
costrutto switch (o, in alcuni linguaggi, il costrutto
case) in sostituzione della cascata di if necessaria per
analizzare il contenuto di stato_corrente.
Algoritmo
•
•
Pongo il valore STATO_INIZ in
stato_corrente
Finché ci sono caratteri
–
–
leggo un carattere in carat
switch su stato_corrente
• caso STATO_INIZ: se carat = ‘S’
– pongo il valore STATO_S in stato_corrente
• caso STATO_S: se carat = ‘U’
– pongo il valore STATO_U in stato_corrente
• altrimenti
– se carat ’S’
» pongo il valore STATO_INIZ in
stato_corrente
•
•
caso STATO_U: se carat = ‘N’
– visualizzo “Parola riconosciuta”
– pongo il valore STATO_INIZ in stato_corrente
altrimenti
– se carat = ‘S’
» pongo il valore STATO_S in stato_corrente
– altrimenti
» pongo il valore STATO_INIZ in stato_corrente
• Fine.