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

Question

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

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

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

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

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

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

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

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

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

Answer 2

Марковские цепи - это автоматы с вероятностью переходов между состояниями.

Слово: Цыпленок; Возможны следующие слова: 10% - есть; 30% - было; 50% - ноги; 10% - бегает;

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