レイマンの用語でマルコフチェーンアルゴリズムを説明してください
質問
私はこのマルコフをよく理解していません...それはプレフィックスと接尾辞がそれらのリストを保存し、ランダムな単語を作成する2つの単語を取りますか?
/* 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);
}
}
解決
ウィキペディアによると、マルコフ連鎖は、次の状態が前の状態に依存しているランダムなプロセスです。これは少し理解するのが難しいので、私はそれをよりよく説明しようとします:
あなたが見ているものは、テキストベースのマルコフチェーンを生成するプログラムのようです。基本的にそのためのアルゴリズムは次のとおりです。
- テキストの本体をトークン(言葉、句読点)に分割します。
- 周波数テーブルを作成します。これは、テキストの本体のすべての単語に対して、エントリ(キー)があるデータ構造です。このキーは、基本的にこの単語(キー)に従うすべての単語のリストとその頻度のリストである別のデータ構造にマッピングされます。
- マルコフチェーンを生成します。これを行うには、開始点(周波数テーブルのキー)を選択し、次に別の状態をランダムに選択して(次の単語)に移動します。次に選択する単語は、その頻度に依存しています(したがって、一部の単語は他の単語よりも可能性があります)。その後、この新しい単語をキーとして使用して最初から使用します。
たとえば、このソリューションの最初の文を見ると、次の周波数表を思いつくことができます。
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で行うプログラムを書きました。あなたはそれについて読むことができます ここ.
他のヒント
マルコフチェーンは、状態遷移が確率である状態マシンです。
単語:鶏肉;可能な次の単語:10% - IS; 30% - 50% - 脚; 10% - 実行;
次に、次の単語をランダムに選択するか、ルーレットホイールの選択によって選択します。いくつかの入力テキストからこれらの確率を取得します。
所属していません StackOverflow