Apparatus and method for finding records in a database by formulating a query using equivalent terms which correspond to terms in the input query

• US 5,404,507 A
• Filed: 03/02/1992
• Issued: 04/04/1995
• Est. Priority Date: 03/02/1992
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Simon, Jeffrey J., Bohm, Charles P., Nowitz, David A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US07/844,045
• Time in Patent Office: 1,128 Days
• Field of Search: 395/600, 364/419.07, 364/419.13, 364/419.14, 364/419.15, 364/419.19
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An apparatus and method for searching for records of database items with incomplete or incorrectly provided input data. Database queries are automatically created and executed in a manner that has a high probability of selecting the correct record indicative of a desired item from a retrieved set of candidates. The queries comprise search expressions which are generated for supplementing each one of a series of input words comprising the input data. These search expressions include terms and phrases that are equivalent to each input word and also include expanded acronyms and abbreviations. When required, the search expressions further include words that are close to an input word when it appears to be misspelled.

Claims

1. A method of retrieving a record for an item in an information database in response to an input string of target words, the method comprising the steps of:

comparing each word contained in the input string of target words with words contained in a search expression database associated with the information database;

generating a set of search expressions for each one of multiple ordered queries, each search expression including words from the search expression database for providing an equivalent representation of one or more of the input string of target words;

retrieving records from the information database, each record retrieved in each of the multiple ordered queries containing the set of search expressions respectively generated for one of the multiple ordered queries, the multiple ordered queries being arranged in order of a most restrictive query to a least restrictive query; and

selecting in accordance with a predetermined parameter a retrieved one of the records that best matches the input string of target words.

2. The method of claim 1 wherein the words in the search expression database include expanded acronyms and abbreviations that are equivalent to associated words stored in the information database.

3. The method of claim 1 wherein the most restrictive query contains the most search expressions and the least restrictive query contains the fewest search expressions.

4. The method of claim 3 wherein the ordered queries are executed by the executing step for retrieving records from the information database, the executing step including the steps of executing the most restrictive query and, if no records are retrieved, executing the next most restrictive query for retrieving records from the information database.

5. The method of claim 1 wherein the predetermined parameter comprises assigning a closeness value to each record found in accordance with the retrieving step.

6. The method of claim 5 wherein the closeness value assigned to each record is determined by evaluative criteria, said criteria including exact word matching and ordered word prefix matching.

7. The method of claim 6 further comprising the step of comparing the number of matched words and matched word prefixes in each of the retrieved records with said words and word prefixes in the input string of target words.

8. The method of claim 7 wherein the highest closeness value is assigned to the one of the retrieved records having the greater number of matching words and the fewer number of nonmatching words.

9. The method of claim 8 wherein the selecting step further comprises the step of requesting the item corresponding to the retrieved one of the records from an item provider.

10. A method of retrieving a record for an item in an information database in response to an input string of target words, the method comprising the steps of:

comparing each word contained in the input string of target words with words contained in a first search expression database associated with the information database;

generating a plurality of search expressions, each search expression including a word from the string of target words and words from the search expression database for providing art equivalent representation of one or more of the input string of target words, and one or more selected words close in character content to one of the target words not located in the first search expression database, the one or more selected words being obtained from a second search expression database for supplementing said target word;

retrieving records from the information database, each record containing the words included in each of the search expressions; and

selecting in accordance with a predetermined parameter a retrieved one of the records that best matches the input string of target words.

11. The method of claim 10 wherein the second search expression data base comprises a trigram database, the trigram database containing words that are close in character content to mispelled target words.

12. The method of claim 11 wherein the predetermined parameter comprises assigning a closeness value to each record found in accordance with the retrieving step.

13. The method of claim 12 wherein the closeness value assigned to each record is determined by evaluative criteria, said criteria including exact word matching and ordered word prefix matching.

14. The method of claim 13 further comprising comparing the number of matched words and matched word prefixes in each of the retrieved records with said words and word prefixes in the input string of target words.

15. The method of claim 14 wherein the highest closeness value is assigned to the one of the retrieved records having the greater number of matching words and the fewer number of nonmatching words.

16. The method of claim 10 wherein the selecting step further comprises the step of requesting the item corresponding to the retrieved one of the records from an item provider.

17. A method of retrieving a record of an item from a plurality of information databases in response to a series of input words, the method comprising the steps of:

comparing each word contained in the series of input words with words contained in a first and a second one of a plurality of search expression databases associated with a first one of the plurality of information databases;

generating a set of search expressions, each search expression in the set including words from the first search expression database for providing an equivalent representation of one or more of the series of input words and words from the second search expression database for providing selected words close in character content to one or more of the series of input words;

searching in the first one of the plurality of information databases for retrieving records containing the search expressions;

searching in other of the plurality of information databases for retrieving records containing the search expressions when none of the retrieved records in the first one of the plurality of information databases best matches the series of input words in accordance with a predetermined parameter; and

selecting in accordance with the predetermined parameter the retrieved record from any of the plurality of information databases that best matches the series of input words.

18. The method of claim 17 wherein the searching in other of the plurality of information databases is performed in a predetermined order.

19. The method of claim 17 wherein the predetermined parameter comprises assigning a closeness value to each record found in accordance with the retrieving step.

20. The method of claim 19 wherein the closeness value assigned to each record is determined by evaluative criteria, said criteria including exact word matching and ordered word prefix matching.

21. The method of claim 20 wherein the closeness value assigned to each record is further determined by the step of comparing the number of matched words and matched word prefixes in each of the retrieved records with said words and word prefixes in the series of input words.

22. The method of claim 21 wherein the highest closeness value is assigned to the one of the retrieved records having the greater number of matching words and matching prefixes and the fewer number of nonmatching words.

23. A system for retrieving a record of an item in an information database in response to an input string of target words, the system comprising:

means for comparing each word contained in the input string of target words with words contained in a search expression database associated with the information database;

means for generating a set of search expressions for each one of multiple ordered queries, each search expression including words from the search expression database for providing an equivalent representation of one or more of the input string of target words;

means for retrieving records from the information database, each record retrieved in each of the multiple ordered queries containing the set of search expressions respectively generated for one of the multiple ordered queries, the multiple ordered queries being arranged in order of a most restrictive query to a least restrictive query; and

means for selecting in accordance with a predetermined parameter a retrieved one of the records that best matches the input string of target words.

24. The system of claim 23 wherein the words in the search expression database include expanded acronyms and abbreviations that are equivalent to associated words stored in the information database.

25. The system of claim 23 wherein the predetermined parameter comprises a closeness value indicator assigned to each record retrieved in the information database.

26. The system of claim 25 wherein the closeness value indicator assigned to each record is determined by evaluative criteria, said criteria including exact word matching and ordered word prefix matching.

27. The system of claim 25 further comprising means for comparing the number of matched words and matched word prefixes in each of the retrieved records with said words and word prefixes in the input string of target words.

28. The system of claim 25 wherein the highest closeness value indicator is assigned to the one of the retrieved records having the greater number of matching words and the fewer number of nonmatching words.