Patroon matching

Patroonherkenning (Engels voor patroonherkenning ) of patroonmatige search is een term voor verwerkingsprocedures symbool op basis van een vooraf bepaald patroon, het zoekscherm , discrete identificeren discrete structuur of structuren subsets.

Patroonvergelijking is bijvoorbeeld een methode voor fylogenetische analyse in de bioinformatica .

Basis

Een discrete structuur bestaat uit discrete elementen ( symbolen ) en relaties daartussen. Voorbeelden zijn strings , maar ook bomen of grafieken . Het zoekpatroon zelf is ook een discrete structuur, maar het kan een hele klasse structuren beschrijven door extra metatekens te gebruiken . In tegenstelling tot patroonherkenning , dat continue structuren interpreteert, werkt patroonherkenning vanaf het begin op een symbolische representatie.

Patroonherkenning speelt niet alleen een centrale rol bij het zoeken, maar ook bij de patroon- en regelgebaseerde transformatie van discrete structuren. In vervangings- of transformatiesystemen is patroonherkenning de eerste stap. Delen van het patroon worden geïdentificeerd met delen van de geanalyseerde structuur. De gevonden substructuren worden vervolgens gebruikt als parameters in de transformatiefunctie. Voorbeelden van dergelijke transformaties zijn tekstvervanging in tekenreeksen en grafiekvervangingssystemen .

toepassingsgebieden

programmeren

In sommige functionele of logische programmeertalen wordt patroonherkenning gebruikt om gegevens te verwerken op basis van de structuur (bijv. Scala , Objective CAML , ML , Haskell , Erlang , Opal )

Voorbeeld casusonderscheid: Een mogelijke definitie van het n-de Fibonacci-getal is:

Deze definitie kan rechtstreeks naar Haskell worden overgebracht met behulp van patroonherkenning . 

-- Matcht die ersten beiden Fälle
fib 0 = 0
fib 1 = 1
-- Alle anderen Zahlen n sind definiert als
fib n = fib(n-1) + fib(n-2)

Voorbeeld: In Haskell worden de argumenten in een functiedefinitie gekoppeld aan patronen. Een patroon kan, maar hoeft geen elementaire waarde te zijn (bijvoorbeeld 0), zoals in het vorige voorbeeld, maar kan ook een dataconstructor beschrijven. 

-- 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) = ...

Tekstverwerking

Patroonovereenkomst wordt ook gebruikt om tekst te manipuleren. In programmeertalen als Perl of awk en ook in de meeste teksteditors zijn er tools om in een tekst naar een patroon te zoeken. De patronen bestaan ​​uit reguliere expressies .

Zie ook

literatuur