CONDITIONAL STRING SEARCH

• US 20090157673A1
• Filed: 12/12/2007
• Published: 06/18/2009
• Est. Priority Date: 12/12/2007
• Status: Active Grant

• Current Assignee: Trend Micro Kabushiki Kaisha
• Original Assignee: Trend Micro Kabushiki Kaisha
• Inventors: BOYCE, Kevin Gerard
• Granted Patent: US 8,825,693 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/279 Recognition of textual entities

Abstract

A method and a system for efficient search of string patterns characterized by positional relationships in a character stream are disclosed. The method is based on grouping string patterns of a dictionary into at least two string sets and performing string search processes of a text of the character stream based on individual string sets with the outcome of a search process influencing a subsequent search process. A system implementing the method comprises a dictionary processor for generating string sets with corresponding text actions and search actions, a conditional search engine for locating string patterns belonging to at least one string set in a text according to a current search state, a text operator for producing an output text according to search results, and a search operator for determining a subsequent search state.

Claims

1. A method of string search in a character stream, the method comprising:

grouping string patterns of a dictionary into a plurality of string sets according to predetermined criteria;

defining a set of parameterized search states each search state characterized by;

domain parameters defining a search domain within said character stream;

a string set from among said plurality of string sets; and

a search rule;

associating with each string pattern of each string set a search action identifying a search domain and a subsequent search state;

acquiring an input text from said character stream;

selecting a current search state and setting a current search domain to cover the entire input text;

determining a current string set and a current rule corresponding to said current search state;

executing a search procedure using said current rule to determine a location of a current string pattern belonging to said current string set within said current search domain; and

ascertaining a subsequent search state and corresponding domain parameters.

2. The method of claim 1 further comprising:

setting said subsequent search state as said current search state;

delimiting said current search domain according to said corresponding domain parameters; and

repeating the steps of determining and executing.

3. The method of claim 1 wherein said each search state is further characterized by a search data structure.

4. The method of claim 1 further comprising a step of encoding said search rule as a set of data-driven instructions.

5. The method of claim 1 wherein said predetermined criteria are set by an administrator.

6. The method of claim 1 wherein said predetermined criteria are determined according to topological sorting of string patterns of said dictionary.

7. The method of claim 1 wherein said dictionary includes at least one complex string.

8. The method of claim 1 wherein said plurality of string sets comprises non-intersecting string sets.

9. The method of claim 1 wherein said plurality of string sets comprise a first group of non-intersecting string sets and at least one string set comprising at least two string sets of said first group of non-intersecting string sets.

10. The method of claim 1 further comprising:

associating with each string pattern of each string set a text action, from among a set of predefined text actions; and

performing a text action associated with said current string pattern.

11. The method of claim 3 wherein said text action is one of marking, altering, substituting, and deletion of said current string pattern.

12. A method of string search in a character stream, the method comprising:

constructing a dictionary of string patterns, associating a text action, from among a set of text actions, with each string pattern;

grouping said string patterns into a predefined number of ordered string sets according to predetermined criteria;

acquiring an input text from said character stream;

selecting a first string set as a current string set and a current search domain as the entire input text;

executing a search procedure to determine locations of current string patterns belonging to said current string set within said current search domain;

determining current text actions corresponding to said current string pattern;

cumulatively storing said locations and said current text actions;

selecting a subsequent string set according to a predetermined order of said string sets;

defining a current search domain according to said locations;

repeating said executing, determining, and storing for remaining string sets in said predefined number of ordered string sets; and

returning to the step of acquiring.

13. The method of claim 12 wherein the step of defining comprises setting said current search domain as a portion of said input text between two consecutive locations of said locations of current string patterns.

14. The method of claim 12 wherein the step of defining comprises setting said current search domain as a portion of said input text within a predefined number of characters following one of said locations of current string patterns.

15. A system for string search in a character stream, the system comprising:

a dictionary processor for grouping string patterns of a dictionary into a plurality of string sets and associating with each string pattern of each string set post-detection information comprising;

a text action, selected from a predefined set of text actions, to be applied to said character stream;

a subsequent string set; and

domain parameters defining a search domain within said character stream;

a conditional search engine for locating current string patterns belonging to a current string set within a current search domain in said character stream;

a search operator for setting a subsequent string set and corresponding search domain according to said current string patterns; and

a text operator for performing text actions corresponding to said current string patterns.

16. The system of claim 15 wherein said dictionary processor further assigns to each string set a search rule encoded as a set of data-driven instructions.

17. The system of claim 15 wherein said dictionary processor further assigns to each string set a respective search data structure.

18. The system of claim 15 further comprising buffers for storing input texts extracted from said character stream and output texts to be

19. The system of claim 15 further comprising encoded search instructions based on a set of predefined search states where each string set in said plurality of string sets is associated with a search state.

20. The system of claim 15 further comprising a memory device storing a search-state-transition matrix each entry of which comprises encoded search instructions to be followed upon transition from one search state to another.