Configurable pattern recognition and filtering tool

• US 6,687,694 B2
• Filed: 01/09/2001
• Issued: 02/03/2004
• Est. Priority Date: 01/05/2000
• Status: Expired due to Fees

• Current Assignee: Jim Miller
• Original Assignee: Jim Miller
• Inventors: Miller, Jim
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/756,511
• Publication Number:
  US 20020040357A1
• Time in Patent Office: 1,120 Days
• Field of Search: 707/1-10, 706/47, 706/20
• US Class Current: 706/47
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Highly configurable software apparatus for recognizing and manipulating user-defined patterns in an input data stream. It allows the user to define unlimited combinations and sequences of patterns, and actions to perform when patterns are recognized. Patterns are defined in terms of user-defined sets. Patterns are linked in graph-like structures. As the input stream is scanned the apparatus progresses from one pattern (subpattern) to the next. The rules the apparatus follows to make transitions from one pattern to the next can be configured. Configured actions are performed as patterns are recognized in the input stream.

Claims

1. An apparatus for recognizing user-defined patterns in a data stream,

the apparatus comprising

a subpattern configuring means, each subpattern comprising

a value set and a range,

each value set comprised of a list of values,

each range comprising a minimum number and a maximum number of occurrences of said values contained in said value set,

a subpattern sequence configuring means, each subpattern sequence comprised of one or more subpatterns, each of said subpatterns being followed in said sequence by zero or more said subpatterns,

a transition rule configuring means, said means used to configure the rules that the apparatus follows when making transitions between said subpatterns in said sequences,

a starting subpattern designation means, said starting subpattern being the first subpattern in said sequences to be sought by the apparatus in said data stream, said starting subpattern to be sought by the apparatus when the apparatus is unable to continue making transitions from one subpattern to another in said data stream,

an action configuration means that configures actions to be performed by the apparatus when events occur during the operation of the apparatus, said actions constituting the results of the operation of the apparatus,

said apparatus recognizing patterns in said data stream by traversing said sequences, beginning the traversal at said starting subpattern, continuing said traversal by making transitions according to said transition rules between subpatterns in said sequences, resuming said traversal at said starting subpattern when unable to make a transition from the current subpattern to another in said sequences, said apparatus producing results with said actions,

whereby any data stream may be divided into segments per the configuration of said apparatus.

2. An apparatus as in claim 1,

wherein said transition rules include the ability to make the transition between adjacent subpatterns in said sequences as late as possible, said apparatus considering

the current value in said data stream,

the configuration of the current subpattern in said sequences,

whereby the overhead of examination of any subsequent subpatterns may be avoided.

3. An apparatus as in claim 2,

wherein said transition rules include the ability to make the transition between adjacent subpatterns in said sequences as soon as possible, said apparatus considering

the current value in said data stream,

the values succeeding said current value in said data stream,

the configuration of the current subpattern in said sequences,

the configuration of the subsequent subpatterns in said sequences,

whereby a subpattern with a substantially inclusive set, being followed in said sequences by one or more less-inclusive subpatterns, causes said apparatus to search for said less-inclusive subpatterns.

4. An apparatus as in claim 3,

further including a means of configuring priorities for attempts by said apparatus to make the transition from one subpattern to another when said subpattern is followed by more than one subpattern in said sequences.

5. An apparatus as in claim 4,

further including a means of configuring a pattern, said pattern comprising one or more said subpatterns,

whereby said pattern can represent its respective subpatterns anywhere in the configuration of said apparatus.

6. An apparatus as in claim 5,

further including a means of identifying with a tag one or more sub-sequences of said sequences, said tag thereby defining a group of said sub-sequences, said tag referring during operation of said apparatus to the member of said group most recently recognized in said data stream.

7. An apparatus as in claim 6,

further including a means of configuring a “

bookend”

subpattern of maximum length zero, said “

bookend”

subpattern

being considered recognized by said apparatus before scanning of said data stream,

being considered recognized by said apparatus after scanning of said data stream,

whereby beginning-of-input and end-of-input conditions can be handled.