Pattern Matching

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Pattern Matching (englisch für Musterabgleich) oder musterbasierte Suche ist ein Begriff für symbolverarbeitende Verfahren, die anhand eines vorgegebenen Musters diskrete Strukturen oder Teilmengen einer diskreten Struktur identifizieren.

Grundlagen[Bearbeiten]

Eine diskrete Struktur besteht aus diskreten Elementen (Symbolen) und Beziehungen zwischen diesen. Beispiele sind Zeichenketten, aber auch Bäume oder Graphen. Das Suchmuster selbst ist ebenfalls eine diskrete Struktur, die aber durch Verwendung zusätzlicher Metazeichen eine ganze Klasse von Strukturen beschreiben kann. Im Gegensatz zur Mustererkennung, die kontinuierliche Strukturen interpretiert, operiert das Pattern Matching von vornherein auf einer symbolischen Repräsentation.

Das Pattern Matching spielt jedoch nicht nur bei der Suche, sondern auch bei der muster- und regelbasierten Transformation diskreter Strukturen eine zentrale Rolle. In Ersetzungs - oder Transformationssystemen bildet das Pattern Matching den ersten Schritt. Dabei werden Teile des Musters mit Teilen der analysierten Struktur identifiziert. Die gefundenen Teil-Strukturen gehen dann als Parameter in die Transformationsfunktion ein. Beispiele für solche Transformationen sind Textersetzung in Zeichenketten und Graphersetzungssysteme.

Anwendungsgebiete[Bearbeiten]

Programmierung[Bearbeiten]

In einigen funktionalen oder logischen Programmiersprachen wird es genutzt, um Daten anhand ihrer Struktur zu verarbeiten.(z. B.: Scala, Objective CAML, ML, Haskell, Erlang)

Beispiel: In der funktionalen Programmiersprache Haskell werden die Argumente in einer Funktionsdefinition mit Pattern gematcht. Ein Pattern kann entweder jeden Wert eines Datentyps, einen elementaren Wert oder einen Daten-Konstruktor beschreiben.

-- matcht die leere Liste (Konstruktor [])
f []     = ...
-- matcht alle Listen der Länge > 0 (Konstruktor :), wobei x den Kopf und xs den Listenrest enthält
f (x:xs) = ...

Textverarbeitung[Bearbeiten]

Es wird auch verwendet, um Text zu bearbeiten. In Programmiersprachen wie Perl oder awk und auch in den meisten Texteditoren existieren Werkzeuge, um einen Text nach einem Muster zu durchsuchen. Die Muster bestehen aus regulären Ausdrücken. siehe String-Matching-Algorithmus

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]