Method, apparatus and computer program product for extracting known patterns from a data structure in a single pass

Claim 2

A computer controlled method for searching a data structure to extract possible matches of one or more known patterns that may exist in said data structure, said method comprising steps of: (a) building said data structure, said data structure having a starting node and one or more dependent nodes linked to said starting node; (b) matching said starting node with a first base leaf contained within a direction list, said direction list comprising a plurality of tnodes one of which is said first base leaf, said direction list also representing said one or more known patterns each capable of being represented within said data structure, each of said one or more known patterns sharing said first base leaf within said direction list, the plurality of tnodes including a plurality of tnode markers; (c) searching said data structure from said starting node for said one or more known patterns in said direction list by performing a single traversal of said direction list, said single traversal corresponding to said dependent nodes; and (d) accumulating one or more patterns dependent on step (c).

Claim 3

The computer controlled method of claim 1 further comprising: (e) constructing said direction list.

Claim 4

The computer controlled method of claim 2 wherein step (e) comprises steps of: (e1) identifying said one or more known patterns; and (e2) creating a first tree of tnodes, extending from said first base leaf representing said one or more known patterns that start from said first base leaf, each of said one or more known patterns represented by a respective interrelationship between said plurality of tnodes, wherein portions of said respective interrelationship that are shared between each of said one or more known patterns are represented by shared tnodes, each of said plurality of tnodes containing pattern information.

Claim 5

The computer controlled method of claim 3 wherein said direction list further comprises a second base leaf having a second tree of tnodes.

Claim 6

The computer controlled method of claim 1 wherein step (c) further comprises steps of: (c1) gathering a plurality of tnode markers from said plurality of tnodes, each of said plurality of tnode markers associated with said one or more known patterns; (c2) identifying a pattern termination tnode corresponding to a specific pattern of said one or more known patterns; and (c3) validating that said single traversal gathered required tnode markers associated with said specific pattern.

Claim 7

The computer controlled method of claim 1 wherein step (d) further comprises selecting a first pattern over a second pattern dependent on the number of tnodes represented by said first pattern and said second pattern.

Claim 8

The computer controlled method of claim 1 wherein said data structure is a directed acyclic graph (DAG), said starting node and said dependent nodes represent atomic image processing operations, said one or more known patterns representing molecular image processing operations.

Claim 11

The apparatus of claim 8 further comprising a direction list construction mechanism configured to construct said direction list.

Claim 12

The apparatus of claim 9 wherein the direction list construction mechanism comprises: a pattern identification mechanism configured to identify said one or more known patterns; and a direction list creation mechanism configured to create a first tree of tnodes, extending from said first base leaf, representing said one or more known patterns that start from said first base leaf, each of said on e or more known patterns represented by a respective interrelationship between said plurality of tnodes, wherein portions of said respective interrelationship that are shared between each of said one or more known patterns are represented by shared tnodes, each of said plurality of tnodes containing pattern information.

Claim 13

The apparatus of claim 10 wherein said direction list further comprises a second base leaf having a second tree of tnodes.

Claim 14

The apparatus of claim 8 wherein the pattern search mechanism further comprises: a marker gathering mechanism configured to gather a plurality of tnode markers from said plurality of tnodes, each of said plurality of tnode markers associated with said one or more known patterns; a termination tnode identification mechanism configured to identify a pattern termination tnode corresponding to a specific pattern of said one or more known patterns; and a pattern validation mechanism configured to validate that said single traversal gathered required tnode markers associated with said specific pattern.

Claim 15

The apparatus of claim 8 wherein the pattern accumulation mechanism further comprises a pattern selection mechanism configured to select a first pattern over a second pattern dependent on the number of tnodes represented by said first pattern and said second pattern.

Claim 16

The apparatus of claim 8 wherein said data structure is a directed acyclic graph (DAG), said starting node and said dependent nodes represent atomic image processing operations, said one or more known patterns representing molecular image processing operations.

Claim 17

