On-line help method and system utilizing free text query

• US 5,694,559 A
• Filed: 03/07/1995
• Issued: 12/02/1997
• Est. Priority Date: 03/07/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Flynn, James R., Finkelstein, Erich-S.o slashed.ren, Horvitz, Eric, Heckerman, David E., Jensen, Karen, Breese, John S., Shaw, Gregory L., Hobson, Samuel D.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/400,797
• Time in Patent Office: 1,001 Days
• Field of Search: 395/600, 395/603-606, 395/12, 395/155, 395/156, 395/161, 395/336-338, 395/758-759, 364/419.08, 364/419.13
• US Class Current: 715/705
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 9/453 Help systems
• CPC Class Codes: G06F 9/454 Multi-language systems; Localisation; Internationalisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An improved free text query method and system is provided as part of an improved on-line help system. In a preferred embodiment of the present invention, the on-line help system provides a free text query system that performs partial analysis. The partial analysis performed by the preferred embodiment includes identifying keywords within input provided by the user, performing disambiguation analysis, performing definiteness analysis, performing capitalization analysis, and generating a ranked list of candidates according to a probability associated with each candidate. In addition, the preferred embodiment of the present invention is internationalizable. That is, the present invention is easily ported between different languages.

Claims

1. In a computer system having a plurality of help-topics for providing assistance to a user of the computer system and a free text query system for receiving input from the user indicating a selection and for generating a list of candidates for the selection, a method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection;

providing a plurality of keywords relevant to the selection to the computer system and identifying ones of the keywords within the received input in response to receiving the input;

providing a plurality of metanyms to the computer system, wherein each of the metanyms is a general concept describing at least one of the keywords, wherein each of the metanyms is associated with a candidate help topic and determining the metanym for each of the ones of the keywords in response to identifying the ones of the keywords;

identifying the candidate help topic associated with each of the determined metanyms, wherein each candidate help topic has an associated likelihood that the selection refers to the candidate help topic;

for each identified candidate help topic,

increasing the likelihood of the identified candidate help topic when each of the determined metanyms is associated with the identified candidate help topic;

decreasing the likelihood of the identified candidate help topic when each of the determined metanyms is not associated with the identified candidate help topic; and

generating a list of the identified candidate help topics according to the likelihood of the identified candidate help topics.

2. In a computer system having a free text query system for receiving input from a user indicating a selection and for generating a list of candidates for the selection, a method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection;

providing a plurality of keywords relevant to the selection to the computer system and identifying ones of the keywords within the received input in response to receiving the input;

providing a plurality of metanyms to the computer system, wherein each of the metanyms is a general concept describing at least one of the keywords and is associated with a candidate, wherein the general concept describing at least one of the keywords is not particular to a natural language, and determining the metanym for each of the ones of the keywords in response to identifying the ones of the keywords;

identifying the candidate associated with each determined metanym, wherein each candidate has an associated likelihood that the selection refers to the candidate; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

3. The method of claim 2 wherein each of the plurality of words has a case, wherein the step of determining the metanym includes the steps of changing the case of each of the ones of the keywords to create new case keywords, and determining the metanym for each of the new case keywords.

4. The method of claim 2 wherein the free text query system accepts input in a first language, wherein the keywords and the metanyms are in the first language, wherein the free text query system has a first language component for performing processing specific to the first language, and said method further including the steps of:

creating a second language component for performing processing specific to a second language; and

converting the synonyms and metanyms from the first language to the second language in response to creating the second language component.

5. The method of claim 2 wherein the computer system has a default probability indicating a likelihood that a candidate that is unassociated with a metanym is relevant to the selection, and the method further including the steps of:

identifying candidates unassociated with each of the determined metanyms to create second identified candidates, and

multiplying the likelihood of each second identified candidates by the default probability, and

wherein the step of generating a list includes the step of generating a list of the candidates according to the likelihood of the first identified candidates and the second identified candidates.

6. The method of claim 2 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating a list includes the step of generating a list of the help topics.

7. In a computer system having a free text query system for receiving input from a user indicating a selection and for generating a list of candidates for the selection, a method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection, wherein each of the words has a form;

providing a plurality of keywords to the computer system that are relevant to the selection and that are associated with candidates and identifying ones of the keywords within the received input;

