Mönstermatchning

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

Mönstermatchning (engelska för mönstermatchning) eller mönsterbaserad sökning är en term för symbolbehandlingsprocedurer baserade på ett förutbestämt mönster av diskreta strukturer eller delmängder identifierar en diskret struktur.

Mönstermatchning är till exempel en metod för fylogenetisk analys inom bioinformatik .

Grunderna

En diskret struktur består av diskreta element ( symboler ) och relationer mellan dem. Exempel är strängar , men också träd eller grafer . Själva sökmönstret är också en diskret struktur, men det kan beskriva en hel klass av strukturer med hjälp av ytterligare metatecken . Till skillnad från mönsterigenkänning , som tolkar kontinuerliga strukturer, fungerar mönstermatchning från början på en symbolisk representation.

Mönstermatchning spelar inte bara en central roll i sökningen, utan också i mönstret och regelbaserad transformation av diskreta strukturer. I ersättnings- eller transformationssystem är mönstermatchning det första steget. Delar av mönstret identifieras med delar av den analyserade strukturen. De hittade delstrukturerna används sedan som parametrar i transformationsfunktionen. Exempel på sådana transformationer är textbyte till teckensträngar och grafersättningssystem .

tillämpningsområden

programmering

I vissa funktionella eller logiska programmeringsspråk används mönstermatchning för att bearbeta data baserat på dess struktur (t.ex. Scala , Objective CAML , ML , Haskell , Erlang , Opal )

Exempel på fallskillnad: En möjlig definition av det n: e Fibonacci -talet är:

Denna definition kan överföras direkt till Haskell med hjälp av mönstermatchning.

 - Matcha de två första fallen
fib 0 = 0
fib 1 = 1
- Alla andra tal n definieras som
fib n = fib ( n - 1 ) + fib ( n - 2 )

Exempel: I Haskell matchas argumenten i en funktionsdefinition med mönster. Ett mönster kan, men behöver inte vara ett elementärt värde (t.ex. 0), som i föregående exempel, men kan också beskriva en datakonstruktör.

 - matchar den tomma listan (konstruktör [])
f [] = ...
- matchar alla listor med längd> 0 (konstruktör :), där x innehåller rubriken och xs resten av listan
f ( x : xs ) = ...

Ordbehandling

Mönstermatchning används också för att manipulera text. På programmeringsspråk som Perl eller awk och även i de flesta textredigerare finns det verktyg för att söka efter en text efter ett mönster. Mönstren består av regelbundna uttryck .

Se även

litteratur