Patent US6785677B1 successfully refreshed from Google Patents.

US6785677B1 Expired / Lapsed US ⏱️ 0.0 years remaining

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

Assignee: Unisys Corp

•

Filing: 2001-05-02

•

Granted: 2004-08-31

•

Expires: 2021-05-02

📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

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.

Inventors

👤 Barry Lynn Fritchman

Bibliographic Details

Application Number —

Jurisdiction US

Data Source google_patents

Last Synchronized 2026-11-09 13:28

CPC Classifications

G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/28; G06F16/284; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936; Y10S707/99937

Claims Analysis

Total Claims: 11

Claim 1

Independent Claim 114 words

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.

Claim 2

Dependent Claim 114 words

Claim 3

Dependent Claim 27 words

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.

Claim 4

Dependent Claim 42 words

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.

Claim 5

Dependent Claim 114 words

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 L 1 and L 2 characters long where L 1 is the character-length of said prefix segment and L 2 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 L 2 characters of said target string; (b3) matching said extracted prefix segment with said target string by comparing said prefix segment to the first L 1 characters of said target string; (b4) matching said extracted interior segment(s) with said target string.

Claim 6

Dependent Claim 87 words

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.

Claim 7

Dependent Claim 89 words

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.

Claim 8

Dependent Claim 90 words

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.

Claim 9

Dependent Claim 84 words

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.

Claim 10

Dependent Claim 86 words

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.

Claim 11

Dependent Claim 103 words

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.

References Cited (Backward Citations)

US4450520A Cited

US5051745A Cited

WO1992015067A1 Cited

US5559693A Cited

US5412808A Cited

US5615283A Cited

US6131092A Cited

US5794177A Cited

US6397346B1 Cited

US5926652A Cited

US6122757A Cited

US6018735A Cited

US6026398A Cited

US6338061B1 Cited

US6047283A Cited

US6321224B1 Cited

US6459810B1 Cited

US20030200528A1 Cited

USPTO Annuity & Maintenance Windows

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2007-08-31	2008-03-01	2008-08-31	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2011-08-31	2012-03-01	2012-08-31	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2015-08-31	2016-03-01	2016-08-31	$7700.00	Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag

Select Category

Notes (Optional)