Pattern matching
Pattern Matching (English for pattern matching ) or pattern-based search is a term for symbol processing procedures based on a predetermined pattern, the search mask , discrete identify a discrete structure or structures subsets.
Pattern matching is, for example, a method of phylogenetic analysis in bioinformatics .
Basics
A discrete structure consists of discrete elements ( symbols ) and relationships between them. Examples are strings , but also trees or graphs . The search pattern itself is also a discrete structure, but it can describe a whole class of structures by using additional metacharacters . In contrast to pattern recognition , which interprets continuous structures, pattern matching operates from the outset on a symbolic representation.
Pattern matching does not only play a central role in the search, but also in the pattern and rule-based transformation of discrete structures. Pattern matching is the first step in replacement or transformation systems . Parts of the pattern are identified with parts of the analyzed structure. The sub-structures found are then used as parameters in the transformation function. Examples of such transformations are text replacement into character strings and graph replacement systems .
application areas
programming
In some functional or logical programming languages, pattern matching is used to process data based on its structure (e.g. Scala , Objective CAML , ML , Haskell , Erlang , Opal )
Example case distinction: A possible definition of the nth Fibonacci number is:
This definition can be transferred directly to Haskell with the help of pattern matching .
-- 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)
Example: In Haskell, the arguments in a function definition are matched with patterns. A pattern can, but does not have to be an elementary value (e.g. 0), as in the previous example, but can also describe a data constructor.
-- 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) = ...
Word processing
Pattern matching is also used to manipulate text. In programming languages such as Perl or awk and also in most text editors there are tools to search a text for a pattern. The patterns consist of regular expressions .
See also
- Search procedure
- Pattern analysis
- Levenshtein distance
- Gestalt Pattern Matching
- Fuzzy search
- Phonetic search
literature
- Simon Peyton Jones (Ed.): Haskell 98 Language and Libraries: The Revised Report . Cambridge University Press, 2003, ISBN 0-521-82614-4 ( HTML version - Section 3.17, HTML version ).
- Richard Bird: Introduction to Functional Programming using Haskell . 2nd Edition. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 .