LUA / Algoritmo en cadena de Markov

Bienvenidos sean a este post, hoy continuaremos con el segundo ejemplo para aplicar todos nuestros conocimientos y para ello haremos una implementacion del algoritmo en cadena de Markov, este programa genera texto de forma a la azar basado en que palabras podria seguir una secuencia de n palabras previas en un texto base, para este caso asumiremos el valor de 2 para n, la primera parte del programa lee la base de texto y construye una tabla, por cada prefijo de dos palabras da una lista de las palabras que siguen a ese prefijo en el texto, despues de construir la tabla el programa la usa para generar texto a la azar en donde cada palabra sigue a las dos palabras previas con la misma probabilidad tal como el texto base, como resultado tenemos un texto que es, pero no tanto, muy azaroso (tambien conocido como random).

Para entender mejor este concepto procedamos a trabajar sobre el codigo, primero crearemos un prefijo concatenando dos cadenas con un espacio entre medio:

function prefijo (p1, p2)
	return p1 .. " " .. p2
end

Usamos la cadena SINPALABRA («\n») para inicializar las palabras prefijas y para marcar el fin del texto, tomemos el siguiente texto como ejemplo:

mas lo intentamos mas lo logramos

La tabla de las palabras anteriores seria:

{ 
	["\n \n"] = { "mas" },
	["\n mas"] = { "lo" },
	["mas lo"] = { "intentamos", "logramos" },
	["lo intentamos"] = { "mas" },
	["lo logramos"] = { "\n" }
}

El programa mantiene su tabla en la variable estadotab, para ingresar una nueva palabra en la lista de prefijos de esta tabla debemos usar la siguiente funcion:

function insertar (indice, valor)
	local lista = estadotab[indice]
	if lista == nil then
		estadotab[indice] = { valor }
	else
		lista[#lista + 1] = valor
	end
end

Primero creamos nuestra variable lista en base a estadotab y el valor de indice informado, en caso de que lista sea nil le asigna directamente el valor informado en el argumento a estadotab con el indice, de lo contrario procede a usar lista donde calcula la cantidad de elementos de lista, le agrega uno y asigna a valor, dejandolo al final de la misma.

Para construir la tabla estadotab mantenemos dos variables, p1 y p2, con las ultimas dos palabras leidas, por cada nueva palabra que lee la agregamos a la lista asociada a p1 y p2 y luego actualizamos a p1 y p2, despues de creada la tabla el programa comienza a generar con las palabras de MAXGEN, primero reinicializa las variables p1 y p2, luego por cada prefijo escoge una palabra de forma al azar de la lista de proximas palabras validas, imprime estas palabras y actualiza p1 y p2, veamos el listado completo del programa, primero veamos las funciones auxiliares:

function palabrasTodas()
	local linea = io.read()
	local pos = 1
	return function()
		while linea do
			local i, f = string.find(linea, "%w+", pos)
			if i then
				pos = f + 1
				return string.sub(linea, i, f)
			else
				linea = io.read()
				pos = 1
			end
		end
		return nil
	end
end

function prefijo (p1, p2)
	return p1 .. " " .. p2
end

local estadotab = {}

function insertar(indice, valor)
	local lista = estadotab[indice]
	if lista == nil then
		estadotab[indice] = { valor }
	else
		lista[#lista + 1] = valor
	end
end

En este caso tenemos a la funcion palabrasTodas que hemos visto en post anteriores, y las dos funciones que vimos en este post, pasemos a agregar el cuerpo principal:

local N = 2
local MAXGEN = 10000
local SINPALABRA = "\n"

local p1, p2 = SINPALABRA, SINPALABRA
for p in palabrasTodas() do
	insertar(prefijo(p1, p2), p)
	p1 = p2; p2 = p
end
insertar(prefijo(p1,p2), SINPALABRA)

p1 = SINPALABRA; p2 = SINPALABRA
for i = 1, MAXGEN do
	local lista = estadotab[prefijo(p1, p2)]
	local r = math.random(#lista)
	local proximapalabra = lista[r]
	if proximapalabra == SINPALABRA then return end
	io.write(proximapalabra, " ")
	p1 = p2; p2 = proximapalabra
end

En este caso es bastante simple, tenemos tres variables locales (N, MAXGEN y SINPALABRA) con sus respectivos valores iniciales, el siguiente bloque sera el encargado de crear la tabla, por medio de un for generico y la funcion palabrasTodas usara a insertar con prefijo y asignara todos los valores de p1 y p2, una vez terminado ingresara a SINPALABRA para cerrarlo, el siguiente bloque se encargara de generar el texto, donde utilizara un bucle for cuyo limite sera MAXGEN, despues tendremos una variable local llamada lista con el ultimo valor de estadotab, despues tendremos a r que usara un valor a la azar de la cantidad de elementos de lista, por ultimo una variable llamada proximapalabra que sera de lista y la posicion quedara determinada por r, si despues proximapalabra es igual a SINPALABRA procede a retornar de lo contrario lo escribe en pantalla, y se asigna a p2, asi hasta que encuentre el valor SINPALABRA.

En resumen, hoy hemos visto otras de las lecciones que hemos estado viendo hasta ahora, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.