¿Sueñan los ordenadores con imitar a Cervantes?

Cualquier día es bueno, y más si la climatología acompaña, para dar un paseo por el parque. Aquel día coincidía con una feria del libro, y mi amigo Descollante y yo andábamos de caseta en caseta en busca de algún buen libro extranjero de informática (porque de los autóctonos mejor ni hablamos). En una de las casetas estaba Fulano sentado, firmando libros a troche y moche, el último fabricante de bestsellers en serie. A mí no me parece mal siempre que ayude a que algunos lean algo, aunque sea por poder decir que se han leído el último libro de moda, pero mi amigo Descollante suele ser algo más radical e intolerante con la literatura barata y de consumo, y más si mediocres escritores que aprovechan filón literario del último tema de moda, junto con un marketing estudiadísimo, acaban forrándose de la noche a la mañana. Quizás influya que Descollante lleva dentro un escritor frustrado y un montón de negativas de editoriales a sus espaldas. Y no es que sea Borges o Delibes, pero tampoco se le da mal eso de contar historias dándole a la tecla.

Para mí que Fulano tiene un grupo de monos escribiéndole las cosas esas que publica -comenzó a decir Descollante- Seguro que tiene un programa de ordenador que le escribe los libros.
Si fueras capaz de hacer un programa para escribir bestsellers seguro que te forrabas más que Fulano con sus libros -bromeé.
Descollante me miró con media sonrisa y me dijo que quizás no estábamos tan lejos de conseguir que los ordenadores fueran capaces de hacer literatura. No pude esconder mi sonrisa al pensar que ya estaba fanfarroneando de nuevo. Tuvo que captar mi pensamiento porque se paró en seco frente a una terraza-bar y se sentó en una silla sin ni siquiera avisar. Antes de que pudiera reaccionar había pedido dos Cocacolas.
No hace mucho estuve "jugando" con cadenas de Markov para tratar de generar texto con cierto sentido. Y no fue mal el experimento -comenzó a decirme Descollante.
¿Cadenas de Markov? me suena de la facultad -le contesté- pero no recuerdo muy bien en qué consistían.
Descollante sonrió y empezó a explicarme que las cadenas de Markov son una estructura matemática cuya definición formal es algo compleja, aburrida y además requiere sólidos conocimientos de Probabilidad. Así que, saltándose toda la parte aburrida, me explicó que una cadena de Markov es básicamente un grafo dirigido (un digrafo realmente) cuyos nodos están conectados por aristas, y a cada arista se le asocia un valor que es la probabilidad que hay de pasar de un nodo a otro.
La verdad es que me he quedado un poco a cuadros -le dije.
Es muy sencillo, Alberto. Imagina que le mostramos a un ordenador el siguiente texto: "Hola Lola". Y queremos construir una cadena de Markov que nos indique qué probabilidad hay, en esta frase, de pasar de una letra a otra. O mejor dicho de que a una letra le siga otra concreta. Por ejemplo, ¿qué probabilidad hay de que a la letra H le siga una O?
Teniendo en cuenta que las letras posibles son sólo H, O, L, A y espacio (SP), ya que no distinguimos aquí entre mayúsculas y minúsculas. Una cadena de Markov para esta frase tendría el siguiente aspecto.

Según el grafo, la probabilidad de que tras una L aparezca una A es del 50%. Aunque para trabajar con estos porcentajes mejor diremos que la probabilidad es de 0.5, es decir, la probabilidad será un valor real entre 0 y 1. La suma de las probabilidades de las aristas salientes de un nodo siempre tiene que valer 1.
Como ya habrás deducido -me dijo Descollante por sorpresa- el cambio de un estado a otro es una función de probabilidad que depende exclusivamente del estado anterior. Por lo tanto, aquello que haya ocurrido antes del estado anterior no tiene relevancia.
Vale, le dije. Y... ¿cómo se supone que esto va a escribir un libro?
Descollante empezó a reír mientras sacaba su portátil. Mira -me dijo- esto es una prueba que hice el otro día.
Me enseño el siguiente listado.

1. import random
2.  
3. def create_char_map(filepath):
4.   chars={}
5.   f = open(filepath, 'r')
6.   done=False
7.   lastchar=''
8.   while not done:
9.     t=f.readline()
10.     if len(t)==0:
11.       done=True
12.     else:
13.       for c in t:
14.         if not c in chars:
15.           chars[c]={}
16.         if len(lastchar)>0:
17.           if c in chars[lastchar]:
18.             chars[lastchar][c]=chars[lastchar][c]+1.0
19.           else:
20.             chars[lastchar][c]=1.0
21.         lastchar=c
22.   f.close()
23.  
24.   return chars
25.  
26.  
27.  
28. def markov_net(chars):
29.   for c in chars:
30.     tot=0
31.     for n in chars[c]:
32.       tot=tot+chars[c][n]
33.  
34.     for n in chars[c]:
35.       chars[c][n]=chars[c][n]/tot
36.  
37.   return chars
38.  
39.  
40. def generate_text(chars, initial_char, num_chars):
41.   text=''
42.   ch=initial_char
43.   for c in range(num_chars-1):
44.     text += ch
45.     ch=prob_choice(chars[ch])
46.   return text
47.  
48.  
49. def prob_choice(prob_chars):
50.   probability = []
51.   char = []
52.   cur_prob = 0.0
53.  
54.   for c, p in prob_chars.iteritems():
55.     cur_prob = cur_prob + p
56.     probability.append(cur_prob)
57.     char.append(c)
58.  
59.   rnd = random.random() * cur_prob
60.   for i, total in enumerate(probability):
61.     if rnd < total:
62.       return char[i]
63.  
64.  
65. if __name__ == "__main__":
66.   # cambiar alicia.txt por el nombre del
67.   # archivo que se quiera utilizar.
68.   chars = create_char_map('alicia.txt')
69.   chars = markov_net(chars)
70.   text = generate_text(chars, 'd', 1000)
71.   print text

