Generando texto pseudo-aleatorio mediante cadenas de Markov en python.

Primero, una breve definición de Wolfram:

A Markov chain is collection of random variables  (where the index  runs through 0, 1, ...) having the property that, given the present, the future is conditionally independent of the past.

In other words,

Por si no queda claro, la wikipedia viene en nuestra ayuda:

En teoría de la probabilidad, se conoce como cadena de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende del evento inmediatamente anterior. En efecto, las cadenas de este tipo tienen memoria. "Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Márkov de las series de eventos independientes, como tirar una moneda al aire o un dado.

 Las cadenas de Markov tienen múltiples aplicaciones (especialmente en el campo de la ciencia), pero nos centraremos en la generación de textos aleatorios pero legibles.

El algoritmo consiste en:

1. Tomar un texto que nos servirá como fuente para establecer las cadenas y sus transiciones.
2. Tomar dos palabras aleatorias y consecutivas del texto fuente. Estas constituyen la semilla del estado actual. En todo momento las dos últimas palabras son las que generan las subsiguientes cadenas.
3. General la siguiente palabra de la cadena de transiciones de Markov. Para ello se usa el texto original, seleccionando al azar de entre las posibles soluciones de la cadena.
4. Repetir hasta completar el texto.

El código en python es:

import random

class Markov(object):

    def __init__(self, open_file):
        self.cache = {}
        self.open_file = open_file
        self.words = self.file_to_words()
        self.word_size = len(self.words)
        self.database()


    def file_to_words(self):
        self.open_file.seek(0)
        data = self.open_file.read()
        words = data.split()
        return words


    def triples(self):
        """ Generates triples from the given data string. So if our string were
                "What a lovely day", we'd generate (What, a, lovely) and then
                (a, lovely, day).
        """

        if len(self.words) < 3:
            return

        for i in range(len(self.words) - 2):
            yield (self.words[i], self.words[i+1], self.words[i+2])

    def database(self):
        for w1, w2, w3 in self.triples():
            key = (w1, w2)
            if key in self.cache:
                self.cache[key].append(w3)
            else:
                self.cache[key] = [w3]

    def generate_markov_text(self, size=25):
        seed = random.randint(0, self.word_size-3)
        seed_word, next_word = self.words[seed], self.words[seed+1]
        w1, w2 = seed_word, next_word
        gen_words = []
        for i in xrange(size):
            gen_words.append(w1)
            w1, w2 = w2, random.choice(self.cache[(w1, w2)])
        gen_words.append(w2)
        return ' '.join(gen_words)

 Y su uso es (como ejemplo se usa el "My man jeeves" del Proyecto Gutemberg):

In [1]: file_ = open('/home/shabda/jeeves.txt')

In [2]: import markovgen

In [3]: markov = markovgen.Markov(file_)

In [4]: markov.generate_markov_text()
Out[4]: 'Can you put a few years of your twin-brother Alfred,
who was apt to rally round a bit. I should strongly advocate
the blue with milk'

 Cómo funciona el algoritmo:

• Las dos últimas palabras forman el estado actual.
• La siguiente palabra depende únicamente del estado actual (tan solo dos palabras).
• La siguiente palabra es elegida al azar de las posibles cadenas extraídas del texto original.

Como ejemplo, del texto:
“The quick brown fox jumps over the brown fox who is slow jumps over the brown fox who is dead.”
Se extraen las cadenas:
{('The', 'quick'): ['brown'],
 ('brown', 'fox'): ['jumps', 'who', 'who'],
 ('fox', 'jumps'): ['over'],
 ('fox', 'who'): ['is', 'is'],
 ('is', 'slow'): ['jumps'],
 ('jumps', 'over'): ['the', 'the'],
 ('over', 'the'): ['brown', 'brown'],
 ('quick', 'brown'): ['fox'],
 ('slow', 'jumps'): ['over'],
 ('the', 'brown'): ['fox', 'fox'],
 ('who', 'is'): ['slow', 'dead.']}
Ahora si comenzamos con "brown fox" las opciones para la siguiente palabra son "jumps" o "who". Si se escoge "jumps", tenemos "fox jumps" cuyo siguiente eslabón de cadena es "over" y así se genera el texto.

Notas:

• Cuanto mayor sea el texto fuente (y más complicado), mayor será el número de eslabones posibles, tendremos más elementos para elegir de entre los que forman una cadena y por tanto mejores serán los resultados del texto.
• En este caso tomamos cadenas de dos elementos, pero a medida que tomamos un mayor número de palabras para el estado base, menor será la aleatoriedad aparente del texto (se forman menos galimatías).
• No es aconsejable quitar los signos de puntuación del texto fuente, ya que serán incluidos en las cadenas dando lugar a mejores textos.