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,256,630 B1
• Filed: 06/17/1999
• Issued: 07/03/2001
• 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: Gilai, Atzmon, Resnekov, Hezi
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/335,456
• Time in Patent Office: 747 Days
• Field of Search: 707/5, 707/533, 707/6, 707/532, 704/255, 704/239, 704/240, 704/251
• 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 has a predetermined structure comprising 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;

a dictionary searcher operative to find words in said dictionary which resemble each of said inputs and to assign to each found word a similarity score describing the degree to which said word resembles said input; and

a database searcher operative to use said similarity scores in order to find entries in said database whose words, have cumulative scores which indicate that they most resemble said query.

2. A system according to claim 1 wherein the similarity score 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 said database searcher includes:

a candidate entry searcher operative to find all entries which exceed a predetermined entry-level resemblance threshold rather than comprising a predetermined number of best entries; and

a conversation manager operative, if more than one entries are found by the candidate entry searcher, to hold an interactive conversation with a human user in order to allow the human user to select from among the more than one entries found by the candidate entry searcher.

5. 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.

6. 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.

7. 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.