Este programita lee un texto (preferiblemente grande) y construye una malla de probabilidades como esta, pero evidentemente mucho más grande para albergar todas las letras del alfabeto y los signos de puntuación.

La idea es que a partir de esta malla de probabilidades podemos hacer que el ordenador genere un texto sin sentido, pero con silabas habituales del idioma. Algo así como un lenguaje inventado.
Tras ejecutarlo usando el texto del libro Alicia en el país de las maravillas obtuvimos el siguiente texto:

1. de domal ajaterébobasta sesude co taditegabocudes a ni Ala y desuiñose os e itadonco ladezaden mo do paribl dace senanoca ca lie e mel M, diciontando renastuefa seloren coso llomara br Fun sero pre ire do-. atis Resties tun magunande la e sapu sa gils dedonco do acaren dontiga ventrtijo ta e padele aitoja vor dicancora-Nos y qur a puema dicienchadante deca la m!

Pues no creo que esto se venda más que los libros de Fulanito -dije riendo. Aunque la verdad es que parecen palabras inventadas de un idioma de Tolkien. Descollante ejecutó el programa varias veces más obteniendo diferentes resultados.
Bueno, todavía podemos mejorarlo un poco -dijo. En vez de construir una malla de probabilidades con las letras del alfabeto podemos hacerlo directamente con palabras completas.
¿Quieres decir que habría que construir una malla en la que, dada un palabra, contenga la probabilidad con la que aparecerá la siguiente palabra?
Efectivamente -respondió. Por cada palabra del texto analizado incluiremos todas las palabras que en algún momento del texto la sigan y con qué frecuencia, por ejemplo, en la frase "Soy grande porque no soy pequeño" vemos que tras la palabra "soy" aparecen las palabras "grande" y "pequeño", por lo tanto tras la palabra "soy" hay una probabilidad de 0.5 de que aparezca "grande" y 0.5 de que aparezca la palabra "pequeño".
Descollante se puso a teclear y cambió el programa que acabó teniendo el siguiente aspecto:

1. import random
2.  
3. def create_word_map(filepath):
4.   words={}
5.   f = open(filepath, 'r')
6.   done=False
7.   lastword=''
8.   while not done:
9.     t=f.readline()
10.     if len(t)==0:
11.       done=True
12.     else:
13.       for c in t.split(' '):
14.         if not c in words:
15.           words[c]={}
16.         if len(lastword)>0:
17.           if c in words[lastword]:
18.             words[lastword][c]=words[lastword][c]+1.0
19.           else:
20.             words[lastword][c]=1.0
21.         lastword=c
22.   f.close()
23.   return words
24.  
25.  
26.  
27. def markov_net(chars):
28.   for c in chars:
29.     tot=0
30.     for n in chars[c]:
31.       tot=tot+chars[c][n]
32.  
33.     for n in chars[c]:
34.       chars[c][n]=chars[c][n]/tot
35.  
36.   return chars
37.  
38.  
39. def generate_text(chars, initial_char, num_chars):
40.   text=''
41.   ch=initial_char
42.   for c in range(num_chars-1):
43.     text += ' '+ch
44.     ch=prob_choice(chars[ch])
45.   return text
46.  
47.  
48. def prob_choice(prob_chars):
49.   probability = []
50.   char = []
51.   cur_prob = 0.0
52.  
53.   for c, p in prob_chars.iteritems():
54.     cur_prob = cur_prob + p
55.     probability.append(cur_prob)
56.     char.append(c)
57.  
58.   rnd = random.random() * cur_prob
59.   for i, total in enumerate(probability):
60.     if rnd < total:
61.       return char[i]
62.  
63.  
64. if __name__ == "__main__":
65.   chars = create_word_map('alicia.txt')
66.   chars = markov_net(chars)
67.   text = generate_text(chars, 'La', 1000)
68.   print text

Descollante ejecutó el programa de nuevo usando el texto de Alicia en el país de las maravillas y este fue el texto obtenido.

1.  El Lirón se llevó a la boca, mamá! -protestó Alicia quedó muy soliviantadas.
2.  
3.  -¡Ratoncito querido! ¡vuelve atrás, que los pájaros se me suene de estas palabras, su libro de las palabras:
4.  
5.  Cuando volvió hacia arriba, pero no es muy cómodo, y después una de debajo de extrañar que vio al cuerpo, y a suceder en que comer y seguía achicándose rápidamente. Se está del jardín, y Morcaro, duques de haber muchas ganas de manzanas, con el suelo su alrededor hacia el aire. Incluso la dirección en esto, pero no lo que no se interrumpió, y tan terrible entre los pececillos
6.  Para esto no hacer esta mañana -dijo Alicia.
7.  
8.  -¡Yo no quiere decir! -refunfuñó el Grifo.
9.  
10.  Alicia empezaba a oír esto no había largado al principio -dijo Alicia-, qué tipo de que ir a
11.  

Curioso -dije- parece un texto escrito por un paranoico, pero algunas frases tienen sentido y todo. Parece interesante esto de las cadenas de Markov.
Pues sí -dijo Descollante. Las cadenas de Markov se aplican en gran cantidad de campos: en problemas de termodinámica y física estadística, para crear modelos meteorológicos, en simulación, juegos de azar, economía y predicción de valores de bolsa, incluso el algoritmo page rank de google hace uso de él.