mercoledì 2 marzo 2011

So let me introduce to you the one and only Mark V. Shaney!

Un problema ricorrente è quello di generare infiniti nomi/cognomi casuali*.
Per fare questo avete bisogno di un algoritmo che simuli la linguistica, che imiti cioè il processo di generazione di un nome.
Ci sono un sacco di metodi, ma sono quasi tutti complicati e con scarsi risultati.
Il metodo secondo me più efficace e semplice è quello che prevede l'uso delle catene di Markov.

Un processo Markoviano è un processo che determina la Nesima realizzazione in funzione solamente dalla sua N-1esima realizzazione. Una parola può essere vista sotto quest'ottica, cioè la Nesima lettera dipende solo dalla N-1esima lettera.

La parola "ugo" ad esempio può essere vista come una catena di due processi Markoviani con una struttura del tipo u->g->o, dove u->g è il primo processo e g->o il secondo. Di conseguenza, data una lettera qualsiasi si può usare un processo markoviano per trovare la lettera successiva e così via fino a formare una parola intera.

Ma l'operatore (->) come si fa a costruire? Semplice*, con una lista di parole già esistenti, ovvero calcolando la probabilità che da un qualsiasi stato (cioè una lettera) si passi al successivo.

Nell'esempio in cui il vostro vocabolario sia composto dalla sola parola "ugo", la probabilità di passare da "u" a "g" è del 100% così come la probabilità di passare da "g" ad "o". Ma se introduco anche la parola "urlo",
le cose cambiano, cioè la probabilità di passare da "u" a "g" scende al 50%,
perché adesso esiste anche la transizione u->r. Se introduco un numero abbastanza grande di parole posso costruirmi una sorta di matrice di transizione delle probabilità. Supponiamo che le parole siano formate solo da abcdefghijklmnopqrstuvwxyz (facciamo finta che siano 29, non le ho contate per pigrizia*). Avrò una matrice 29x29 che mi dà la probabilità di transizione tra una lettera e la successiva.

L'esempio forse più semplice si può fare con il DNA, le cui basi (lettere) sono solo quattro: ATGC (anche queste non le ho contate per pigrizia). In questo caso la matrice è una 4x4. Supponete di avere una stringa di DNA e.g. ATTTTCGGATTTGTA.
Contate il numero di volte che da una base si passa ad un'altra. e.g. A->T si verifica 2 volte, G->G una volta sola, eccetera... Se normalizzate potete trovare la probabilità che da X si passi a Y. Se moltiplicate per 100 trovate la percentuale di probabilità. In Fig.1 vedete proprio questo per la stringa di DNA di esempio (i numeri sono le percentuali di transizione, le transizioni con probabilità nulla sono state omesse e.g. C->T).

Estendete questa cosa ad una lista di cognomi e invece di 4 basi usate le 29 lettere. Adesso, data una lettera a caso so qual è la probabilità di avere una data lettera successiva a quella scelta. Data dunque una lettera e tirando un dado ("truccato" con le probabilità) posso ottenere la lettera successiva.
Reiterando il processo ottengo una parola.

Se si vuole essere più precisi possiamo anche introdurre una "lettera di inizio parola" tipo $ e una "lettera di fine parola" tipo #. Avremo dunque $ugo# e i cinque processi $->u->g->o->#. In questo modo ho la probabilità che una parola inizi con una data lettera e che finisca con una data lettera.

L'esempio pratico lo avete qui, dove da una lista con pochi cognomi (questa) si possono ricavare potenzialmente infiniti cognomi basati su quelli della lista. Si parte da "$" e si randomizza per trovare la sequenza di lettere. Notare che vengono scartati nomi troppo lunghi, troppo corti o sequenze di consonanti consecutive lunghe. Inoltre potete generare cognomi che profumano di diverse nazionalità. Si noti infine che i nomi sono scelti a caso da una lista, mentre i cognomi sono generati con un processo markoviano.

Di più. Se non avete già sboccato per la noia* potete usare questo metodo per un sacco di cose utili. Ad esempio (i) controllare la spam, verificando se un messaggio ha una probabilità bassa rispetto a quelli che vi arrivano di solito, oppure (ii) simulare lo stile di scrittura usando le parole al posto delle lettere nell'esempio precedente, o (iii) fare previsioni meteo in base a quelle registrate nella vostra zona negli ultimi anni... eccetera

basta!
s.j.

*notare che la frase non cela alcuna ironia.

4 commenti:

Aleksy ha detto...

Figata !

ATG = Met

ma viene considerato il bias dovuto alle diverse probabilità di sostituzione nella tripletta?

sushi john ha detto...

no. la uso come una stringa qualsiasi.

silvia.paperblog ha detto...

Buongiorno,
Ti contatto tramite commento perché non ho trovato nessun altro modo per farlo.
Vorrei farti conoscere il servizio Paperblog, http://it.paperblog.com che ha la missione di individuare e valorizzare i migliori blog della rete. I tuoi articoli mi sembrano adatti a figurare tra le pagine del nostro magazine e mi piacerebbe che tu entrassi a far parte dei nostri autori.

Sperando di averti incuriosito, ti invito a contattarmi per ulteriori chiarimenti,

Silvia

silvia [at] paperblog.com
Responsabile Comunicazione Paperblog Italia
http://it.paperblog.com

sushi john ha detto...

ciao, il materiale di questo blog è pubblicato con licenza creative commons. qui i dettagli http://creativecommons.org/licenses/by-nc-sa/2.5/it/.
se vi attenete a questa licenza potete utilizzare il materiale.