Topic: pattern matching

topics > computer science > programming > Group: patterns

sequence operations

access by pattern matching
approximate string matching and pattern matching with errors
function syntax by pattern
pattern brackets
pattern components
search algorithms
sequence generators
spelling errors
string operations
string transformation languages
structure transformation languages
suffix trie and suffix array
syntax analysis


A pattern matcher determines whether or not a pattern matches a sequence or sub-sequence. It may try many patterns over many sub-sequences or use patterns to delimitate new subsequences for matching. Typically, matching is left to right and from most specific pattern to most general. A pattern may find partial matches or determine the best or closest match. A carefully designed pattern database makes such searches feasible. In syntax analysis, pattern matching can be implemented by traversing a state tree which continually reduces the number of possibilities. (cbb 5/80)
Subtopic: substring match up

Quote: Boyer and Moore's string matching algorithm is more efficient than Knuth et al and Karp and Rabin [»daviG6_1986]
Quote: computing hash values slows down Karp and Rabin's string matching algorithm [»daviG6_1986]
Quote: using a pattern shift table, can search for substrings faster than the Boyer-Moore algorithm [»sundDM8_1990]
Quote: average case for 2 string matching algorithms, Boyer-Moore-Horspool faster than hardware character match for most pattern lengths [»baezRA8_1989]
Quote: simple code for an efficient version of Boyer-Moore-Horspool string matching algorithm [»baezRA8_1989]
Quote: fast string searching by variants of Boyer-Moore; toolkit for skip loop, match and shift components [»humeA11_1991]
Quote: Boyer-Moore string matching requires roughly 3n comparisons and less than 4n comparisons [»coleR10_1994]
Quote: adaptive, cycle method first compares the mismatched character from the last checking operation; circular pattern; faster than Sunday's and Smith's algorithms [»liuZ2_1998]

Subtopic: preprocessed match up

Quote: faster string matching by partitioning text into segments of the pattern length; search by hashing; requires linked lists and more memory [»kimS_1999]
Quote: with suffix trie, search time independent of text length [»nelsMR8_1996]

Subtopic: regular expression up

Quote: any finite automaton is a regular set -- closed under disjunction, product, and repetition [»kleeSC_1956]
Quote: the leftmost longest match rule does not work for regular expressions in structured text [»clarCL5_1997]
Quote: use the leftmost shortest match rule for regular expressions in structured text without predefined retrieval units [»clarCL5_1997]
Quote: sublinear search algorithm for regular expressions on preprocessed text; uses a Patricia tree for the index [»baezRA11_1996]
Quote: skip text runs during regular expression searching by recognizing shorter, reverse prefixes; performance similar to DFA [»navaG7_1999]
Quote: grep pattern matching by suffix array of vocabulary or by inverted index of digrams or trigrams [»zobeJ7_2006]

Subtopic: fingerprint match up

Quote: test equality of arbitrary byte sequences by testing their 128-bit fingerprints

Subtopic: partial match up

Quote: instead of failing a partial match query, may want the closest record [»linWC3_1979]
Quote: the same methods used for partial match query, group similar records into clusters [»linWC3_1979]
Quote: handle partial match queries by a permuted dictionary where each word appears in all possible rotations [»wittIH_1991]

Subtopic: data structure matching up

Quote: like pattern matching in a string, traverse data structures with directives [»hallJC5_1974]
QuoteRef: earlJ4_1974 ;;38 pattern matching on sequences and structures-- but nothing special
QuoteRef: sammJE_1969 ;;587 f==P if form f represented by pattern P, f>>P if P represents a subexpression of the form f

Subtopic: abstract tree matching up

Quote: use abstract tree matching to check the parse tree of a use pattern

Subtopic: event log matching up

Quote: PQL queries match a context-sensitive pattern of events; subqueries match context-free grammars over the call chain; the partial-order operator matches the intersection of context-free languages [»martM10_2005]

Subtopic: dynamic match up

Quote: a PQL query is a pattern to be matched on the execution trace; typed variables match an object of that type; subqueries; action to perform on match [»martM10_2005]

Subtopic: repeating patterns up

Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]

Subtopic: file difference up

Quote: while computing file differences, solitary lines must be the same in both files; may have moved [»heckP4_1978]
Quote: while computing file differences, identify matching precursors and successors of a matched pair of lines [»heckP4_1978]

Subtopic: name matching up

Quote: Synoname matches personal names by heuristics derived from correct matches of personal names [»grosAD4_1991]

Subtopic: patterns as events up

Quote: meta-level compilation through extensible compiler with high-level state machines applied down every path; transitions triggered by patterns [»chouA11_2000]
QuoteRef: waitWM7_1967 ;;434 matches by full left to right ordered match with back up
QuoteRef: waitWM7_1967 ;;434 pattern matching by all possibilities. arbitrary strings no types

Subtopic: pattern reduction up

Quote: TUTOR removes matching part of a student response and attempts to find additional matches [»schwJ_1980]
QuoteRef: noshK_1972 ;;217 Formal-2 takes input and parses it into a tree using forms and backtracking. Matches done on longest match first.

Subtopic: compressed data up

Quote: algorithm for pattern matching in UNIX Z-compressed files; O(n log m + m) for short patterns of length m [»amirA1_1994]
Quote: search compressed text with byte-pair compression; faster search, 30% compression, byte-pairs can not overlap [»manbU4_1997]

Subtopic: match iterator up

Quote: unlike SNOBOL4, Icon allows matching procedures in the form of a generator; returns a value when 'suspend' is done [»grisRE4_1980]
Quote: instead of constructing patterns, Icon uses 'scan s using e' to establish a context for pattern matching by e [»grisRE4_1980]

Subtopic: alphabet size up

Quote: use alphabet transformation to increase alphabet size; e.g., "A G G C T A" becomes "AG GG GC CT TA" [»kimS_1999]
Quote: Quick Search is best for large alphabets and small patterns while Reverse Factor is best for small alphabets and large patterns [»lecrT7_1995]

Subtopic: problems with pattern matching up

Quote: pattern matching in SNOBOL4 can be very arcane, even to the point of needing the system's source listings

Related Topics up

Group: grammar   (8 topics, 181 quotes)
Group: sequence operations   (7 topics, 85 quotes)

Topic: access by pattern matching (18 items)
Topic: approximate string matching and pattern matching with errors (19 items)
Topic: backtracking (30 items)
Topic: function syntax by pattern (15 items)
Topic: pattern brackets (15 items)
Topic: pattern components (15 items)
Topic: search algorithms (40 items)
Topic: sequence generators (16 items)
Topic: spelling errors (18 items)
Topic: string operations (20 items)
Topic: string transformation languages (17 items)
Topic: structure transformation languages (7 items)
Topic: sub-sequences (13 items)
Topic: suffix trie and suffix array (20 items)
Topic: syntax analysis
(29 items)

Updated barberCB 11/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.