Processo markoviano

Questo post necessita di una lunga introduzione.
Circa vent'anni fa mi capitò d'ascoltare un frammento di musica campionata di pochi secondi (*1).
Nonostante la sua brevità mi piacque moltissimo e mi rimase fortemente impresso. Le uniche parole chiaramente distinguibili erano “21th century digital boy” ma per molti anni non ne feci di niente.
Poi, ormai circa 8 anni fa quando ero in Olanda, risentii la stessa musica e, grazie a internet, fu facile scoprire che la canzone era 21th century digital boy dei Bad Religion. Così mi decisi finalmente a comprare il relativo album “Stranger than fiction” del quale mi piacquero praticamente tutti i vari pezzi.
Fra i vari brani c'è anche “Markovian Process” ovvero “Processo Markoviano”.

Ma che cos'è un processo markoviano?
Per il momento preferisco lasciare in sospeso questa domanda e passare a un argomento del tutto (ma solo apparentemente in realtà!) diverso.

Come forse avrete notato di tanto in tanto mi capita di imbarcarmi in vari progetti software per realizzare applicazioni disparate. Un problema che ho ripetutamente affrontato è quello di creare dei nomi casuali. Per nomi intendo nomi propri di persona come “Gabriele”, “Tommaso”, “Marco”, “Federico” o “Roberto” solamente generati al computer mischiandone le sillabe.

Ovviamente provai diversi algoritmi ma il più semplice di essi mi dette risultati deludenti: l'idea era quella di fornire al computer le sillabe di numerosi nomi reali in maniera che potesse poi ricomporle casualmente. Sfortunatamente, accanto a nomi passabili, come “Gaberco” o “Madele” ottenevo anche delle brutte cacofonie come “Rorco” o peggio “Tomco”.
Arrivai alla conclusione che non potevo usare le sillabe in maniera totalmente casuale ma che dovevo farmi guidare dal finale di quella precedente. Cioè, solo la prima sillaba era totalmente casuale (ma comunque scelta solamente fra le prime sillabe dei vari nomi), la seconda infatti sarebbe stata scelta in funzione della lettera finale della prima sillaba.
Faccio un esempio perché è veramente più facile da capire vedendolo in pratica che a spiegandolo teoricamente!
Prendiamo i nomi “Ga-bri-ele”, “Ma-ri-o”, “Ro-ber-to” e “Ro-mi-no”
Le prime sillabe possibili sono “Ga”, “Ma”, “Ro” e “Ro” (in questo caso “Ro” appare due volte ma non è un problema: sarà solo più probabile).
Fra queste quattro supponiamo che venga scelta casualmente “Ga”. Adesso la seconda sillaba non sarà scelta fra tutte le seconde sillabe ma solamente da quelle che ne seguivano una terminante per “a”, ovvero “bri” o “ri”. Supponiamo che venga scelta “ri”. Adesso la terza sillaba verrà scelta fra “ele”, “o” ma anche “no” (da “Romino”...).
Supponendo che venga scelto “no” si otterrà il nome “Garino” che proprio carino non è ma suona comunque credibile...

Nel complesso il codice necessario per implementare questo algoritmo è relativamente semplice: io ho realizzato in Java (*2) un oggetto con il costruttore che prende un array di stringhe (i nomi iniziali) e, alla bisogna, genera un nome casuale tramite il metodo generateName().

Qualche esempio di nomi femminili generati a partire dalla seguente lista:
String[] fNames =
{
"Gra,zia", "E,le,na", "A,gla,ia", "Pa,tri,zia", "Vi,via,na",
"Giu,sep,pi,na", "Mi,ri,am", "Ri,ta", "Ce,li,de", "A,rian,na",
"An,ge,la", "Ti,zia,na", "En,ri,ca", "Fran,ces,ca", "Bar,ba,ra",
"Sa,ra", "Chia,ra", "So,fia", "Le,ti,zia", "Be,ne,det,ta",
"I,sa", "An,drei,na", "Ma,ria", "Sil,via", "Se,re,na",
"Gu,ia", "Ca,ro,li,na", "Si,mo,na", "Va,nia", "Va,len,ti,na",
"E,li,sa", "Da,nie,la", "Giu,lia", "An,na", "A,les,san,dra",
"Lau,ra", "E,mi,lia", "Gia,da", "E,li,sa,bet,ta", "An,to,niet,ta",
"Zai,ra", "Ve,ro,ni,ca", "I,da", "Ma,ri,sa", "Nau,si,ca",
"Gai,a", "Do,na,tel,la", "Sa,bri,na", "Ger,tru,de", "Mar,cel,la",
"Su,san,na", "Vio,la"
};

Nomi generati dal computer:
Ada
Cazia
Lauseppica
Sabrisa
Lausanna
Mira
Daria
Sonatella
Abrizia
Iziaia

Che a parte “Sonatella” e soprattutto “Iziaia” sono abbastanza credibili...

Volendo si potrebbe “migliorare” l'algoritmo usando per la scelta della sillaba successiva non solo l'ultima lettera ma anche la penultima: io non l'ho fatto perché volevo poter usare una base di nomi molto piccola ma sono sicuro che i risultati sarebbero ancor più realistici.

Ma torniamo al nostro processo Markoviano.
La definizione data da Wikipedia.it è: “Un processo stocastico markoviano o processo di Markov è un processo stocastico nel quale la probabilità di transizione che determina il passaggio ad uno stato di sistema dipende unicamente dallo stato di sistema immediatamente precedente (proprietà di Markov) e non dal come si è giunti a tale stato (in quest'ultima ipotesi si parla di processo non markoviano).”

Questa definizione vi dice niente? Ok, leggete allora le sue applicazioni pratiche (sempre da wikipedia.it): “Modelli di tipo markoviano vengono anche utilizzati nel progetto di reti di telecomunicazioni; la teoria delle code che ne consegue trova applicazione in molti ambiti: dalla fila alle poste ai pacchetti in coda in un router.”

Beh, queste definizioni suonano piuttosto matematiche ma tradotte terra terra nell'ottica della mia applicazione equivalgono a: “Un processo markoviano è un processo casuale nel quale il passaggio da una sillaba alla successiva dipende unicamente dalla prima di queste due sillabe”

Insomma, come spesso mi capita, per la mia applicazione sui nomi avevo reinventato la ruota: per l'esattezza il processo markoviano!

Nota (*1): all'epoca TUTTI i campionamenti erano brevi perché i computer non erano abbastanza potenti!
Nota (*2): Non ho voglia di copiare il codice qui sul blog perché dovrei formattarlo, ripulirlo etc... Se qualcuno però dovesse essere interessato mi faccia sapere...

Share