Multistage intelligent string comparison method

• US 5,978,797 A
• Filed: 07/09/1997
• Issued: 11/02/1999
• Est. Priority Date: 07/09/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Yianilos, Peter N.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US08/890,659
• Time in Patent Office: 846 Days
• Field of Search: 707/3, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A multistage database search method includes a first stage that only considers textual polygraphic frequencies and a second stage that considers the location of the polygraphs and coarsely approximates the proper alignment between the query and the database strings and a third stage that provides a better approximation of the alignment. The final output is a listing of suggested database records ranked by their similarity to the query.

Claims

1. A method of searching a database for a query comprising the steps of:

(a) providing a database of strings of characters;

(b) providing a query string;

(c) identifying polygraphs that occur in said query string and also in said database strings;

(d) providing a cost to each said identified polygraph;

(e) positioning the query string relative to each database string;

(f) matching polygraph occurrences in the query string with those in each database string, the cost of matching providing a numerical indication of the similarity between said query string and each said database string;

(g) realigning said query string to reduce the cost by examining edges present in the matching solution;

(h) repeating said matching and said realigning a predetermined number of times or until the cost of matching fails to improve; and

(i) repeating the steps (c) to (h) above for each database string for the purpose of identifying those database strings most similar to said query string.

2. A method of searching as set forth in claim 1, where polygraphs are longer than a predetermined fixed minimum length and shorter than a predetermined fixed maximum length.

3. A method of searching as set forth in claim 1, where the query string is initially left-aligned with each database string.

4. A method of searching as set forth in claim 1, where said matching is approximated by relying only on the number of matching of said polygraph.

5. A method of searching as set forth in claim 1, where said matching is approximately identified by dividing matching polygraphs into levels so that occurrences alternate between said query string and database string such that:

when the number of occurrences is even, the matching is uniquely defined and when the number of occurrences is odd, omitting either the first or last occurrence.

6. A method of searching as set forth in claim 1, where said matching is identified by a quasi-convex matching method.

7. A method of searching as set forth in claim 1, where said examination of edges comprises computing the mean of the edge lengths.

8. A method of searching as set forth in claim 1, where said examination of edges comprises computing the median of the edge lengths.

9. A method of searching as set forth in claim 1, where said matching following realigning is approximated by mathematically adjusting edge lengths.

10. A method of searching as set forth in claim 1, where said identification of most similar database strings is performed using a heap data-structure.

11. A method of searching as set forth in claim 1, where said query strip and database string are mathematically padded to a predetermined length.

12. A multistage method of searching a database for a query comprising the steps of:

providing a database of strings of characters;

providing a query string;

processing each database string using a first method selected on the basis of computational time efficiency for identifying database strings that are similar to said query string;

processing said similar database strings using a second method selected to be more accurate but less time efficient than said first method for identifying smaller numbers of database strings that are similar to said query string, and

providing final identification of most similar database strings based on the result of processing said similar database strings.

13. A multistage method of searching as set forth in claim 12, where said first method and said second method are selected from the group consisting of relying on the number of matchings of a polygraph, dividing matching polygraphs into levels so that occurrences alternate between said query string and database string such that when the number of occurrences is even, the matching is uniquely defined and when the number of occurrences is odd, omitting either the first or last occurrences, quasi-convex matching, and mathematically adjusting edge length.

14. A multistage method of searching as set forth in claim 13, where said providing final identification of most similar database strings is performed using a heap data-structure.

15. A multistage method of searching as set forth in claim 12, where said providing final identification of most similar database strings is performed using a heap data-structure.