Group:
grammar
Group:
sequence operations
Topic:
access by pattern matching
Topic:
approximate string matching and pattern matching with errors
Topic:
backtracking
Topic:
function syntax by pattern
Topic:
pattern brackets
Topic:
pattern components
Topic:
search algorithms
Topic:
sequence generators
Topic:
spelling errors
Topic:
string operations
Topic:
string transformation languages
Topic:
structure transformation languages
Topic:
sub-sequences
Topic:
suffix trie and suffix array
Topic:
syntax analysis
| |
Summary
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 
| 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
| 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
| 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
| Quote: test equality of arbitrary byte sequences by testing their 128-bit fingerprints
|
Subtopic: partial match
| 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
| 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
| Quote: use abstract tree matching to check the parse tree of a use pattern
|
Subtopic: event log matching
| 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
| 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
| Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]
|
Subtopic: file difference
| 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
| Quote: Synoname matches personal names by heuristics derived from correct matches of personal names [»grosAD4_1991]
|
Subtopic: patterns as events
| 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
| 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
| 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
| 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
| 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
Quote: pattern matching in SNOBOL4 can be very arcane, even to the point of needing the system's source listings
[»grisRE4_1980]
|
Related Topics
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)
|
