Spiegare algoritmo di Markov-chain in termini profani

Question

Io non capisco questo Markov ... ci vogliono due parole un prefisso e suffisso salva un elenco di loro e fa parola a caso?

    /* 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

Secondo Wikipedia, una catena di Markov è un processo casuale in cui lo stato successivo dipende dallo stato precedente. Questo è un po 'difficile da capire, quindi cercherò di spiegarlo meglio:

Quello che stai guardando, sembra essere un programma che genera una catena di Markov basato su testo. In sostanza l'algoritmo di ciò è la seguente:

1. Spalato un corpo di testo in token (parole, punteggiatura).
2. Crea una tabella di frequenza. Si tratta di una struttura di dati in cui per ogni parola nel corpo del testo, si dispone di una voce (chiave). Questa chiave viene mappato a un'altra struttura di dati che è fondamentalmente un elenco di tutte le parole che seguono questa parola (la chiave) insieme con la sua frequenza.
3. Genera la catena di Markov. Per fare questo, si seleziona un punto di partenza (una chiave dal vostro tavolo frequenza) e poi in modo casuale seleziona un altro Stato per andare (parola successiva). La parola successiva si sceglie, dipende dalla sua frequenza (così alcune parole sono più probabili di altri). Dopo di che, si utilizza questa nuova parola come chiave e ricominciare da capo.

Per esempio, se si guarda la primissima frase di questa soluzione, si può trovare con la seguente tabella delle frequenze:

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%)

In sostanza, il passaggio di stato da uno stato all'altro è basato probabilità. Nel caso di una catena di Markov basato su testo, la probabilità di transizione è basata sulla frequenza delle parole che seguono la parola selezionata. Così la parola selezionata rappresenta lo stato precedente e la tabella di frequenza o parole rappresenta le (possibili) stati successivi. Potete trovare lo stato successivo se si conosce lo stato precedente (che è l'unico modo si ottiene la tabella di frequenza a destra), quindi questo in sintonia con la definizione in cui lo stato successivo dipende dallo stato precedente.

Shameless plug - ho scritto un programma per fare proprio questo in Perl, qualche tempo fa. Si può leggere su di esso qui .

Answer 2

Catene di Markov sono macchine a stati con transizioni di stato essendo probabilità.

Parola: Pollo; possibili parole successive: il 10% - è; 30% - è stato; 50% - le gambe; 10% - corre;

poi si seleziona la parola successiva in modo casuale o da qualche selezione ruota della roulette. È possibile ottenere queste probabilità da qualche testo di input.