Document-based synonym generation

• US 8,392,413 B1
• Filed: 01/17/2012
• Issued: 03/05/2013
• Est. Priority Date: 02/07/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Grushetskyy, Oleksandr, Baker, Steven D.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/352,126
• Time in Patent Office: 413 Days
• Field of Search: 707/727, 707/728, 707/730, 707/E17.008, 707/E17.064, 707/804, 707/811, 707/755, 715/258, 715/260, 704/E15.021, 704/E15.024, 704/4, 704/9, 704/10, 704/205, 704/231
• US Class Current: 707/727
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

One embodiment of the present invention provides a system that automatically generates synonyms for words from documents. During operation, this system determines co-occurrence frequencies for pairs of words in the documents. The system also determines closeness scores for pairs of words in the documents, wherein a closeness score indicates whether a pair of words are located so close to each other that the words are likely to occur in the same sentence or phrase. Finally, the system determines whether pairs of words are synonyms based on the determined co-occurrence frequencies and the determined closeness scores. While making this determination, the system can additionally consider correlations between words in a title or an anchor of a document and words in the document as well as word-form scores for pairs of words in the documents.

Claims

1. A computer-implemented method comprising:

selecting a pair of words;

receiving a document having an associated title or anchor;

determining that a word of the pair of words occurs in the title or anchor of the document and that a different word of the pair of words occurs within the document;

determining a co-occurrence frequency of the word of the pair of words and the different word of the pair of words in a collection of documents; and

determining that the word and the different word are synonyms based at least upon determining that the word of the pair of words occurs in the title or anchor of the document and that the different word of the pair of words occurs within the document and based at least on the determined co-occurrence frequency of the word of the pair of words and the different word of the pair of words.

2. The method of claim 1, wherein the anchor is a Uniform Resource Locator (URL) anchor.

3. The method of claim 1, further comprising:

generating an alternative search query for a search query that includes the word or the different word using the synonym of the word or the different word.

4. A computer-implemented method comprising:

receiving a first word and a second word;

computing a frequency with which the first word occurs in a collection of documents and a frequency with which the second word occurs in the collection of documents;

determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least a certain amount; and

determining that the pair of words are not synonyms based at least on determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least the certain the amount.

5. The method of claim 4, further comprising:

excluding the pair of words from a list of synonyms used to generate alternative search queries.

6. The method of claim 4, further comprising:

determining a co-occurrence frequency for the pair of words in the collection of documents; and

determining that the pair of words are not synonyms further based at least on the determined co-occurrence frequency.

7. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

selecting a pair of words;

receiving a document having an associated title or anchor;

determining that a word of the pair of words occurs in the title or anchor of the document and that a different word of the pair of words occurs within the document;

determining a co-occurrence frequency of the word of the pair of words and the different word of the pair of words in a collection of documents; and

determining that the word and the different word are synonyms based at least upon determining that the word of the pair of words occurs in the title or anchor of the document and that the different word of the pair of words occurs within the document and based at least on the determined co-occurrence frequency of the word of the pair of words and the different word of the pair of words.

8. The system of claim 7, wherein the anchor is a Uniform Resource Locator (URL) anchor.

9. The system of claim 7, wherein the operations further comprise:

generating an alternative search query for a search query that includes the word or the different word using the synonym of the word or the different word.

10. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a first word and a second word;

computing a frequency with which the first word occurs in a collection of documents and a frequency with which the second word occurs in the collection of documents;

determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least a certain amount; and

determining that the pair of words are not synonyms based at least on determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least the certain amount.

11. The system of claim 10, wherein the operations further comprise:

excluding the pair of words from a list of synonyms used to generate alternative search queries.

12. The system of claim 10, wherein the operations further comprise:

determining a co-occurrence frequency for the pair of words in the collection of documents; and

determining that the pair of words are not synonyms further based at least on the determined co-occurrence frequency.

13. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

selecting a pair of words;

receiving a document having an associated title or anchor;

determining that a word of the pair of words occurs in the title or anchor of the document and that a different word of the pair of words occurs within the document;

determining a co-occurrence frequency of the word of the pair of words and the different word of the pair of words in a collection of documents; and

determining that the word and the different word are synonyms based at least upon determining that the word of the pair of words occurs in the title or anchor of the document and that the different word of the pair of words occurs in text within the document and based at least on the determined co-occurrence frequency of the word of the pair of words and the different word of the pair of words.

14. The computer-readable medium of claim 13, wherein the anchor is a Uniform Resource Locator (URL) anchor.

15. The computer-readable medium of claim 13, wherein the operations further comprise:

generating an alternative search query for a search query that includes the first word or the second word using the synonym of the first word or the second word.

16. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving a first word and a second word;

computing a frequency with which the first word occurs in a collection of documents and a frequency with which the second word occurs in the collection of documents;

determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least a certain amount; and

determining that the pair of words are not synonyms based at least on determining that the frequency with which the first word occurs in the collection of documents is greater than the frequency with which the second word occurs in the collection of documents by at least the certain amount.

17. The computer-readable medium of claim 16, wherein the operations further comprise:

excluding the pair of words from a list of synonyms used to generate alternative search queries.

18. The computer-readable medium of claim 16, wherein the operations further comprise:

determining a co-occurrence frequency for the pair of words in the collection of documents; and

determining that the pair of words are not synonyms further based at least on the determined co-occurrence frequency.