Expliquer l'algorithme de la chaîne en markov termes simples

Question

Je ne comprends pas tout à fait ce Markov ... il faut deux mots un préfixe et suffixe enregistre une liste d'entre eux et fait mot au hasard?

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

Selon Wikipedia, une chaîne de Markov est un processus aléatoire où l'état suivant dépend de l'état précédent. Ceci est un peu difficile à comprendre, donc je vais essayer de l'expliquer mieux:

Qu'est-ce que vous cherchez à, semble être un programme qui génère une chaîne de Markov à base de texte. Essentiellement, l'algorithme qui est la suivante:

1. Diviser un corps de texte en jetons (mots, ponctuation).
2. Construire une table de fréquence. Ceci est une structure de données où pour chaque mot dans votre corps de texte, vous avez une entrée (clé). Cette clé est associée à une autre structure de données qui est essentiellement une liste de tous les mots qui suivent ce mot (la clé) ainsi que sa fréquence.
3. Générer la chaîne de Markov. Pour ce faire, vous sélectionnez un point de départ (une touche de votre table de fréquence), puis vous sélectionnez au hasard un autre Etat pour aller à (le mot suivant). Le mot suivant vous choisissez, dépend de sa fréquence (si certains mots sont plus probables que d'autres). Après cela, vous utilisez ce nouveau mot comme la clé et recommencer.

Par exemple, si vous regardez la première phrase de cette solution, vous pouvez venir à la table de fréquences suivantes:

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

Essentiellement, la transition d'état d'un état à un autre est basée probabilité. Dans le cas d'une chaîne de Markov à base de texte, la probabilité de transition est basée sur la fréquence des mots suivant le mot sélectionné. Ainsi, le mot sélectionné représente l'état précédent et le tableau de fréquences ou des mots représente les (possibles) états successifs. Vous trouvez l'état successif si vous connaissez l'état précédent (qui est la seule façon que vous obtenez le tableau de fréquences à droite), de sorte que cela correspond à la définition où l'état successif dépend de l'état précédent.

Shameless plug - J'ai écrit un programme pour faire exactement cela en Perl, il y a quelque temps. Vous pouvez lire à ce sujet .

Answer 2

Chaînes de Markov sont des machines d'Etat avec des transitions État étant des probabilités.

Mot: Poulet; possibles mots suivants: 10% - est; 30% - était; 50% - jambes; 10% - runs;

alors que vous choisissez simplement le mot suivant au hasard ou par une sélection de roue de roulette. Vous obtenez ces probabilités d'un texte d'entrée.