lunedì 16 aprile 2012

Come funziona il generatore automatico di testi

Nel post precedente ho parlato di un generatore automatico di testi in "lingua italiana". Ecco come ho fatto a costruirlo (ho usato il python perché mi piace, ma anche chi non lo conosce dovrebbe essere in grado di seguire il sorgente, il linguaggio non lo conosco bene nemmeno io e quindi non ho usato costruzioni strane e incomprensibili).

L'idea di base è questa: non faccio una analisi statistica del testo, perché tenere una tabella delle frequenze di tutte le possibili sestine diventa improponibile. Uso invece il testo stesso come generatore.

E cioè: leggo il testo in memoria e, quando ho bisogno di generare un carattere, estraggo una lettera a caso dal testo. E fin qua è facile.

Se devo generare delle coppie di caratteri, invece, faccio così: all'inizio leggo una lettera a caso, poi a partire da un punto casuale del testo cerco la prima occorrenza di quella particolare lettera, e scelgo la lettera immediatamente successiva. Memorizzo quest'ultima lettera e continuo così.

Se poi devo generare delle terne tengo in memoria una coppia di lettere, e a partire da un punto casuale del testo cerco quella coppia e prendo la lettera successiva, e così via.

Vediamo un po' se si capisce il sorgente. Partiamo così:

f=open("i_promes.txt","r")

testo=f.read()

testo=testo.replace("\x0D","")
testo=testo.replace("\x0A","")

N=len(testo)

from random import randrange

M = 1000 #dimensione massima del testo da generare
K = 6 #memoria del generatore casuale

buffer=testo[randrange(N)]
if K==0:
  buffer=""

output=""

Dovrebbe essere semplice: leggo tutto il file all'interno della variabile testo, tolgo dai piedi i caratteri di line feed e carriage return, memorizzo in N la lunghezza del testo, e importo la funzione che mi serve per generare numeri casuali. Poi definisco M, la lunghezza del testo che deve essere generato, e K, la memoria del generatore (nello scorso post ho mostrato il risultato per i valori di K che vanno da 0 a 6).

Poi inizializzo un buffer che memorizzerà i caratteri che dovrò cercare (ma se K è uguale a zero il buffer non mi serve, quindi lo riazzero (lo so, era più elegante inserire un if, ma questa è una correzione dell'ultimo minuto…), e preparo la variabile che memorizzerà l'output e che si chiama, giustamente, output.

Ora viene il bello: la funzione che cerca, all'interno del testo, la prima occorrenza dei caratteri contenuti nel buffer. Il testo viene immaginato infinito, quando arrivo alla fine ricomincio dall'inizio.

def trova(lista,posizione):
  #restituisce il carattere successivo a quelli presenti nella lista
  #a partire dalla posizione data, cerca la prima occorrenza di lista
  #(l'ho chiamata lista, ma e' poi una stringa, ehm)
  l=len(lista)

  if l==0:
    return randrange(N)
  
  trovato = False
  c=0
  j=(posizione) % N

  while not trovato:

    if lista[c]==testo[j]:
      c+=1
    else:
      j=j-c #devo riportare indietro j, maledetto
      c=0

    if c==l:
      trovato=True

    j+=1
    j%=N

  return j%N


Questa funzione trova la posizione in cui compaiono tutti i caratteri di lista, a partire dalla posizione indicata dalla variabile posizione. Le prime righe fanno funzionare il generatore senza memoria: se la lista l è vuota, restituisci un numero casuale e basta. Altrimenti vai avanti.

La variabile trovato si occupa di fare terminare il ciclo; all'inizio non ho ancora trovato niente e quindi è settata a False. La variabile c serve per scorrere il buffer, e la j invece scorre il testo (la j viene sempre usata modulo N, in modo da essere riazzerata se supera N).

Poi comincia il ciclo di ricerca: fino a che non è stato trovato tutto ciò che è contenuto nel buffer si fa una ricerca: se il primo carattere del buffer è uguale al carattere nel testo, aumento c di 1 (così successivamente proverò col secondo carattere del buffer, col terzo, eccetera), altrimenti vado avanti. Il vado avanti mi ha fatto penare, e questo è il motivo del commento nella riga j=j-c.

Le cose stanno in questo modo: supponiamo che il buffer contenga le lettere "abc" e che nel testo siano presenti invece le lettere "aabc". Allora il primo confronto ha successo, ma il secondo no: c viene riazzerato, ma j non deve proseguire dal terzo carattere del testo, cioè b, ma deve tornare indietro. So che mi sono spiegato male, ma provate a togliere la riga maledetta e vedrete che non funziona più.

Il resto è facile: se c è uguale alla lunghezza del buffer l, ho trovato tutto quello che cercavo. Segnalo il tutto settando la variabile trovato e restituisco j (che è stato già incrementato di 1 e che quindi punta al primo carattere dopo la stringa trovata). Ed ecco fatto.

Manca il programma principale, molto semplice:

for i in xrange(M):
    j=trova(buffer,randrange(N))
    buffer+=testo[j]
    output+=testo[j]
    if len(buffer)>K:
      buffer=buffer[1:] #cancello il primo carattere


print output

Faccio un ciclo lungo M, all'interno del quale chiamo la funzione trova. Aggiungo al buffer e a output il nuovo carattere restituito da trova, e se il buffer è troppo lungo lo accorcio.

Fine.

Se avete idee per migliorare, dite pure. Con un generatore a memoria 6 comincia a diventare lento.

13 commenti:

Giuseppe Lipari ha detto...

due commenti:
1) non hai generato secondo la frequenza della lingua italiana, ma secondo la frequenza del testo dei promessi sposi che hai letto. In prima approssimazione direi che va bene!
2) se cancelli il primo carattere dal buffer, nel caso di memoria 6, certe sequenze di 5 caratteri possono avere una frequenza piuttosto bassa, e quindi nel fare la ricerca random in maniera circolare, il programma si ritrova allo stesso punto, e quindi la sequenza diventa facilmente di 7 o di 8 caratteri. Per curiosità, quanto è lungo il testo iniziale?
3) penso si possa ottimizzare, magari ci penso prima di addormentarmi!

