Markov-Algorithmus


Markov-Algorithmus

Der vom sowjetischen Mathematiker Andrei Markow entwickelte Markow–Algorithmus stellt einen wichtigen Ansatz zur Formalisierung des Algorithmusbegriffs dar. Besonders Aufgaben der symbolischen Datenverarbeitung, beispielsweise die Konjugation und Deklination natürlicher Sprachen, lassen sich mit seiner Hilfe sehr effizient lösen.

Inhaltsverzeichnis

Definition

Informelle Beschreibung

Der Markow–Algorithmus betrachtet die Eingabedaten eines Algorithmus als Wörter oder Sätze, aus denen durch Übersetzung ein Ergebnis ermittelt werden kann. Das Lösungsprinzip beruht also ausschließlich auf der Substitution von Zeichenketten. Weitere Operationen stehen nicht zur Verfügung. Analog zur Turingmaschine wird eine Symbolkette als grundlegende Datenstruktur verwendet. Obwohl Produktivsysteme meist eine nichtdeterministische Verarbeitung solcher Symbolketten vornehmen, lässt sich durch spezielle Einschränkungen ein deterministisches Verhalten erreichen:

  • Können mehrere Regeln angewendet werden, muss die Anwendungsreihenfolge immer eindeutig festgelegt sein
  • Ist eine Regelanwendung an mehreren Positionen des Ausgangsworts möglich, muss stets eine Priorität definiert sein

Der Markow–Algorithmus erfüllt die Anforderungen an einen solchen deterministischen Wortkalkül. Mit Mitteln der Berechenbarkeitstheorie kann man beweisen, dass Markow-Algorithmen genauso mächtig sind wie beliebige andere Algorithmen, Turingmaschinen oder µ–rekursive Funktionen.

Formale Definition

Markow-Algorithmus und natürlicher Algorithmus stellen Semi-Thue-Systeme dar, deren Regeln eine geordnete Menge bilden, die wiederum in folgende disjunkte Teilmengen zerfällt:

  • terminierende Regeln
  • nicht terminierende Regeln

Unter folgenden Voraussetzungen ist bei einem Markow-Algorithmus das Wort Q aus dem Wort P durch eine Regel R direkt ableitbar:

  • P wurde durch eine nicht terminierende Regel erzeugt
  • R ist die erste auf P anwendbare Regel
  • Q wird durch Anwendung von R auf das am weitesten links zu findende Teilwort von R in P erzeugt

Die Arbeit des Markow-Algorithmus bricht bei dem Wort ab, das durch eine terminierende Regel erzeugt wurde oder auf das keine weitere Regel anwendbar ist. Im Unterschied zum Post-Kalkül wird stets nur auf den passenden Teilen des Wortes operiert. Die Substitution eines Wortpaares (P, Q) bildet die Grundlage des Markow-Algorithmus:

  • Ein gegebenes Ausgangswort wird auf das erste Enthaltensein des Wortes P durchsucht
  • Kann P gefunden werden, wird es durch das Wort Q ersetzt

Es existieren folgende Spezialfälle der Substitution:

  • \varepsilon \Rightarrow Q
    Das leere Wort wird durch ein Wort Q ersetzt
  • P \Rightarrow \varepsilon
    Ein Wort P wird durch das leere Wort ersetzt
  • \varepsilon \Rightarrow \varepsilon
    Das leere Wort wird durch sich selbst ersetzt

Die zu verarbeitenden Wörter werden aus einem Alphabet A gebildet. Linke und rechte Teile der Regeln eines Markow-Algorithmus stellen Wörter des Alphabets A dar. Folgende Metazeichen dürfen nicht im Alphabet enthalten sein:

  • \Rightarrow wird als Substitutionsoperator verwendet
  • . kennzeichnet terminierende Regeln

Arbeitsweise

Flussdiagramm

Markow–Algorithmus als Flussdiagramm

Auf dem zu verarbeitenden Eingangswort findet eine Suche über das linke Wort der ersten Regel statt. Ist dieses im Eingangswort enthalten, wird eine der Regel entsprechende Substitution ausgelöst. Das Eingangswort wird von links nach rechts durchsucht. Somit wird bei einem Mehrfachvorkommen des linken Wortes der Regel stets das am weitesten links stehende Vorkommen substituiert.

