Expliquer l'algorithme de la chaîne de markov en termes simples
Je ne comprends pas bien ce Markov... il faut deux mots un préfixe et un suffixe enregistre une liste d'entre eux et fait un mot aléatoire?
/* 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);
}
}
2 réponses
Selon Wikipedia, une Chaîne de Markov est un processus aléatoire où l'état suivant dépend de l'état précédent. C'est un peu difficile à comprendre, alors je vais essayer de mieux l'expliquer:
Ce que vous regardez, semble être un programme qui génère une chaîne de Markov basée sur du texte. Essentiellement, l'algorithme pour cela est le suivant:
- diviser un corps de texte en jetons (mots, ponctuation).
- construire une table de fréquence. C'est une structure de données où chaque mot dans votre corps de texte, vous avez une entrée (clé). Cette clé est mappée à une autre structure de données qui est essentiellement une liste de tous les mots qui suivent ce mot (la clé) avec sa fréquence.
- Générer la chaîne de Markov. Pour ce faire, vous sélectionnez un point de départ (une clé de votre table de fréquence), puis vous sélectionnez au hasard un autre État pour aller à (le mot suivant). Le mot suivant que vous choisissez dépend de sa fréquence (certains mots sont donc plus probables que d'autres). Après cela, vous utilisez ce nouveau mot comme clé et recommencez.
Par exemple, si vous regardez la toute première phrase de cette solution, vous pouvez trouver le tableau de fréquence suivant:
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 sur la probabilité. Dans le cas d'une chaîne de Markov basée sur le 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 la table de fréquence ou les mots représentent les états successifs (possibles). Vous trouvez l'état successif si vous connaissez l'état précédent (c'est la seule façon d'obtenir la bonne table de fréquence), donc 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 ici.
Les chaînes de Markov sont des Machines D'État dont les transitions D'État sont des probabilités.
Mot: Poulet; mots suivants possibles: 10% - est; 30% - était; 50% - jambes; 10% - runs;
Ensuite, vous choisissez simplement le mot suivant au hasard ou par une sélection de roue de roulette. Vous obtenez ces probabilités à partir d'un texte d'entrée.