zar ha detto...

1) Certo, la "lingua italiana" è rappresentata solo dal testo dei promessi sposi, non ho fatto medie, non ho utilizzato testi diversi.

2) Hai ragione, non ho fatto i conti per capire se potevo spingermi fino a memoria 6. Il bug "maledetto" l'ho scoperto proprio perché a un certo punto il programma era finito su una sequenza che compariva solo 2 volte, ma non si fermava più. Il testo è lungo 1310308 caratteri.

3) Ottimo :-)

Flame Alchemist ha detto...

Penso che cambiare il corpo della funzione trova in questo qua sotto dovrebbe produrre un buon miglioramento.

try:
return testo.index(lista, j) + len(lista)
except:
return testo.index(lista) + len(lista)

Che cerca la prima occorrenza di lista in testo a partire dalla posizione j, e se non la trova, cerca nell'intero testo.

Ogni tanto entra in qualche strano loop e ritorna mezzo testo costituito da -- o da spazi, ma per la maggior parte delle volte funziona (ma magari è solo il mio testo un po' strano)

Giuseppe Lipari ha detto...

riguardo al puno 2) mi è venuto un altro dubbio. Non sarebbe più "corretto" ripartire a caso da un altro punto invece di cancellare la prima lettera del buffer? perché osì facendo la probabilità di alcune stringhe ti dipende dalla storia con cui ci si arriva. O era proprio questo che volevi fare e non l'ho capito?

Juhan ha detto...

Sembra tutto OK. Volendo l'istruzione
testo=testo.replace("\x0A","")
la modificherei così
testo=testo.replace("\x0A"," ")
e \x0A si può scrivere anche \n che è più usuale e leggibile (newline).
Ma devo ancora capire se la lunghezza delle parole è significativa. (sto facendo altro, o meglio dovrei).

zar ha detto...

@Flame Alchemist: uh, proverò.

@Giuseppe Lipari: mh, se riparto da capo non genero più secondo la frequenza delle coppie/terne, ecc, no? Per esempio, se (con un generatore a memoria 1) prima genero "ab" e successivamente "cd", la coppia "bc" non risulta avere la frequenza giusta. La "c" non ha memoria della precedente "b".

@Juhan: dici che eliminando sia cr che lf ho inavvertitamente unito delle parole, cancellando lo spazio? Forse sì, in effetti.

Giuseppe Lipari ha detto...

Perché dici che "bc" non ha la "frequenza giusta"? Facciamolo con 3 caratteri. Tutte le sequenze "bcd" devono cominciare con "b". Supponiamo ci siano 100 sequenze che cominciano per "b", e di queste 25 sono "bcd". Se cerchi nel file una posizione a caso di "b", la probabilità di trovare una sequenza "bcd" è correttamente pari a un quarto rispetto a quella di trovare "b". O no? Se invece parti da "abc", la probabilità di trovare "bcd" è condizionata dall'aver trovato prima una sequenza che terminasse con "bc".

