Document-based synonym generation

• US 7,890,521 B1
• Filed: 02/07/2008
• Issued: 02/15/2011
• Est. Priority Date: 02/07/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Grushetskyy, Oleksandr, Baker, Steven D.
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US12/027,559
• Time in Patent Office: 1,104 Days
• Field of Search: 707/804, 707/811, 707/755, 704/4, 704/10, 704/231, 715/258, 715/260
• US Class Current: 707/755
• 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 method for automatically determining whether pairs of words are synonym pairs, comprising:

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether each of the pairs of words is a synonym pair based on the determined co-occurrence frequencies, the determined closeness scores, and the correlations, wherein a high closeness score is a negative indicator that a pair of words is a synonym pair, a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair;

wherein the determining co-occurrence frequencies, determining closeness scores, generating correlations, and determining whether each of the pairs of words is a synonym pair is performed by a computer system.

2. The method of claim 1, wherein determining a closeness score for a pair of words includes dividing the probability that the words are very close to each other by the probability that the words are near each other.

3. The method of claim 2, wherein words are determined to be very close to each other if they are less than a small number of words apart;

and wherein words are determined to be near each other if they are within a pre-specified number of words of each other.

4. The method of claim 3, wherein the small number of words apart is about 4 words;

and wherein the pre-specified number of words is about 100 words.

5. The method of claim 1, further comprising:

determining word-form scores for pairs of words, wherein a high word-form score results when a pair of words share common parts, which can include prefixes, suffixes and/or middle sections, and wherein remaining parts of the pair of words are consistent with word-form rules;

wherein determining whether each of the pairs of words is a synonym pair is further based on the word-form scores.

6. The method of claim 1, wherein the method further comprises automatically generating the word-form rules from synonymous words that share common parts, which can include prefixes, suffixes and/or middle sections.

7. The method of claim 1, further comprising:

determining whether a candidate word in a pair of words is a synonym for a target word in the pair of words, the determining comprising;

considering whether the candidate word is much more common than the target word, in which case the candidate word is not a synonym because search results produced by the candidate word will overwhelm search results produced by the target word; and

considering whether the candidate word is much less common than the target word in which case the candidate word is not a synonym because using the candidate word will produce very few additional search results.

8. The method of claim 1, wherein the method further comprises:

receiving a query containing words;

using the synonym pairs to identify one or more synonyms for the one or more words in the query;

generating an altered query using the one or more synonyms; and

using the altered query to produce search results.

9. A method for automatically determining whether pairs of words are synonym pairs, comprising:

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

determining word-form scores for pairs of words in the documents, wherein a high word-form score results when a pair of words share common parts, which can include prefixes, suffixes and/or middle sections, and wherein remaining parts of the pair of words are consistent with word-form rules;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether pairs of words are synonyms based on the determined co-occurrence frequencies, the determined closeness scores, the determined word-form scores, and the generated correlations, wherein a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, a high closeness score is a negative indicator that a pair of words is a synonym pair, a high word-form score is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair;

wherein the determining co-occurrence frequencies, determining closeness scores, generating correlations, and determining whether each of the pairs of words is a synonym pair is performed by a computer system.

10. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform operations comprising:

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether each of the pairs of words is a synonym pair based on the determined co-occurrence frequencies, the determined closeness scores, and the correlations, wherein a high closeness score is a negative indicator that a pair of words is a synonym pair, a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair.

11. The computer-readable storage medium of claim 10, wherein determining a closeness score for a pair of words includes dividing the probability that the words are very close to each other by the probability that the words are near each other.

12. The computer-readable storage medium of claim 11,

wherein words are determined to be very close to each other if they are less than a small number of words apart, such as 4 words;

and

wherein words are determined to be near each other if they are within a pre-specified number of words of each other, such as 100 words.

13. The computer-readable storage medium of claim 12,

wherein the small number of words apart is about 4 words;

and

wherein the pre-specified number of words is about 100 words.

14. The computer-readable storage medium of claim 10, wherein determining whether pairs of words are synonyms additionally involves:

determining word-form scores for pairs of words, wherein a high word-form score results when a pair of words share common parts, which can include prefixes, suffixes and/or middle sections, and wherein remaining parts of the pair of words are consistent with word-form rules; and

analyzing the word-form scores when determining whether pairs of words are synonym pairs.

