RETRIEVAL USING A GENERALIZED SENTENCE COLLOCATION

• US 20100114574A1
• Filed: 01/29/2009
• Published: 05/06/2010
• Est. Priority Date: 11/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Gang, Zhou, Ming, Zhao, Jing, Jiang, Long, Liu, Xiaohua, Wei, Hao, Scott, Matthew R.
• Granted Patent: US 8,484,014 B2
• Time in Patent Office: Days
• US Class Current: 704/251
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules

Abstract

A method and system for identifying documents relevant to a query that specifies a part of speech is provided. A retrieval system receives from a user an input query that includes a word and a part of speech. Upon receiving an input query that includes a word and a part of speech, the retrieval system identifies documents with a sentence that includes that word collocated with a word that is used as that part of speech. The retrieval system displays to the user an indication of the identified documents.

Claims

1. A method in a computing device for searching for sentences, the method comprising:

providing a collection of sentences;

for each sentence in the collection,

identifying pairs of collocated words of the sentence;

for each identified pair of collocated words,

identifying a part of speech of each word of the pair;

generating a first part of speech and word pair that includes the identified part of speech of the first word and the second word and a second part of speech and word pair that includes the first word and the identified part of speech of the second word; and

generating a mapping from the first part of speech and word pair and the second part of speech and word pair for the sentence;

receiving an input query that includes a first word, a part of speech, and a second word;

identifying from the mapping sentences that include the first word of the input query collocated with a word with the part of speech of the input query and a word with the part of speech collocated with the second word of the input query; and

displaying to a user the identified sentences.

2. The method of claim 1 wherein the identifying of sentences includes identifying a sentence such that the same word with the part of speech of input query is collocated with both the first word and the second word of the input query.

3. The method of claim 1 wherein the mapping includes an entry for each unique part of speech and word pair that identifies sentences that contain collocated words with that part of speech and word pair.

4. The method of claim 3 wherein each entry of the mapping identifies a position of the part of speech and a position of the word within each sentence that contains collocated words.

5. The method of claim 1 wherein the identifying of a part of speech of a word within a sentence includes invoking a natural language parser.

6. The method of claim 1 including ranking the identified sentences based on readability and displaying the sentences in an order base on their ranking.

7. The method of claim 1 wherein when the input query includes multiple parts of speech identifying sentences that include each of the multiple parts of speech collocated with a word of the input query.

8. A computer-readable storage medium containing instructions for controlling a computing device to identify documents relevant to a query, by a method comprising:

receiving from a user an input query that includes a word and a part of speech;

identifying documents with a sentence the includes the word collocated with a word of that part of speech;

ranking the identified documents; and

displaying to the user the identified documents in order of their rankings.

9. The computer-readable storage medium of claim 8 wherein the documents are sentences.

10. The computer-readable storage medium of claim 9 including

providing a collection of sentences;

for each sentence in the collection,

identifying pairs of collocated words of the sentence;

for each identified pair of collocated words,

identifying a part of speech of each word of the pair as used in the sentence;

generating a first part of speech and word pair that includes the identified part of speech of the first word and the second word and a second part of speech and word pair that includes the first word and the identified part of speech of the second word; and

generating a mapping from the first part of speech and word pair and the second part of speech and word pair for the sentence.

11. The computer-readable storage medium of claim 10 wherein the identifying of documents uses the generated mapping.

12. The computer-readable storage medium of claim 8 wherein the documents are web pages identified by crawling web sites.

13. The computer-readable storage medium of claim 12 wherein the ranking of the documents includes ranking web pages based on the relevance of sentences to the input query.

14. The computer-readable storage medium of claim 12 including generating a mapping of collocated words and their parts of speech for the web pages.

15. The computer-readable storage medium of claim 14 wherein the identifying of documents uses the generated mapping to identify web pages that include the word of the input query collocated with a word of the part of speech of the input query.

16. A computing device for identifying sentences having words of a designated part of speech, comprising:

a component that inputs from a user a query having a word and a part of speech;

a component that identifies sentences that have the word of the query collocated with a word used as the part of speech of the query; and

a component that displays to the user the identified sentences.

17. The computing device of claim 16 wherein the word of the query and the word used as the part of speech are the same word.

18. The computing of claim 16 wherein the word of the query and the word used as the part of speech are different words.

19. The computing device of claim 16 including a component that ranks the sentences and wherein the sentences are displayed in an order based on their ranking.

20. The computing device of claim 16 including a component that generates a mapping of collocated words and their parts of speech for sentences that contain them.