Word-containing database accessing system for responding to ambiguous queries, including a dictionary of database words, a dictionary searcher and a database searcher

• US 6,018,736 A
• Filed: 11/20/1996
• Issued: 01/25/2000
• Est. Priority Date: 10/03/1994
• Status: Expired due to Term

• Current Assignee: Phonetic Systems Limited (Microsoft Corporation)
• Original Assignee: Phonetic Systems Limited (Microsoft Corporation)
• Inventors: Resnekov, Hezi, Gilai, Atzmon
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/749,374
• Time in Patent Office: 1,161 Days
• Field of Search: 707/5, 707/6, 707/532, 707/533, 704/239, 704/240, 704/251, 379/89
• 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: G06F 16/90335 Query processing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A database accessing system for processing a request to access a database including a multiplicity of entries, each entry including at least one word, the request including a sequence of representations of possibly erroneous user inputs, the system including a similar word finder operative, for at least one interpretation of each representation, to find at least one database word which is at least similar to that interpretation, and a database entry evaluator operative, for each database word found by the similar word finder, to assign similarity values for relevant entries in the database, said values representing the degree of similarity between each database entry and the request.

Claims

1. A database accessing system for processing a database query, the database including a multiplicity of entries each of which comprises at least first and second words, the database query including a sequence of at least first and second inputs corresponding to said first and second words respectively, each input including a plurality of input elements, the system including:

a dictionary of all words in said database, including, for each word, a spelled representation of the word and a phonetic representation of the word;

an input element interpreter operative to convert each of said at least first and second inputs into a representation of a plurality of strings of symbol-probability pairs, each symbol-probability pair including a symbol which is a possible interpretation of an individual input element and an estimated probability of said input element having said possible interpretation;

a trigram stochastic evaluator operative to select high-probability strings from among said plurality of strings in said graph based at least partly on the frequency with which trigrams of symbols within said strings appear in said database;

a dictionary searcher operative, for each individual high-probability string, to search said dictionary for words whose phonetic representation is similar, relative to a predetermined similarity threshold, to a phonetic representation of said individual high-probability string and to assign to each found word a similarity value quantifying the degree to which the found word phonetically resembles the individual high-probability string; and

an entry similarity evaluator operative to identify a subset of entries in the database, based on output from said dictionary searcher, and, for each individual entry in said subset, to evaluate the similarity of said entry as a whole to said database query by combining the similarity values representing similarity of the words within said individual entry to the corresponding inputs within said database query.

2. A system according to claim 1 wherein the similarity value assigned to an individual word depends only on the absolute degree of resemblance of the individual word to said input and does not depend on the relative degree to which the individual word resembles said input, in relation to the degrees to which other words in the dictionary resemble said input.

3. A system according to claim 1 wherein the words found by the dictionary searcher comprise all words which exceed a predetermined word-level resemblance threshold rather than comprising a predetermined number of best words.

4. A system according to claim 1 wherein at least one of said inputs comprises a spoken word and at least one of said input elements comprises a phoneme.

5. A system according to claim 1 wherein at least one of said inputs comprises an orally spelled word and at least one of said input elements comprises an orally spoken letter.

6. A system according to claim 1 wherein at least one of said inputs comprises a sequence of keystrokes and at least one of said input elements comprises a keystroke.

7. A system according to claim 1 wherein said representation comprises a a probabilistic string including a sequence S over an alphabet A of n elements where each element S_i (i=1, . . . , n) in sequence S is a finite, nonempty set of (symbol, probability) pairs.

8. A system according to claim 1 and also comprising a phonetic translator operative to generate a phonetic representation of each said high-probability string.

9. A system according to claim 1 wherein said entry similarity evaluator is operative to compute the similarity between at least one similar/non-similar entry and said query, wherein said similar/non-similar entry includes a first word whose similarity relative to the query'"'"'s first word falls above the predetermined similarity threshold and a second word whose similarity relative to the query'"'"'s first word falls below the predetermined similarity threshold.

10. A system according to claim 1 and also comprising a dictionary arranger operative to arrange said dictionary as a hierarchy of clusters, each cluster including words with an identical reduced alphabet, and wherein said dictionary searcher is operative to traverse the dictionary hierarchically.

11. A system according to claim 1 wherein said database comprises a telephone directory.

12. A system according to claim 1 wherein at least one of said inputs comprises a spoken word and at least one of said input elements comprises a phoneme.

13. A system according to claim 1 wherein at least one of said inputs comprises an orally spelled word and at least one of said input elements comprises a orally spoken letter.

14. A system according to claim 1 wherein at least one of said inputs comprises a sequence of keystrokes and at least one of said input elements comprises a keystroke.

15. A system according to claim 1 wherein the entry similarity evaluator is operative to combine said similarity scores into a combined value and to select entries having highest combined value.

16. A system according to claim 1 wherein the entry similarity evaluator is operative to decide whether a database entry does or does not correspond to a database query based on the similarity values of all inputs in the query.