Erklären markov-Kette Algorithmus in juristischer Hinsicht

Question

Ich verstehe nicht ganz diese Markov verstehen ... es dauert zwei Wörter ein Präfix und Suffix speichert eine Liste von ihnen und macht Zufallswort?

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

Laut Wikipedia eine Markov-Kette ist ein statistisches Verfahren, bei dem der nächste Zustand auf dem vorherigen Zustand abhängt. Dies ist ein wenig schwer zu verstehen, also werde ich versuchen, es besser zu erklären:

Was Sie betrachten, scheint ein Programm, das eine textbasierte Markov Chain erzeugt. Im Wesentlichen für den Algorithmus, ist wie folgt:

1. Split ein Textkörper in Tokens (Wörter, Satzzeichen).
2. Erstellen Sie eine Frequenztabelle. Dies ist eine Datenstruktur, in der für jedes Wort in Ihrem Körper von Text, können Sie einen Eintrag (Schlüssel). Dieser Schlüssel wird auf eine andere Datenstruktur abgebildet, die im Grunde eine Liste aller Wörter, die dieses Wort (der Schlüssel) zusammen mit seiner Frequenz folgen.
3. Generieren Sie die Markov-Kette. Dazu wählen Sie einen Startpunkt (ein Schlüssel aus der Frequenztabelle) und wählen Sie dann zufällig einen anderen Zustand zu gehen (das nächste Wort). Das nächste Wort, das Sie wählen, ist abhängig von ihrer Frequenz (so einige Worte als andere wahrscheinlicher sind). Danach verwenden Sie dieses neue Wort als Schlüssel und von vorn beginnen.

Zum Beispiel, wenn Sie auf dem ersten Satz dieser Lösung suchen, können Sie mit der folgenden Frequenztabelle kommen:

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

Wesentlichen der Zustandsübergang von einem Zustand zu einem anderen ist Wahrscheinlichkeit basiert. Im Fall einer textbasierten Markov-Kette, wird die Übergangswahrscheinlichkeit auf der Frequenz von Worten nach dem ausgewählten Wort basiert. So stellt das ausgewählte Wort den vorherigen Zustand und die Häufigkeitstabelle oder Worte darstellen, die (möglichen) aufeinanderfolgenden Zuständen. Sie finden den aufeinanderfolgenden Zustand, wenn Sie den vorherigen Zustand kennen (das ist der einzige Weg Sie die richtige Frequenztabelle erhalten), so dass diese Anfälle in der Definition, wo der aufeinanderfolgenden Zustand auf dem vorherigen Zustand abhängig ist.

Shameless Stecker - Ich schrieb ein Programm nur dieses in Perl zu tun, vor einiger Zeit. Sie können es lesen zu hier .

Answer 2

Markov-Ketten sind State Machines mit Zustandsübergängen Wahrscheinlichkeiten zu sein.

Wort: Huhn; mögliche nächste Worte: 10% - ist; 30% - war; 50% - Beine; 10% - läuft;

dann wählen Sie einfach das nächste Wort zufällig oder durch eine Roulette-Rad Auswahl. Sie erhalten diese Wahrscheinlichkeiten von einem Eingabetext.