15. The computer-readable storage medium of claim 10, wherein the method further comprises automatically generating the word-form rules from synonymous words that share common parts, which can include prefixes, suffixes and/or middle sections.

16. The computer-readable storage medium of claim 10, further operable to perform operations comprising:

determining whether a candidate word in a pair of words is a synonym for a target word in a pair of words, the determining comprising;

considering whether the candidate word is much more common than the target word, in which case the candidate word is not a synonym because search results produced by the candidate word will overwhelm search results produced by the target word; and

considering whether the candidate word is much less common than the target word in which case the candidate word is not a synonym because using the candidate word will produce very few additional search results.

17. The computer-readable storage medium of claim 10, further operable to perform operations comprising:

receiving a query containing words;

using the synonym pairs to identify one or more synonyms for the one or more words in the query;

generating an altered query using the one or more synonyms; and

using the altered query to produce search results.

18. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform operations comprising:

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

determining word-form scores for pairs of words in the documents, wherein a high word-form score results when a pair of words share common parts, which can include prefixes, suffixes and/or middle sections, and wherein remaining parts of the pair of words are consistent with word-form rules;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether pairs of words are synonyms based on the determined co-occurrence frequencies, the determined closeness scores, the determined word-form scores, and the generated correlations, the determined word-form scores, and the generated correlations, wherein a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, a high closeness score is a negative indicator that a pair of words is a synonym pair, a high word-form score is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair.

19. A system, comprising:

one or more computers configured to perform operations comprising;

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether each of the pairs of words is a synonym pair based on the determined co-occurrence frequencies, the determined closeness scores, and the correlations, wherein a high closeness score is a negative indicator that a pair of words is a synonym pair, a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair;

wherein the determining co-occurrence frequencies, determining closeness scores, generating correlations, and determining whether each of the pairs of words is a synonym pair is performed by a computer system.

20. A system, comprising:

one or more computers configured to perform operations comprising;

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

determining word-form scores for pairs of words in the documents, wherein a high word-form score results when a pair of words share common parts, which can include prefixes, suffixes and/or middle sections, and wherein remaining parts of the pair of words are consistent with word-form rules;

generating correlations between (i) words in a title or an anchor of each document in the documents and (ii) words in the document; and

determining whether pairs of words are synonyms based on the determined co-occurrence frequencies, the determined closeness scores, the determined word-form scores, and the generated correlations, wherein a high co-occurrence frequency is a positive indicator that the pair of words is a synonym pair, a high closeness score is a negative indicator that a pair of words is a synonym pair, a high word-form score is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair;

wherein the determining co-occurrence frequencies, determining closeness scores, generating correlations, and determining whether each of the pairs of words is a synonym pair is performed by a computer system.

21. A computer implemented method for automatically determining whether pairs of words are synonym pairs, comprising:

determining, for a pair of words, a co-occurrence frequency of the pair of words in a plurality of documents;

determining a closeness score for the pair of words in the plurality of documents, wherein the closeness score is derived from how close a first and a second word appear to each other in the plurality of documents;

generating a correlation between (i) one of the words in each pair of words appearing in a title or anchor of each of one or more documents and (ii) another word in the pair of words appearing in each of the one or more documents;

determining whether the pair of words is a synonym pair according to the co-occurrence frequency, the closeness score, and the correlation, wherein a high closeness score is a negative indicator that the pair of words is a synonym pair, a high co occurrence frequency is a positive indicator that the pair of words is a synonym pair, and a high correlation is a positive indicator that the pair of words is a synonym pair.

22. A computer-implemented method for automatically determining whether pairs of words are synonym pairs, comprising:

determining co-occurrence frequencies for pairs of words in documents;

determining closeness scores for pairs of words in the documents, wherein a closeness score indicates whether words in a pair of words are located so close to each other in the documents that the words are likely to occur in the same sentence or phrase;

determining word-form scores for pairs of words in the documents, wherein a word-form score specifies an extent to which a pair of words share common parts and an extent to which, which can include prcfixcs, cuffixcs and/or remaining parts of the pair of words are consistent with word-form rules, wherein the common parts include one or more prefixes, suffixes, and middle sections, and wherein a word-form rule designates acceptable variations among words that share a common stem; and

determining whether each of the pairs of words is a synonym pair based on the determined co-occurrence frequencies, the determined closeness scores, and an analysis of the word-form scores.