exorciser.ch

exorciser.ch

Webseiten-Werkzeuge

Sie befinden sich hier: exorciser.ch » Markow Algorithmen

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
markow:index [2017/03/30 14:31] – ↷ Links angepasst weil Seiten im Wiki verschoben wurden u313950markow:index [2024/03/03 22:36] (aktuell) – Tscherter, Vincent
Zeile 1: Zeile 1:
 +====== Markow Algorithmen ======
 +
 +===== 1 Einleitung =====
 +Das vom sowjetischen Mathematiker Andrei Markow entwickelte Verfahren zur symbolischen Datenverarbeitung verwendet als einziger Programmierbaustein Substitutionsregeln. Mit dem Verfahren lassen sich zahlreiche Probleme, z.B. die Konjugation und Deklination natürlicher Sprachen effizient lösen. Anders als im [[wpde>Markow-Algorithmus|Original]] verwenden wir eine mit [[c:mustersuche|regulären Ausdrücken]]((cf. http://www.danielfett.de/internet-und-opensource,artikel,regulaere-ausdruecke))erweitere Form. Das ermöglicht es mit weniger Code schon komplexere Aufgaben zu lösen.
 +
 +===== 2 Und so funktioniert es ... =====
 +
 +Ein  Markow-Algorithmus (MA) ist eine geordnete Menge von Substitutionsregeln. Die Regeln haben jeweils die folgende Form:
 +
 +<ebnf>{
 +Substitutionsregel = '/' Suchmuster '/' Ersetzungsmuster '/' [ Modifikator ] [ '!' ] .
 +}</ebnf>
 +
 +Auf dem zu verarbeitenden Eingangswort findet nach dem Starten des Programms eine Suche über das Suchmuster der ersten Regel statt. Ist dieses im Eingangswort enthalten, wird eine der Regel entsprechende Substitution durch das Ersetzungsmuster 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. Bei der Verwendung des Modifikators ''g'' werden alle gefundenen Muster geleichzeitig 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. Terminierende Regeln sind am ''!'' am Schluss zu erkennen. Wurde mittels einer nicht terminierenden Regel substituiert, so beginnt der gesamte Ablauf unter Berücksichtigung des geänderten Wortes erneut.
 +Kann keine passende Substitutionsregel gefunden werden, stoppt das Programm ebenfalls.
 +
 +== In anderen Worten ... ==
 +
 +Der Markow-Algorithmus wandelt einen vorgegebenen Text nach vorgegebenen Regeln um. Diese Regeln bestehen ausschliesslich aus Ersetzungsmustern. Beispielsweise schreibt man für die Anweisung, dass die Ziffernfolge '010' durch die Ziffernfolge '111' ersetzt werden soll, folgende Regel:
 +
 +  /010/111/
 +  
 +Ein Markow-Algorithmus kann natürlich aus vielen solchen Anweisungen bestehen. Diese werden dann nach folgendem Schema immer wieder durchgearbeitet, bis es nicht mehr weitergeht:
 +
 +  - Gehe alle Regeln der Reihe nach durch.
 +  - Wenn eine Regel irgendwo anwendbar ist, so führe sie an der linkesten Stelle aus, wo sie auf den Text zutrifft.
 +  - Starte danach von Neuem.
 +Einigen Regeln kann man mit einem Terminierungs-Symbol die Anweisung mitgeben, dass der Algorithmus, sobald er diese Regel ausführt, danach automatisch stoppt. Sie werden durch einen Ausrufezeichen versehen.
 +
 +  /010/111/ !
 +
 +==== 2.1 Marker ====
 +
 +Diese simplen Regeln reichen oft nicht für alle Probleme aus. Was noch hinzukommt sind Marker. Dies sind Buchstaben oder Symbole, die für die Ausführungsdauer in den Text eingearbeitet werden können, jedoch vor Terminierung wieder entfernt werden müssen. Meistens werden dafür die Buchstaben des griechisches Alphaets verwendet:
 +
 +<code text>α β γ δ ε ζ η θ ι κ λ μ ν ξ ο π ρ ς σ τ υ φ χ ψ ω ϑ ϒ ϖ</code>
 +
 +Das folgende Beispiel soll eine solche Anwendung illustrieren. Die folgenden Ersetzungsregeln bewirken, dass das linkeste ''0'' in einer Binärzahl ganz nach hinten verschoben wird:
 +
 +  ; Eingabe
 +  : <code>01010001111</code>
 +  ; Ausgabe
 +  : <code>10100011110</code>
 +  ; Algorithmus
 +  : <code>/π1/1π/
 +/π0/0π/
 +/π/0/ !
 +/0/π/ 
 +</code>
 +  ; Variante
 +  : Da die Substitutionsregeln als reguläre Ausdrucke interpretiert werden, hat man die Möglichkeit zahlreiche Probleme wie das obige, unter Verwendung von Gruppen, eleganter lösen. <code>/(0)(.*)/$2$1/ !</code>
 +
 +==== 2.2 Modifikatoren ===== 
 +Die Substitutionsregeln ''/Suchmuster/Ersetzungsmuster/'' lassen sich mit Modificatoren ergänzen. Siehe oben.
 +
 +  ; ''g''
 +  : wendet die Ersetzungsregel global an, also auf alle Textbausteine, die ersetzt werden
 +  ; ''m''
 +  : Mehrzeilenmodus. Im Mehrzeilenmodus bekommen ''^'' und ''$'' eine neue Bedeutung. ''^'' steht neue für Zeilenanfang und ''$'' steht neu für Zeilenende anstelle von Textanfang und -ende.
 +  ; ''i''
 +  : insensitiv gegenüber Gross- und Kleinschreibung
 +  
 +Das folgende Schema veranschaulich die Anwendung der Modifikatoren. Für weiterführende Informationen: siehe [[http://wiki.selfhtml.org/wiki/Referenz:JavaScript/RegExp#Modifikatoren|selfhtml.org]]
 +
 +<ebnf> {
 +
 +Modifikator = ['i'] [ 'g' ] [ 'm' ] .
 +
 +} </ebnf>
 +===== 3 Entwicklungsumgebung =====
 +
 +Unter [[http://exorciser.ch/dev/rema.html]] findest Du eine Arbeitsumgebung für erweiterte Markov Algorithmen.
 +
 +===== 4 Aufgaben =====
 +
 +  * [[seriea]]
 +  * [[serieb]]
 +  * [[seriec]]
  

Benutzer-Werkzeuge

Seiten-Werkzeuge

Webseiten-Werkzeuge