A computer program product comprising: a computer usable medium having computer readable code embodied therein for causing a computer to search a data structure in a memory to extract possible matches of one or more known patterns that may exist in said data structure, said computer readable code comprising: computer readable program code configured to cause said computer to effect a data structure construction mechanism configured to build said data structure in said memory, said data structure having a starting node and one or more dependent nodes linked to said starting node; computer readable program code configured to cause said computer to effect a base-leaf matching mechanism configured to match said starting node of said data structure with a first base leaf contained within a direction list, said direction list comprising a plurality of tnodes one of which is said first base leaf, said direction list also representing said one or more known patterns each capable of being represented within said data structure, each of said one or more known patterns sharing said first base leaf within said direction list, the plurality of tnodes including a plurality of tnode markers; computer readable program code configured to cause said computer to effect a pattern search mechanism configured to search said data structure from said starting node for said one or more known patterns in said direction list by performing a single traversal of said direction list, said single traversal corresponding to said dependent nodes; and computer readable program code configured to cause said computer to effect a pattern accumulation mechanism configured to accumulate one or more patterns dependent on the pattern search mechanism.

Claim 18

A computer program product comprising: a computer usable medium having computer readable code embodied therein for causing a computer to search a data structure in a memory to extract possible matches of one or more known patterns that may exist in said data structure, said computer readable code comprising: computer readable program code configured to cause said computer to effect a data structure construction mechanism configured to build said data structure in said memory, said data structure having a starting node and one or more dependent nodes linked to said starting node; computer readable program code configured to cause said computer to effect a base-leaf matching mechanism configured to match said starting node of said data structure with a first base leaf contained within a direction list, said direction list comprising a plurality of tnodes one of which is said first base leaf, said direction list also representing said one or more known patterns each capable of being represented within said data structure, each of said one or more known patterns sharing said first base leaf within said direction list, the plurality of tnodes including a plurality of tnode markers; computer readable program code configured to cause said computer to effect a pattern search mechanism configured to search said data structure from said starting node for said one or more known patterns in said direction list by performing a single traversal of said direction list, said single traversal corresponding to said dependent nodes; and computer readable program code configured to cause said computer to effect a pattern accumulation mechanism configured to accumulate one or more patterns dependent on the pattern search mechanism.

Claim 19

The computer program product of claim 15 further comprising computer readable program code configured to cause said computer to effect a direction list construction mechanism configured to construct said direction list.

Claim 20

The computer program product of claim 16 wherein the direction list construction mechanism comprises: computer readable program code configured to cause said computer to effect a pattern identification mechanism configured to identify said one or more known patterns; and computer readable program code configured to cause said computer to effect a direction list creation mechanism configured to create a first tree of tnodes, extending from said first base leaf, representing said one or more known patterns that start from said first base leaf, each of said one or more known patterns represented by a respective interrelationship between said plurality of tnodes, wherein portions of said respective interrelationship that are shared between each of said one or more known patterns are represented by shared tnodes, each of said plurality of tnodes containing pattern information.

Claim 21

The computer program product of claim 17 wherein said direction list further comprises a second base leaf having a second tree of tnodes.

Claim 22

The computer program product of claim 15 wherein the pattern search mechanism further comprises: computer readable program code configured to cause said computer to effect a marker gathering mechanism configured to gather a plurality of tnode markers from said plurality of tnodes, each of said plurality of tnode markers associated with said one or more known patterns; computer readable program code configured to cause said computer to effect a termination tnode identification mechanism configured to identify a pattern termination tnode corresponding to a specific pattern of said one or more known patterns; and computer readable program code configured to cause said computer to effect a pattern validation mechanism configured to validate that said single traversal gathered required tnode markers associated with said specific pattern.

Claim 23

The computer program product of claim 15 wherein the pattern accumulation mechanism further comprises computer readable program code configured to cause said computer to effect a pattern selection mechanism configured to select a first pattern over a second pattern dependent on the number of tnodes represented by said first pattern and said second pattern.

Claim 24

The computer program product of claim 15 wherein said data structure is a directed acyclic graph (DAG), said starting node and said dependent nodes represent atomic image processing operations, said one or more known patterns representing molecular image processing operations.