identifying the candidates associated with the ones of the keywords, wherein each of the candidates has an associated likelihood that the selection refers to the candidate;

providing a definiteness component for determining a form of each of the ones of the keywords and invoking the definiteness component to determine the form of the ones of the keywords in response to identifying the candidates associated with the ones of the keywords;

adjusting the probability for each of the identified candidates in response to invoking the definiteness component; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

8. The method of claim 7 wherein the computer system has a functional word list containing entries which indicate the form of a plurality of words, and wherein the step of invoking the definiteness component includes the steps of:

for each of the identified keywords,

determining a preceding word in the received input to the keyword;

searching the functional word list to find an entry matching the preceding word; and

accessing the found entry to determine the form of the keyword.

9. The method of claim 7 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating a list includes the step of generating a list of the help topics.

10. In a computer system, the computer system having a free text query system for receiving input from a user comprising a plurality of words indicating a selection and for generating a list of candidates for the selection and a disambiguation component, each candidate having an associated likelihood that the selection refers to the candidate, each word having a usage of either a noun or a verb, the disambiguation component for determining the usage of a word, a usage of each word being associated with a candidate, a method comprising the steps of:

receiving input from the user indicating the selection;

invoking the disambiguation component to determine the usage of the words in the received input;

identifying the candidates associated with the words in response to determining the usage of the words; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

11. The method of claim 10 wherein the computer system has a disambiguation list containing words having both a noun usage and a verb usage and a rule base for determining the usage of a word, and wherein the step of invoking the disambiguation component includes the steps of:

searching the disambiguation list to determine whether each word in the received input is found in the disambiguation list; and

for each word found in the disambiguation list,

determining a preceding word from the received input;

determining a following word from the received input; and

invoking the role base with the preceding word and the following word to determine the usage of the word.

12. The method of claim 10 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating a list includes the step of generating a list of the help topics.

13. A free-text query system comprising:

a user input component for receiving user input containing a plurality of words indicating a selection, the selection having a type;

a keyword component for identifying keywords within the user input, keywords being predetermined to be relevant to the type of the selection;

a metanym component for determining a metanym associated with each keyword, the metanym being a general concept for the keyword that is language independent; and

a generating component for identifying a candidate associated with each metanym and generating a list of the identified candidates according to an associated likelihood that the selection refers to the identified candidates.

14. The free text query system of claim 13 wherein the keyword component further comprises:

a disambiguation component for determining a usage of the words in the user input and for determining a keyword associated with the usage of the words.

15. The free text query system of claim 13, further comprising:

a definiteness component for receiving the list of identified candidates from the generating component, for determining a form of each keyword, and for adjusting the likelihood of the identified candidates in response to determining the form of the keyword.

16. The free text query system of claim 13 wherein the keyword component further comprises:

a capitalization component for determining a case of the words in the user input and for determining a keyword associated with the case of the words.

17. The free text query system of claim 13, further comprising:

an internationalization component for converting the free text query system from a first language to a second language before the user input component receives the user input.

18. The free text query system of claim 13 wherein the generating component generates a list of help topics, wherein the help topics contain information to assist the user.

19. The free text query system of claim 13 wherein the generating component increases the likelihood of each identified candidate when each metanym is associated with the identified candidate and decreases the likelihood of each identified candidate when each metanym is not associated with the identified candidate.

20. A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a plurality of help topics for providing assistance to a user of the computer system and a free text query system for receiving input from the user indicating a selection and for generating a list of candidates for the selection, the method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection;

providing a plurality of keywords relevant to the selection to the computer system and identifying ones of the keywords within the received input in response to receiving the input;

providing a plurality of metanyms to the computer system, wherein each of the metanyms is a general concept describing at least one of time keywords, wherein each of the metanyms is associated with a candidate help topic and determining the metanym for each of the ones of the keywords in response to identifying the ones of the keywords;

identifying the candidate help topic associated with each of the determined metanyms, wherein each candidate help topic has an associated likelihood that the selection refers to the candidate help topic;

for each identified candidate help topic,

increasing the likelihood of time identified candidate help topic when each of the determined metanyms is associated with time identified candidate help topic;

decreasing the likelihood of the identified candidate help topic when each of the determined metanyms is not associated with the identified candidate help topic; and

