Markov Chain Text Generation

Question

Nos acaban de asignar un nuevo proyecto en mi clase de estructuras de datos - Generando texto con cadenas de markov.

general

Dado un archivo de texto de entrada, se crea una semilla inicial de longitud n caracteres. Añadimos eso a nuestra cadena de salida y elegimos nuestro próximo carácter basado en el análisis de frecuencia ..

Este es el gato y hay dos perros.

Initial seed: "Th" 
Possible next letters -- i, e, e 
Therefore, probability of choosing i is 1/3, e is 2/3. 

Now, say we choose i. We add "i" to the output string. Then our seed becomes 
hi and the process continues. 

Mi solución

tengo 3 clases, Nodo, ConcreteTrie y Conductor

Por supuesto, la clase ConcreteTrie no es un trie del sentido tradicional. Así es como funciona:

Teniendo en cuenta la frase con k = 2:

Este es el gato y hay dos perros.

I generar nodos Th, hi, is, ... + ..., gs, s. Cada uno de estos nodos tiene hijos que son la letra que los sigue. Por ejemplo, Node Th tendría hijos i y e. Mantengo los recuentos en cada uno de esos nodos para que luego pueda generar las probabilidades de elegir la siguiente letra.

Mi pregunta:

En primer lugar, ¿cuál es la forma más eficiente para completar este proyecto? Mi solución parece ser muy rápida, pero realmente quiero quitarle los calcetines a mi profesor. (En mi último proyecto Una variación del problema de distancia de edición, hice un A *, un algoritmo genético, un BFS y recocido simulado, y sé que el problema es NP-Hard)

En segundo lugar, ¿cuál es el punto de esta tarea? En realidad, no parece estar relacionado con gran parte de lo que hemos cubierto en clase. ¿Qué se supone que debemos aprender?

Answer 1

Sobre la relevancia de esta tarea con lo que cubrió en la clase (Su segunda pregunta). La idea de una clase de 'estructuras de datos' es exponer a los estudiantes a las muchas estructuras que se encuentran frecuentemente en CS: listas, pilas, colas, hashes, árboles de varios tipos, gráficos en general, matrices de diversos credos y avaricia, etc. y para proporcionar una idea de sus implementaciones comunes, sus fortalezas y debilidades y, en general, sus diversos campos de aplicación.
Dado que la mayoría de los juegos/acertijos/problemas se pueden mapear a algún conjunto de estas estructuras, no hay falta de temas en los que basar las conferencias y tareas. Tu clase parece interesante porque si bien te estás enfocando en estas estructuras, también tienes la oportunidad de descubrir aplicaciones reales.
Por ejemplo, de una manera apenas disimulada, el asunto "gato y dos perros" es una introducción a los modelos estadísticos aplicados a la lingüística.Tu curiosidad y motivación te impulsaron a establecer una relación con los modelos de Markov y es algo bueno, porque es probable que te encuentres con "Markov" algunas veces más antes de graduarte ;-) y sin duda en una vida profesional en CS o en un dominio relacionado. Entonces, ¡sí! puede parecer que estás husmeando en muchas aplicaciones, etc., pero siempre que tengas una idea de qué estructuras y algoritmos seleccionar en situaciones particulares, ¡no estás perdiendo el tiempo!

Ahora, algunas pistas sobre posibles enfoques para la asignación
El trie parece como un apoyo natural para este tipo de problema. Sin embargo, tal vez pueda preguntarse cómo se escalaría este enfoque, si tuviera que indexar, diga todo un libro en lugar de esta breve oración. Parece mayormente lineal, aunque esto depende de cómo cada elección en los tres saltos en el trie (para esta cadena de Markov de segundo orden): a medida que aumenta el número de opciones, elegir un camino puede ser menos eficiente.
Un posible almacenamiento alternativo para la construcción del índice es stochatisc matriz (en realidad una matriz "simple" si solo dispersa, durante el proceso de recopilación de estadísticas, se volvió estocástica al final cuando normaliza cada fila -o columna- dependiendo en la configuración) para resumir en uno (100%). Tal matriz sería aproximadamente 729 x 28, y permitiría la indexación, en una sola operación, de una tupla de dos letras y su siguiente letra asociada. (Tengo 28 para incluir las señales de "inicio" y "detener", detalles ...)
El costo de esta indexación más eficiente es el uso de espacio adicional. Space-wise el trie es muy eficiente, solo almacena las combinaciones de trillizos de letras que existen, la matriz sin embargo desperdicia un poco de espacio (apuestes que al final estará muy poco poblada, incluso después de indexar mucho más texto que el " sentencia de perro/gato)
Este tamaño de en comparación con el compromiso de CPU es muy común, aunque algunos algoritmos/estructuras son a veces mejores que otros en ambos casos ... Además, el enfoque de matriz no se escalaría bien, tamaño-wize , si el problema se cambió para basar la selección de letras del mensaje anterior, tres caracteres.
No obstante, tal vez analice la matriz como una implementación alternativa. Está muy en el espíritu de esta clase para probar varias estructuras y ver por qué/dónde son mejores que otras (en el contexto de una tarea específica).
Un pequeño viaje lateral que puede realizar es crear un tag cloud basado en las probabilidades de los pares de letras (o trillizos): tanto el trie como la matriz contienen todos los datos necesarios para eso; la matriz con todas sus propiedades interesantes, puede ser más adecuada para esto.
¡Diviértete!

Answer 2

Utiliza el enfoque de bigram con los caracteres, pero por lo general se aplica a las palabras, porque la salida será más significativa si utilizamos un generador simple como en su caso).

1) Desde mi punto de vista te está yendo bien. Pero puede ser que usted debe intentar seleccionar un poco al azar el siguiente nodo? P.ej. seleccione el nodo aleatorio de 5 más alto. Quiero decir que si siempre seleccionas el nodo con mayor probabilidad, tu cadena de salida será demasiado uniforme.

2) He hecho exactamente la misma tarea en mi universidad. Creo que el punto es mostrarles a los estudiantes que las cadenas de Markov son poderosas pero sin un amplio estudio de la aplicación de dominio de salida del generador será ridículo