Multiple string search method

• US 6,377,942 B1
• Filed: 07/22/1999
• Issued: 04/23/2002
• Est. Priority Date: 09/04/1998
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Hinsley, Stewart Robert, Le Lohé, Léon Richard
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/358,976
• Time in Patent Office: 1,006 Days
• Field of Search: 705/10, 707/2-5, 707/1, 707/6, 707/7, 707/10, 707/200, 709/315, 712/228, 712/245, 711/163
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A data processing system has a searching mechanism for finding occurrences of a plurality of key strings within a target string. The searching mechanism forms a hash value from each of the key strings, and adds each key string to a collection of key strings having the same hash value. It then selects a plurality of symbol positions in the target string, and forms a hash value at each selected symbol position in the target string. This hash value is used to select one of the collections of key strings. Each key string in the selected collection of key strings is then compared with the target string.

Claims

1. A data processing system comprising searching means for finding occurrences of a plurality of key strings within a target string, wherein the searching means comprises:

(a) means for forming a hash value from each of the key strings, and for organizing said plurality of key strings into a plurality of collections of key strings, each of said collections of key strings corresponding to a particular hash value;

(b) means for selecting a plurality of symbol positions in the target string;

(c) means for forming a hash value at each selected symbol position in the target string and for using this hash value to select one of the collections of key strings; and

(d) means for comparing each key string in the selected collection of key strings with the target string.

2. A data processing system according to claim 1 wherein each hash value is formed from two symbols of the string.

3. A data processing system according to claim 1 wherein the hash value is formed from the initial symbols of the string.

4. A data processing system according to claim 1 wherein the collections of key strings are linked lists.

5. A data processing system according to claim 1 wherein the selected symbol positions consist of all symbol positions within the target string.

6. A method for finding occurrences of a plurality of key strings within a target string, comprising the steps:

(a) forming a hash value from each of the key strings, and organizing said plurality of key strings into a plurality of collections of key strings, each of said collections of key strings corresponding to a particular hash value;

(b) selecting a plurality of symbol positions in the target string;

(c) forming a hash value at each selected symbol position in the target string and using this hash value to select one of the collections of key strings; and

(d) comparing each key string in the selected collection of key strings with the target string.

7. A method according to claim 6 wherein each hash value is formed from two symbols of the string.

8. A method according to claim 6 wherein the hash value is formed from the initial symbols of the string.

9. A method according to claim 6 wherein the collections of key strings are linked lists.

10. A method according to claim 6 wherein the selected symbol positions consist of all symbol positions within the target string.

11. An information carrier, holding a program for implementing a method for finding occurrences of a plurality of key strings within a target string, the method comprising the steps:

(a) forming a hash value from each of the key strings, and organizing said plurality of key strings into a plurality of collections of key strings, each of said collections of key strings corresponding to a particular hash value;

(b) selecting a plurality of symbol positions in the target string;

(c) forming a hash value at each selected symbol position in the target string and using this hash value to select one of the collections of key strings; and

(d) comparing each key string in the selected collection of key strings with the target string.