اشرح خوارزمية سلسلة Markov بعبارات Layman

Question

أنا لا أفهم تمامًا هذا Markov ... يستغرق كلمتين بادئة وينقذ اللاحقة قائمة منها ويجعل كلمة عشوائية؟

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

وفقًا لـ Wikipedia ، فإن سلسلة Markov هي عملية عشوائية حيث تعتمد الدولة التالية على الحالة السابقة. هذا صعب بعض الشيء ، لذلك سأحاول شرحه بشكل أفضل:

ما تبحث عنه ، يبدو أنه برنامج يولد سلسلة ماركوف القائمة على النص. في الأساس خوارزمية ذلك كما يلي:

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

في الأساس ، فإن انتقال الحالة من ولاية إلى أخرى يعتمد على الاحتمال. في حالة سلسلة Markov المستندة إلى النص ، يعتمد احتمال الانتقال على تواتر الكلمات التي تتبع الكلمة المحددة. وبالتالي فإن الكلمة المحددة تمثل الحالة السابقة ويمثل جدول التردد أو الكلمات الحالات المتتالية (الممكنة). تجد الحالة المتتالية إذا كنت تعرف الحالة السابقة (هذه هي الطريقة الوحيدة التي تحصل بها على جدول الترددات الصحيحة) ، لذلك فإن هذا يتناسب مع التعريف الذي تعتمد عليه الحالة المتعاقبة على الحالة السابقة.

قابس وقح - كتبت برنامجًا للقيام بذلك فقط في بيرل ، منذ بعض الوقت. يمكنك أن تقرأ عنها هنا.

Answer 2

سلاسل ماركوف هي آلات دولة مع انتقالات الدولة كونها احتمالات.

الكلمة: الدجاج. الكلمات التالية ممكنة: 10 ٪ - هو ؛ 30 ٪ - كان ؛ 50 ٪ - أرجل ؛ 10 ٪ - يدير.

ثم يمكنك ببساطة اختيار الكلمة التالية بشكل عشوائي أو ببعض اختيار عجلة الروليت. يمكنك الحصول على هذه الاحتمالات من بعض نص الإدخال.