Explicar el algoritmo de cadena de Markov en términos sencillos

Question

No entiendo muy bien este Markov ... toma dos palabras un prefijo y sufijo guarda una lista de ellos y hace palabra al azar?

    /* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */

#include <time.h>
#include <iostream>
#include <string>
#include <deque>
#include <map>
#include <vector>

using namespace std;

const int  NPREF = 2;
const char NONWORD[] = "\n";    // cannot appear as real line: we remove newlines
const int  MAXGEN = 10000; // maximum words generated

typedef deque<string> Prefix;

map<Prefix, vector<string> > statetab; // prefix -> suffixes

void        build(Prefix&, istream&);
void        generate(int nwords);
void        add(Prefix&, const string&);

// markov main: markov-chain random text generation
int main(void)
{
    int nwords = MAXGEN;
    Prefix prefix;  // current input prefix

    srand(time(NULL));
    for (int i = 0; i < NPREF; i++)
        add(prefix, NONWORD);
    build(prefix, cin);
    add(prefix, NONWORD);
    generate(nwords);
    return 0;
}

// build: read input words, build state table
void build(Prefix& prefix, istream& in)
{
    string buf;

    while (in >> buf)
        add(prefix, buf);
}

// add: add word to suffix deque, update prefix
void add(Prefix& prefix, const string& s)
{
    if (prefix.size() == NPREF) {
        statetab[prefix].push_back(s);
        prefix.pop_front();
    }
    prefix.push_back(s);
}

// generate: produce output, one word per line
void generate(int nwords)
{
    Prefix prefix;
    int i;

    for (i = 0; i < NPREF; i++)
        add(prefix, NONWORD);
    for (i = 0; i < nwords; i++) {
        vector<string>& suf = statetab[prefix];
        const string& w = suf[rand() % suf.size()];
        if (w == NONWORD)
            break;
        cout << w << "\n";
        prefix.pop_front(); // advance
        prefix.push_back(w);
    }
}

Answer 1

De acuerdo a Wikipedia, una cadena de Markov es un proceso aleatorio, donde el siguiente estado depende del estado previo. Esto es un poco difícil de entender, por lo que voy a tratar de explicarlo mejor:

Lo que está viendo, parece ser un programa que genera una cadena de Markov basado en texto. Esencialmente, el algoritmo para la que es como sigue:

1. Dividir un cuerpo de texto en tokens (palabras, signos de puntuación).
2. Construir una tabla de frecuencias. Se trata de una estructura de datos donde por cada palabra en el cuerpo del texto, tiene una entrada (clave). Esta tecla está asignada a otra estructura de datos que es básicamente una lista de todas las palabras que siguen a esta palabra (la clave), junto con su frecuencia.
3. Generar la cadena de Markov. Para ello, se selecciona un punto de partida (una clave de su tabla de frecuencias) y luego selecciona al azar otro estado para ir a (la siguiente palabra). La siguiente palabra que elija, depende de su frecuencia (por lo que algunas palabras son más probables que otras). Después de eso, se utiliza esta palabra nueva como la clave y empezar de nuevo.

Por ejemplo, si nos fijamos en la primera frase de esta solución, se puede llegar a la siguiente tabla de frecuencias:

According: to(100%)
to:        Wikipedia(100%)
Wikipedia: ,(100%)
a:         Markov(50%), random(50%)
Markov:    Chain(100%)
Chain:     is(100%)
is:        a(33%), dependent(33%), ...(33%)
random:    process(100%)
process:   with(100%)
.
.
.
better:    :(100%)

Esencialmente, la transición de estado de un estado a otro es probabilidad basada. En el caso de una cadena de Markov basado en texto, la probabilidad de transición se basa en la frecuencia de palabras después de la palabra seleccionada. Así que la palabra seleccionada representa el estado anterior y la tabla de frecuencias o las palabras representa las (posibles) estados sucesivos. A encontrar el estado sucesivo si se conoce el estado anterior (que es la única manera de obtener la tabla de frecuencias derecha), por lo que esto encaja con la definición que el estado sucesivo depende del estado anterior.

Shameless Plug - Me escribió un programa para hacer precisamente esto en Perl, hace algún tiempo. Usted puede leer sobre él aquí .

Answer 2

Cadenas de Markov son máquinas de estado con transiciones de estado siendo probabilidades.

Palabra: Pollo; palabras posibles siguientes: 10% - es; 30% - era; 50% - las piernas; 10% - carreras;

A continuación, sólo tiene que elegir la siguiente palabra al azar o por alguna selección ruleta. Se obtiene estas probabilidades de un texto de entrada.