Searching for sequences of character data

• US 6,768,991 B2
• Filed: 05/15/2001
• Issued: 07/27/2004
• Est. Priority Date: 05/15/2001
• Status: Expired due to Term

• Current Assignee: McAfee, LLC
• Original Assignee: Networks Associates Technology, Inc. (McAfee, LLC)
• Inventors: Hearnden, Stephen Owen
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Le, Debbie M.
• Application Number:
  US09/854,456
• Publication Number:
  US 20020188926A1
• Time in Patent Office: 1,169 Days
• Field of Search: 707/1-7
• US Class Current: 707/778
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A modified Boyer-Moore searching algorithm used within an E-mail filtering system for detecting the presence of a plurality of target band strings during a single traversal of the character data to be searched. A single jump table for the combined set of strings for which a search is being made is used. A hierarchical match table starting with the possible terminating letters of strings for which a search is being made is traversed to identify any strings as they are encountered.

Claims

1. A computer program product comprising a computer program operable to control a computer to search within a sequence of character data for occurrence of any of a plurality strings each formed of a predetermined sequence of characters, said computer program comprising:

character identifying logic operable to identify a target character at a target search position within said sequence of character data;

string identifying logic operable to compare character data preceding said target character with data indicative of any of said plurality of strings that terminate with said target character to identify an occurrence of any of said plurality of strings that terminate with said target character; and

target search position advancing logic operable to advance said target search position within said sequence of character data by a predetermined number of character positions equal to a smallest number of character positions separating said target character from a last character within any of said plurality of strings.

2. A computer program product as claimed in claim 1, wherein said character identifying logic, said string identifying logic and said target search position advancing logic operate in a repeating sequence until said target search position reaches an end of said sequence of character data.

3. A computer program product as claimed in claim 1, wherein said plurality of strings comprise a collection of problem words for which a search is made through said sequence of character data.

4. A computer program product as claimed in claim 3, wherein said sequence of character data comprises e-mail message data and said search for problem words is part of an e-mail filtering operation.

5. A computer program as claimed in claim 1, wherein said target search position advancing logic is responsive to a predetermined table of jump data specifying said predetermined number of character position for each target character.

6. A computer program product as claimed in claim 1, wherein said string identifying logic uses a hierarchical data structure to identify said plurality of strings, nodes within said hierarchy corresponding to a match character preceding said target character by a predetermined number of character positions and being connecting to at least one of:

(i) a node higher in said hierarchy corresponding to a character succeeding said match character in one or more of said plurality of strings; and

(ii) a node lower in said hierarchy corresponding to a character preceding said match character in one or more of said plurality of strings.

7. A computer program product as claimed in claim 6, wherein at a lowest level in said hierarchy traced along a path through said hierarchy a lowest node specifies at least one of said plurality of strings.

8. A computer program product as claimed in claim 7, wherein said lowest node specifies a longest character length of any string specified by said lowest node such that said string identifying logic can read a number of characters corresponding to said longest character length from said sequence of character data to be compared with any string specified by said lowest node.

10. A method as claimed in claim 1, wherein said steps of identifying, comparing and advancing operate in a repeating sequence until said target search position reaches an end of said sequence of character data.

9. A method of searching within a sequence of character data for occurrence of any of a plurality strings each formed of a predetermined sequence of characters, said method comprising the steps of:

identifying a target character at a target search position within said sequence of character data;

comparing character data preceding said target character with data indicative of any of said plurality of strings that terminate with said target character to identify an occurrence of any of said plurality of strings that terminate with said target character; and

advancing said target search position within said sequence of character data by a predetermined number of character positions equal to a smallest number of character positions separating said target character from a last character within any of said plurality of strings.

11. A method as claimed in claim 9, wherein said plurality of strings comprise a collection of problem words for which a search is made through said sequence of character data.

12. A method as claimed in claim 11, wherein said sequence of character data comprises e-mail message data and said search for problem words is part of an e-mail filtering operation.

13. A computer program as claimed in claim 9, wherein said step of advancing is responsive to a predetermined table of jump data specifying said predetermined number of character position for each target character.

14. A method as claimed in claim 9, wherein said steps of comparing uses a hierarchical data structure to identify said plurality of strings, nodes within said hierarchy corresponding to a match character preceding said target character by a predetermined number of character positions and being connecting to at least one of:

(i) a node higher in said hierarchy corresponding to a character succeeding said match character in one or more of said plurality of strings; and

(ii) a node lower in said hierarchy corresponding to a character preceding said match character in one or more of said plurality of strings.

15. A method as claimed in claim 14, wherein at a lowest level in said hierarchy traced along a path through said hierarchy a lowest node specifies at least one of said plurality of strings.

16. A method as claimed in claim 15, wherein said lowest node specifies a longest character length of any string specified by said lowest node such that said string identifying logic can read a number of characters corresponding to said longest character length from said sequence of character data to be compared with any string specified by said lowest node.

17. Apparatus for processing data operable to search within a sequence of character data for occurrence of any of a plurality strings each formed of a predetermined sequence of characters, said apparatus comprising:

a character identifier operable to identify a target character at a target search position within said sequence of character data;

a string identifier operable to compare character data preceding said target character with data indicative of any of said plurality of strings that terminate with said target character to identify an occurrence of any of said plurality of strings that terminate with said target character; and

a target search position advancer operable to advance said target search position within said sequence of character data by a predetermined number of character positions equal to a smallest number of character positions separating said target character from a last character within any of said plurality of strings.

18. Apparatus as claimed in claim 17, wherein said character identifier, said strings identifier and said target search position advancer operate in a repeating sequence until said target search position reaches an end of said sequence of character data.

19. Apparatus as claimed in claim 17, wherein said plurality of strings comprise a collection of problem words for which a search is made through said sequence of character data.

20. Apparatus as claimed in claim 19, wherein said sequence of character data comprises e-mail message data and said search for problem words is part of an e-mail filtering operation.

21. A computer program as claimed in claim 17, wherein said target search position advancer is responsive to a predetermined table of jump data specifying said predetermined number of character position for each target character.

22. Apparatus as claimed in claim 17, wherein said string identifier uses a hierarchical data structure to identify said plurality of strings, nodes within said hierarchy corresponding to a match character preceding said target character by a predetermined number of character positions and being connecting to at least one of:

(i) a node higher in said hierarchy corresponding to a character succeeding said match character in one or more of said plurality of strings; and

(ii) a node lower in said hierarchy corresponding to a character preceding said match character in one or more of said plurality of strings.

23. Apparatus as claimed in claim 22, wherein at a lowest level in said hierarchy traced along a path through said hierarchy a lowest node specifies at least one of said plurality of strings.

24. Apparatus as claimed in claim 23, wherein said lowest node specifies a longest character length of any word specified by said lowest node such that said string identifying logic can read a number of characters corresponding to said longest character length from said sequence of character data to be compared with any string specified by said lowest node.