generating a list of the identified candidate help topics according to the likelihood of the identified candidate help topics.

21. A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a free text query system for receiving input from a user indicating a selection and for generating a list of candidates for the selection, the method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection;

providing a plurality of keywords relevant to the selection to the computer system and identifying ones of the keywords within the received input in response to receiving the input;

providing a plurality of metanyms to the computer system, wherein each of the metanyms is a general concept describing at least one of the keywords and is associated with a candidate, wherein the general concept describing at least one of the keywords is not particular to a natural language, and determining the metanym for each of the ones of the keywords in response to identifying the ones of the keywords;

identifying the candidate associated with each determined metanym, wherein each candidate has an associated likelihood that the selection refers to the candidate; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

22. The computer-readable medium of claim 21 wherein each of the plurality of words has a case, wherein the step of determining the metanym includes the steps of changing the case of each of the ones of the keywords to create new case keywords, and determining the metanym for each of the new case keywords.

23. The computer-readable medium of claim 21 wherein the free text query system accepts input in a first language, wherein the keywords and the metanyms are in the first language, wherein the free text query system has a first language component for performing processing specific to the first language, and said method further including the steps of:

creating a second language component for performing processing specific to a second language; and

converting the synonyms and metanyms from the first language to the second language in response to creating the second language component.

24. The computer-readable medium of claim 21 wherein the computer system has a default probability indicating a likelihood that a candidate that is unassociated with a metanym is relevant to the selection, and the method further including the steps of:

identifying candidates unassociated with each of the determined metanyms to create second identified candidates, and

multiplying the likelihood of each second identified candidates by the default probability, and

wherein the step of generating a list includes the step of generating a list of the candidates according to the likelihood of the first identified candidates and the second identified candidates.

25. The computer-readable medium of claim 21 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating a list includes the step of generating a list of the help topics.

26. A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a free text query system for receiving input from a user indicating a selection and for generating a list of candidates for the selection, the method comprising the steps of:

receiving input comprising a plurality of words from the user indicating a selection, wherein each of the words has a form;

providing a plurality of keywords to the computer system that are relevant to the selection and that are associated with candidates and identifying ones of the keywords within the received input;

identifying the candidates associated with the ones of the keywords, wherein each of the candidates has an associated likelihood that the selection refers to the candidate;

providing a definiteness component for determining a form of each of the ones of the keywords and invoking the definiteness component to determine the form of the ones of the keywords in response to identifying the candidates associated with the ones of the keywords;

adjusting the probability for each of the identified candidates in response to invoking the definiteness component; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

27. The computer-readable medium of claim 26 wherein the computer system has a functional word list containing entries which indicate the form of a plurality of words, and wherein the step of invoking file definiteness component includes the steps of:

for each of the identified keywords,

determining a preceding word in the received input to the keyword;

searching the functional word list to find an entry matching the preceding word; and

accessing file found entry to determine the form of the keyword.

28. The computer-readable medium of claim 26 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating at list includes the step of generating a list of the help topics.

29. A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a free text query system for receiving input from a user comprising a plurality of words indicating a selection and for generating a list of candidates for the selection and a disambiguation component, each candidate having an associated likelihood that the selection refers to the candidate, each word having a usage of either a noun or a verb, the disambiguation component for determining the usage of a word, a usage of each word being associated with a candidate, the method comprising the steps of:

receiving input from the user indicating the selection;

invoking the disambiguation component to determine the usage of the words in the received input;

identifying the candidates associated with the words in response to determining the usage of the words; and

generating a list of the identified candidates according to the likelihood of the identified candidates.

30. The computer-readable medium of claim 29 wherein the computer system has a disambiguation list containing words having both a noun usage and a verb usage and a rule base for determining the usage of a word, and wherein the step of invoking the disambiguation component includes the steps of:

searching the disambiguation list to determine whether each word in the received input is found in the disambiguation list; and

for each word found in the disambiguation list,

determining a preceding word from the received input;

determining a following word from the received input; and

invoking the rule base with the preceding word and the following word to determine the usage of the word.

31. The computer-readable medium of claim 29 wherein the computer system has a plurality of help topics for providing assistance to the user, wherein the candidates correspond to the help topics, and wherein the step of generating a list includes the step of generating a list of the help topics.