Объясните алгоритм цепочки Маркова в Условиях Лэймана

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% - беги;

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