用通俗易懂的语言解释马尔科夫链算法

Question

用通俗易懂的语言解释马尔科夫链算法

24

我不太理解这个马尔可夫链... 它需要两个词作为前缀和后缀，保存成列表，然后生成随机单词？

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

- It's Just a Printer Driver

2个回答

5

马尔可夫链是具有状态转移概率的状态机。

单词：鸡；可能的下一个词：10％ - 是；30％ - 过去式was；50％ - 腿；10％ - 跑。

然后你可以随机选择或使用轮盘赌选取下一个单词。你可以从一些输入文本中获得这些概率。

- TechEffigy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vivin Paliath · Accepted Answer

据维基百科所述，马尔可夫链是一个随机过程，其中下一个状态依赖于前一个状态。这可能有些难以理解，所以我将尽力更好地解释：

你看到的似乎是一个生成基于文本的马尔可夫链的程序。基本上，该算法如下：

将一段文本分割成标记（单词、标点符号）。
构建频率表。这是一种数据结构，对于文本中的每个单词，都有一个条目（键）。这个键被映射到另一个数据结构，基本上是一个列表，其中包含跟随此单词（键）的所有单词及其频率。
生成马尔可夫链。要做到这一点，首先选择一个起始点（频率表中的一个键），然后随机选择另一个状态（下一个单词）。所选择的下一个单词取决于其出现的频率（因此某些单词比其他单词更有可能）。之后，使用这个新单词作为键并重新开始。

例如，如果您查看此解决方案的第一句话，可以得出以下频率表：

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编写了一个程序来实现这一点。你可以在这里阅读相关信息。