Supponi che il testo contenga per errore 6 spazi consecutivi in mezzo a centinaia di migliaia di caratteri diversi. Supponiamo anche che, per caso, la prima posizione generata corrisponda al primo spazio della sequenza di 6.
Quello che succede è che a causa della memoria, viene generato un output solo di spazi. Ora, questo mi fa sospettare che ci sia un problema da qualche parte dovuto al condizionamento (ma potrei sbagliarmi).

zar ha detto...

L'esempio che hai fatto sulla sequenza di 6 spazi è giusto. Se c'è solo quella, e ci arrivo "sopra", non ne esco più. Ma questo è un esempio limite, non si fa una gran statistica con un solo elemento.

Invece, per quanto riguarda l'altro esempio, non sono d'accordo. Cioè, se voglio che la memoria del generatore sia 1, e cioè che ogni carattere dipenda dal precedente, devo tenere nel buffer sempre un carattere e basarmi su quello per trovare il successivo.

Allo stesso modo, se voglio che la memoria sia 2, devo tenere sempre memorizzati 2 caratteri. Se sono stati generati "a" e successivamente "b", il prossimo carattere deve essere selezionato in base alla probabilità di trovare "abx", per qualunque x. Non posso dimenticarmi del fatto che sono usciti "a" e "b". Se lo facessi, non mi baserei più sulla probabilità giusta.

Giuseppe Lipari ha detto...

Forse ho capito quello che vuoi dire (credo).

Il tuo requisito è: il testo generato deve avere in media le stesse proprietà statistiche del testo di partenza. Più formalmente: se genero prendo l'insieme di tutti i possibili testi generabili, la probabilità di trovarci una certa stringa è pari alla probabilità di ottenerla nel testo di partenza.

Se nel testo di partenza non c'è la sequenza "bc", non ci deve essere neanche nel testo di arrivo. Quindi, per questo bisogna tenere "memoria". Dopo aver generato "ab", bisogna per forza tirare fuori uno dei caratteri che segue "b" nel testo di partenza e quindi non posso resettare il buffer.

I casi limite però ci sono ancora: se abbiamo nel testo di partenza delle parole strane (come nel mio esempio degli spazi), potremmo entrare in loop e generare testi che non hanno le stesse statistiche di quello di partenza. Però, questi testi li generiamo con probabilità bassa; se prendiamo invece l'insieme di tutti i testi generati, le proprietà statistiche si conservano.

(naturalmente, tutto questo sarebbe da dimostrare... )

Flame Alchemist ha detto...

Fra l'altro se non mi sbaglio si parlava di qualcosa di simile in "Programming Pearls" nel capitolo dedicato ai processi Markoviani (anzi, catene).

E ne parlava anche il buon Shannon nel suo "Mathematical theory of communication"; ovviamente lui era ancora fermo ai libri.

passante ha detto...

Questa non è efficientissima, ma non è particolarmente sensibile ad alti valori di lun_radice ed è facilmente customizzabile. Prevede che siano mantenuti i \n e può lavorare sia per lettere che per parole.

import re, random

def testo_random( testo_modello, lun_radice, lun_testo_random, parole=False ):
    if parole:
        regex_radice = r'(?<=\n)(?:\w+\W+){'
        regex_continuazione = r'\w+\W+'
    else:
        regex_radice = r'(?<=\n).{'
        regex_continuazione = '.'
    regex_radice += str( lun_radice ) + '}'
    new_testo_random = random.choice( re.findall( regex_radice, testo_modello ) )
    if parole:
        coda_list = re.sub( r'(?<=\W)(\w)', r'####\1', new_testo_random ).split( '####' )
    else:
        coda_list = list( new_testo_random )
    print( new_testo_random, end = '' )
    while len( new_testo_random ) < lun_testo_random :
        coda_text = ''.join( coda_list )
        regex_radice = '(?<=' + re.escape( coda_text ) + ')' + regex_continuazione
        more_text = random.choice( re.findall( regex_radice, testo_modello, flags=re.DOTALL ) )
        new_testo_random += more_text
        coda_list = coda_list[1:] + [ more_text ]
        print( more_text, end = '' )

zar ha detto...

Uh, espressioni regolari a profusione...

zar ha detto...

@Giuseppe: sì, le cose stanno come dici nell'ultimo commento (compresa la faccenda dei casi limite).