用外行人的术语解释马尔可夫链算法

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% - 跑步;

然后你只需随机选择下一个单词或选择一些轮盘赌轮.您可以从某些输入文本中获取这些概率.