Approximate string matcher for delimited strings

• US 6,718,325 B1
• Filed: 06/14/2000
• Issued: 04/06/2004
• Est. Priority Date: 06/14/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chandra, Arun
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/593,907
• Time in Patent Office: 1,392 Days
• Field of Search: 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for comparing two delimited strings, each of which has a plurality of substrings, includes pairing each substring in one of the delimited string with a corresponding substring in the other one of the delimited strings. The method further includes computing a proximity value for each pair of substrings, and computing a set of decaying weights corresponding to the pairs of substrings, multiplying the proximity value for each pair of substrings by the corresponding weight, and summing the weighted proximity values to obtain a strength of match between the delimited strings.

Claims

1. A method for comparing two delimited strings each having a plurality of substrings, comprising:

pairing each substring in one of the delimited strings with a corresponding substring in the other one of the delimited strings;

computing a proximity value for each pair of substrings;

computing a set of decaying weights corresponding to the pairs of substrings;

multiplying the proximity value for each pair of substrings by the corresponding weight; and

summing the weighted proximity values to obtain the strength of match between the delimited strings.

2. The method of claim 1, wherein computing a proximity value for each pair of substrings comprises evaluating a proximity function which counts a maximum number of substrings of a given size range that match between the paired substrings.

3. The method of claim 2, further comprising normalizing the proximity function to obtain the proximity value.

4. The method of claim 1, wherein the computing the set of decaying weights comprises calculating a step function.

5. The method of claim 1, wherein the computing the set of decaying weights comprises calculating an exponential function.

6. The method of claim 1, wherein the computing the set of decaying weights comprises calculating a chi-square function.

7. A method for performing a search query, comprising:

receiving a text string from a data source;

pairing substrings in a search query string with substrings in the text string;

computing a proximity value for each pair of substrings;

computing a set of decaying weights corresponding to the pairs of substrings;

multiplying the proximity value for each pair of substrings by the corresponding weight; and

summing the weighted proximity values to obtain a strength of match between the text string and the search query string.

8. A computer-readable medium having stored thereon a program which is executable by a processor, the program comprising instructions for:

receiving two delimited strings, each of which has a plurality of substrings;

pairing each substring in one of the delimited string with a corresponding substring in the other one of the delimited strings;

computing a proximity value for each pair of substrings;

computing a set of decaying weights corresponding to the pairs of substrings;

multiplying the proximity value for each pair of substrings by the corresponding weight; and

summing the weighted proximity values to obtain a strength of match between the delimited strings.

9. The computer-readable medium of claim 8, wherein computing a proximity value for each pair of substrings comprises evaluating a proximity function which counts a maximum number of substrings of a given size range that match between the paired substrings.

10. The computer-readable medium of claim 9, further comprising normalizing the proximity function to obtain the proximity value.

11. The computer-readable medium of claim 8, wherein the computing the set of decaying weights comprises calculating a step function.

12. The computer-readable medium of claim 8, wherein the computing the set of decaying weights comprises calculating an exponential function.

13. The computer-readable medium of claim 8, wherein the computing the set of decaying weights comprises calculating a chi-square function.