Method for execution of query to search strings of characters that match pattern with a target string utilizing bit vector

• US 6,785,677 B1
• Filed: 05/02/2001
• Issued: 08/31/2004
• Est. Priority Date: 05/02/2001
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Fritchman, Barry Lynn
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US09/847,473
• Time in Patent Office: 1,217 Days
• Field of Search: 707/1-10, 707/104-104, 707/200-205, 709/230-238, 704/1-10, 704/39, 710/49-51, 710/65, 710/267-269, 358/403, 382/173, 382/177, 382/231, 382/309, 382/310, 382/229, 382/218, 340/146.2, 712/300, 714/39, 714/715, 714/735
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

The method of the present invention is useful in a computer system including at least one client. The program executes a method for matching a pattern string with a target string, where either string can contain single or multi-character wild cards. The method includes the steps of preprocessing the pattern string into a prefix segment, a suffix segment, and zero or more interior segments. Next, matching the prefix segment, the suffix segment, and the interior segment(s) with the target string.

Claims

1. In a computer system including at least one client and using two special character symbols designated as a single-character wild card and a multi-character wild card, a method for matching a pattern string with a target string, said method comprising the steps of:

(a) preprocessing said pattern string into segments which are the maximal contiguous sequence of characters from the pattern string that do not contain the multi-character wild card;

(b) matching said target string with said segments of said pattern string;

(c) utilizing a bit vector providing a bit-position for each character in said pattern string whereby a bit vector signal “

1”

is set to indicate the presence of a single-character wild card.

2. The method as in claim 1 wherein said segments consist of literal text with no metacharacters and are matched against the target string using string search algorithms.

3. The method as in claim 1 wherein said preprocessing step (a) includes the steps of:

(a1) extracting a prefix segment from said pattern string;

(a2) extracting a suffix segment from said pattern string;

(a3) extracting an interior segment(s) from said pattern string.

4. The method as in claim 3 wherein said matching step (b) of claim 1 includes the steps of:

(b1) determining that said target string is at least L1 and L2 characters long where L1 is the character-length of said prefix segment and L2 is the character-length of said suffix segment;

(b2) matching said extracted suffix segment with said target string by comparing said suffix segment to the last L2 characters of said target string;

(b3) matching said extracted prefix segment with said target string by comparing said prefix segment to the first L1 characters of said target string;

(b4) matching said extracted interior segment(s) with said target string.

5. The method as in claim 4 wherein said step (b2) of matching said extracted suffix segment includes the steps of:

(b2a) determining the number of suffix characters comprising said suffix segment;

(b2b) matching each character of said suffix segment with the final number of said number of suffix characters within said target string, while skipping each single-character wild card marked in said bit vector;

(b2c) if each of said number of suffix characters match, reducing the end of said target string by said number of suffix characters.

6. The method as in claim 4 wherein said step (b3) of matching said extracted prefix segment includes the steps of:

(b3a) determining a number of prefix characters comprising said prefix segment;

(b2b) matching each character of said prefix segment with one of said number of prefix characters at the corresponding position within said target string, while skipping each single-character wild card marked in said bit vector;

(b3c) if each of said number of prefix characters match, moving the beginning of said target string past said number of prefix characters.

7. The method as in claim 4 wherein said step (b4) of matching said interior segment(s) includes the steps of:

(b4a) iterating through each of said interior segments within said interior segment list;

(b4b) performing a search modified to account for single-character wild cards for each of said interior segments within the target string;

(b4c) repositioning a beginning of said target string for each of said successful searches so that the new position for said beginning is the character following the last character which was matched by a given successful search.

8. The method as in claim 3 wherein said step (a1) of extracting said prefix segment includes the steps of:

(a1a) initializing said extracted prefix segment to an empty string;

(a1b) initializing a starting prefix position to a first character in said pattern string;

(a1c) appending each character, from said starting prefix position up to but not including a first multi-character wild card in said pattern string, to said prefix segment, while placing a position signal for each single-character wild card into said bit vector.

9. The method as in claim 3 wherein said step of (a2) extracting said suffix segment includes the steps of:

(a2a) initializing said extracted suffix segment to an empty string;

(a2b) initializing a starting suffix position to a first character past a last multiple wild card character in said pattern string;

(a2c) appending each character, from said starting suffix position up to a last character in said pattern string, to said suffix segment, while placing a position signal for each single-character wild card into said bit vector.

10. The method as in claim 3 wherein said step

(a3) of extracting said interior segment(s) includes the steps of:

(a3a) initializing an interior segment list to an empty list of strings;

(a3b) initializing a string to an area of said pattern string lying between said prefix segment and said suffix segment;

(a3c) adding all characters within said string lying between two multi-character wild cards into an interior segment, while placing a position signal for each single-character wild card into said bit vector;

(a3d) appending each of said interior segments to said interior segment list in the order of its occurrence within the pattern.