Adaptive non-literal text string retrieval

• US 5,600,835 A
• Filed: 11/20/1995
• Issued: 02/04/1997
• Est. Priority Date: 08/20/1993
• Status: Expired due to Term

• Current Assignee: Canon Inc.
• Original Assignee: Canon Inc.
• Inventors: Roberts, Michael G., Avi-Itzhak, Hadar I., Garland, Harry T., Hunter, Kenneth M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lewis, Cheryl Renea
• Application Number:
  US08/561,204
• Time in Patent Office: 442 Days
• Field of Search: 395/600, 364/200, 364/419
• US Class Current: 1/1
• 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: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Method and system for selectively retrieving information contained in a stored document set using a non-literal, or "fuzzy", search strategy. A text string query is transmitted (200) to a computer processor, and a dissimilarity value D_i is assigned (208) to selected ones of stored text strings representative of information contained in a stored document set, based upon a first set of rules (106). A set of retrieved text strings representative of stored information and related to the text string query is generated (212), based upon a second set of rules (107). Each of the retrieved text strings has an associated dissimilarity value D_i, which is a function of at least one rule R_n from the first set of rules (106) used to retrieve the text string and a weight value w_n associated with that rule R_n. The retrieved text strings are displayed (216) preferably in an order based on their associated dissimilarity value D_i. Once one or more of the retrieved text strings is chosen, the weight value w_n associated with at least one rule of the first set of rules (106) is adjusted (220) and stored.

Claims

1. A computer-implemented method for selectively retrieving text strings from a plurality of stored text strings contained in a document set stored on a data storage medium accessible by a computer processor, said method comprising the steps of:

A. transmitting a text string query defined by a user to the processor;

B. generating a dissimilarity value D_i associated with the user-defined text string query and each of selected ones of the text strings in the stored document set in accordance with a first set of rules, wherein each dissimilarity value D_i is a function of at least one rule R_n from the first set of rules and a weight value w_n associated with each R_n, wherein each weight value indicates the relative importance of the associated rule in predicting a desired outcome of the retrieval;

C. retrieving a text string set, including at least one retrieved text string, from the selected text strings in accordance with a second set of rules, based upon the dissimilarity values D_i generated in step B;

D. generating a display of the retrieved text strings in a display order;

E. said user choosing at least one of the retrieved text strings from the displayed text string set for further processing; and

F. automatically adjusting the weight value w_n, defining an adjusted weight value w_n '"'"', associated with at least one rule of the first set of rules, based upon the results of the choosing step.

2. The method of claim 1, wherein, for subsequent retrievals, the dissimilarity value D_i assigned to each selected text string uses the adjusted weight value w_n '"'"'.

3. The method of claim 1, wherein ##EQU2## where r_n is the number of times R_n must be applied to the selected text string to create a test string that matches the text string query, and k is the total number of rules in the first set of rules.

4. The method of claim 3, wherein the step of generating a display comprises generating a display of the retrieved text strings in an increasing order based on the dissimilarity value D_i associated with each retrieved text string.

5. The method of claim 3, wherein the step of adjusting the weight value comprises:

determining a measure of correspondence C between a mean dissimilarity value D_i associated with chosen text strings and a mean dissimilarity value D_m associated with non-chosen text strings.

6. The method of claim 5, further comprising increasing the measure C by selectively adjusting the weight values w_n associated with selected ones of the rules in the first set of rules.

7. The method of claim 6, further comprising normalizing at least one of the weight values w_n.

8. The method of claim 1, wherein the step of adjusting the weight value w_n comprises:

(a) decreasing the dissimilarity value associated with each of the chosen text strings; and

(b) increasing the dissimilarity value associated with each of the non-chosen text strings.

9. A computer system for selectively retrieving text strings from a plurality of stored text strings contained in a document set stored on a data storage medium accessible by a computer processor, said system comprising:

A. data input means for transmitting a text string query defined by a user to the processor;

B. a first storage medium for storing a first set of rules, each rule having an associated weight value w_n, wherein each weight value indicates the relative importance of the associated rule in predicting a desired outcome of the retrieval, and a second storage medium for storing a second set of rules;

C. means for associating a dissimilarity value D_i with each of selected ones of text strings from the data storage medium, wherein each dissimilarity value D_i is a function of at least one rule R_n from the first set of rules and the weight value w_n associated with said R_n ;

D. means for retrieving a text string set, including at least one text string, from the selected text strings, in accordance with the second set of rules, based upon the dissimilarity values D_i ;

E. a display device for generating a display of the retrieved text strings in a display order;

F. choosing means for allowing said user to select at least one of the retrieved text strings for further processing; and

G. coupled to the choosing means and responsive to said user'"'"'s selection of said at least one retrieved text string for further processing, means for automatically adjusting at least one weight value w_n, defining an adjusted weight value w_n '"'"'.

10. The system of claim 9, wherein the dissimilarity value D_i associated with each chosen text string includes the adjusted weight value w_n '"'"'.

11. The system of claim 9, wherein ##EQU3## where r_n is the number of times R_n must be applied to the selected text strings to create a text string that matches the text string query, and k is the total number of rules in the first set of rules.

12. The system of claim 11, wherein the display device comprises means for displaying the retrieved text strings in an increasing order based on the dissimilarity value D_i associated with each retrieved text string.

13. The system of claim 11, further comprising:

means, associated with the first storage medium, for generating and storing a measure of correspondence C between a mean dissimilarity value D_i associated with chosen text strings and a mean dissimilarity value D_m associated with non-chosen text strings.

14. The system of claim 13, further comprising means for increasing the measure C by selectively adjusting at least one weight value w_n.

15. The system of claim 14, further comprising normalizing means for normalizing at least one weight value w_n.

16. The system of claim 9, wherein the adjusting means comprises:

(a) means for decreasing the dissimilarity value associated with each of the chosen text strings; and

(b) means for increasing the dissimilarity value associated with each of the non-chosen text strings.