Ist die oben beschriebene Suche erfolglos, wird zur nächsten Regel übergegangen. Kann unter Einbeziehung aller weiteren Regeln keine Substitution vorgenommen werden, so ist der Algorithmus beendet. Auch die Anwendung einer terminierenden Regel führt zu dessen Beendigung. Wurde mittels einer nicht terminierenden Regel substituiert, so beginnt der gesamte Ablauf unter Berücksichtigung des geänderten Wortes erneut.

Einfaches Fallbeispiel

Nach den Erläuterungen zu oben gezeigtem Flussdiagramm, soll hier noch ein simples Fallbeispiel die Erklärungen zur Arbeitsweise ergänzen. Besonders die Reihenfolge der Regelanwendung und die daraus resultierenden Ergebnisse werden im Folgenden gut verdeutlicht. Das im Beispiel verwendete Eingabewort lautet:

I_I_I_I_

Darüber hinaus seien folgende Regeln definiert:

01 I->A
02 _->B
03 AB->_B
04 BBBBBBBB->I_I_I_I_

Es ergeben sich folgende Substitutionen, die Nummer der angewendeten Regel wurde vorangestellt:

01 A_I_I_I_
01 A_A_I_I_
01 A_A_A_I_
01 A_A_A_A_
02 ABA_A_A_
02 ABABA_A_
02 ABABABA_
02 ABABABAB
03 _BABABAB
02 BBABABAB
03 BB_BABAB
02 BBBBABAB
03 BBBB_BAB
02 BBBBBBAB
03 BBBBBB_B
02 BBBBBBBB
04 I_I_I_I_

Anwendungsbeispiele

Inkrementation und Addition

Die Zahlendarstellung im Dezimalsystem ist für die Lösung des Problems nicht optimal. Verwendet man jedoch einen einfachen Unärkode, so besteht der Algorithmus zur Inkrementation bzw. Addition jeweils aus nur einer einzigen Regel.

Darstellung:

die Kodierung erfolgt in Form von 1 = I, 2 = II, 3 = III etc.

die Addition 1 + 0 + 2 + 4 wird beispielsweise als I++II+IIII kodiert

Es ergibt sich folgende Lösung:

\varepsilon \Rightarrow .I
Inkrementation
+ \Rightarrow \epsilon
Addition

Erkennung korrekter Klammerausdrücke

Der Schlüssel zur Lösung dieses Problems liegt im Auffinden und Streichen zusammengehöriger Klammerpaare. Gestrichene Klammern verschwinden und ihr Platz wird von den angrenzenden Zeichen eingenommen. Nun sind die Klammern der folgenden Paare direkt benachbart und können wiederum leicht aufgefunden werden. Für unser Beispiel wird angenommen, dass der Klammerausdruck beidseitig durch das Zeichen '$' eingegrenzt ist.

Es ergibt sich folgende Lösung:

()  \Rightarrow \varepsilon
Löschen eines Klammerpaares
$$  \Rightarrow $.1$
Alle Paare gelöscht, Ergebnis ist 1
(  \Rightarrow 0
Löschen der Restklammern
)  \Rightarrow 0
Löschen der Restklammern
00  \Rightarrow 0
Löschen aller überzähligen Nullen

Die aufgezeigte Form zur Lösung der Aufgabe ist denkbar einfach und verständlich. Der Markow-Algorithmus bietet hier ein der Problemstellung gut angepasstes Lösungsprinzip.

Siehe auch

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lempel-Ziv-Markov-Algorithmus — Lempel Ziv Markow Algorithmus (LZMA) ist ein freier Datenkompressionsalgorithmus, der von Igor Pavlov seit 1998 entwickelt wird und vergleichsweise gute Kompressionsraten und eine hohe Geschwindigkeit beim Entpacken erreicht. Er ist benannt nach… …   Deutsch Wikipedia

  • Markov Chain Monte Carlo — Verfahren (kurz MCMC Verfahren; seltener auch Markov Ketten Monte Carlo Verfahren) sind eine Klasse von Algorithmen, die Stichproben aus Wahrscheinlichkeitsverteilungen ziehen. Dies geschieht auf der Basis der Konstruktion einer Markow Kette,… …   Deutsch Wikipedia

  • Markov-Chain — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Markov-Eigenschaft — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Markov-Kette — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Markov-Ketten — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Markov-Prozess — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Markov Chain — Eine Markow Kette (engl. Markov chain, auch Markow Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov Kette, Markoff Kette) ist eine spezielle Klasse von stochastischen Prozessen. Man unterscheidet eine Markow Kette in… …   Deutsch Wikipedia

  • Hidden-Markov-Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Hidden Markov Modell — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia