Pattern Matching Task

A Pattern Matching Task is a search task that includes a pattern (a match pattern) as input and requires all matching items to be in a match relation with this pattern.

• Context:
  • Input:
    • an Entity, such as an Artifact, an Unordered Dataset, or a Sequential Dataset.
    • a Pattern, such as a Regular Expression, a Database Schema, or a Training Set.
    • optional: a Mismatch Threshold and a Distance Function.
  • output: One or more Identifiers, such as a Data Record Identifier.
  • It can be solved by a Matching System (that implements a Matching algorithm).
  • It can be:
    • an Exact Matching Task.
    • an Approximate Matching Task (a Detection Task).
• Example(s):
  • A String Matching Task, requires locating Substrings within a string that match a String Pattern.
  • A Tuple Matching Task, requires locating Tuples within a Tuple Set that match a Tuple Pattern.
  • A Graph Matching Task, requires locating Subgraphs within a Graph that match a Graph Pattern.
  • A Schema Object Matching Task, requires locating Schema Objects within a Schema Set that matches a Schema Object Pattern.
  • A Clinical Patient-Trial Matching Task.
  • …
• Counter-Example(s):
  • a Face Recognition Task.
  • an Entity Mention Detection Task.
  • an Optimization Task that requires the optimal solution given a Cost Function.
  • a Constraint Satisfaction Task that requires any solution within the given Constraint Set.
• See: Probabilistic Detection Task, Pattern Recognition Task, Data Mining, NLP.

---

---

References

2009a

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Pattern_matching
  • In computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. In contrast to pattern recognition, the pattern is rigidly specified. Such a pattern concerns conventionally either sequences or tree structures. Pattern matching is used to test whether things have a desired structure, to find relevant structure, to retrieve the aligning parts, and to substitute the matching part with something else. Sequence (or specifically text string) patterns are often described using regular expressions (i.e. backtracking) and matched using respective algorithms. Sequences can also be seen as trees branching for each element into the respective element and the rest of the sequence, or as trees that immediately branch into all elements.
  • Tree patterns can be used in programming languages as a general tool to process data based on its structure. Some functional programming languages such as Haskell, ML and the symbolic mathematics language Mathematica have a special syntax for expressing tree patterns and a language construct for conditional execution and value retrieval based on it. For simplicity and efficiency reasons, these tree patterns lack some features that are available in regular expressions. Depending on the languages, pattern matching can be used for function arguments, in case expressions, whenever new variables are bound, or in very limited situations such as only for sequences in assignment (in Python). Often it is possible to give alternative patterns that are tried one by one, which yields a powerful conditional programming construct. Pattern matching can benefit from guards.
  • Term rewriting and Graph rewriting languages rely on pattern matching for the fundamental way a program evaluates into a result. Pattern matching benefits most when the underlying datastructures are as simple and flexible as possible. This is especially the case in languages with a strong symbolic flavor. In homoiconic programming languages, patterns are the same kind of datatype as everything else, and can therefore be fed in as arguments to functions.

2009b

• (Wiktionary, 2009) ⇒ http://en.wiktionary.org/wiki/match
  • Verb
    • 1. (intransitive) To agree, to be equal.
    • 2. (transitive) To make a successful match or pairing. They found out about his color-blindness when he couldn't match socks properly.
    • 3. (transitive) To equal or exceed in achievement. She matched him at every turn. Anything he could do, she could do better.
  • Derived terms
    • mismatch

1996

• (Wall et al., 1996) ⇒ Larry Wall, Tom Christiansen, and Randal L. Schwartz. (1996). “Programming Perl, 2nd edition." O'Reilly. ISBN:1565921496
  • pattern matching: Taking a pattern, expressed as a regular expression, and trying the pattern various ways on a string to see if there's any way to make it fit. Often used to pick interesting tidbits out of a file.

---