Объясните алгоритм марковской цепи в условиях неспециалиста

Я не совсем понимаю этот марков... он принимает два слова префикс, а суффикс сохраняет список из них и делает случайное слово?

    /* 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);
    }
}

Ответы

Ответ 1

Согласно Википедии, Марковская цепь - это случайный процесс, в котором следующее состояние зависит от предыдущего состояния. Это немного сложно понять, поэтому я попытаюсь объяснить это лучше:

То, что вы смотрите, похоже, представляет собой программу, которая генерирует текстовую цепочку Маркова. По сути, для этого алгоритм выглядит следующим образом:

  • Разделить текст текста на токены (слова, знаки препинания).
  • Создайте частотную таблицу. Это структура данных, где для каждого слова в тексте вашего тела у вас есть запись (ключ). Этот ключ сопоставляется с другой структурой данных, которая в основном представляет собой список всех слов, следующих за этим словом (ключ) вместе с его частотой.
  • Генерировать цепь Маркова. Для этого вы выбираете начальную точку (ключ из вашей частотной таблицы), а затем вы произвольно выбираете другое состояние для перехода к следующему слову. Следующее слово, которое вы выберете, зависит от его частоты (поэтому некоторые слова более вероятны, чем другие). После этого вы используете это новое слово в качестве ключа и начинаете.

Например, если вы посмотрите на первое предложение этого решения, вы можете найти следующую частотную таблицу:

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

По существу, переход состояния из одного состояния в другое зависит от вероятности. В случае текстовой Марковской цепи вероятность перехода основана на частоте слов, следующих за выбранным словом. Таким образом, выбранное слово представляет предыдущее состояние, а таблица частот или слова представляют (возможные) последовательные состояния. Вы находите следующее состояние, если знаете предыдущее состояние (это единственный способ получить правильную частотную таблицу), поэтому это соответствует определению, в котором последующее состояние зависит от предыдущего состояния.

Shameless Plug. Я написал программу, чтобы сделать это только в Perl, некоторое время назад. Вы можете прочитать об этом здесь.

Ответ 2

Марковские цепочки являются государственными машинами с вероятностями состояний.

Слово: курица; возможно следующий Words: 10% - is; 30% - было; 50% - ноги; 10% - работает;

то вы просто выбираете следующее слово случайным образом или с помощью выбора колеса рулетки. Вы получаете эти вероятности из некоторого входного текста.