Synonym generation using online decompounding and transitivity

• US 8,392,441 B1
• Filed: 08/13/2010
• Issued: 03/05/2013
• Est. Priority Date: 08/15/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Papachristou, Dimitra, Popovici, Dan, Martensson, Lina C., Carattini, Kendra J.
• Primary Examiner(s): Ng, Amy
• Application Number:
  US12/856,537
• Time in Patent Office: 935 Days
• Field of Search: 707/759, 707/765
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for query synonym expansion. One method includes receiving a query including a first compound term, and in response to receiving the query, performing the following operations: generating one or more splits of the first compound term, assigning a score to each subterm of each split, determining an overall score for each split from the scores for the subterms of the split, selecting a first split from the one or more splits according to the overall score for each split, and augmenting the query with a first synonym phrase that is a synonym of a first subterm of the first split.

Claims

1. A system comprising:

one or more processors; and

a computer-readable storage device storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving a query submitted by a user to a search engine, wherein the query includes a first compound term; and

in response to receiving the query, performing the following operations;

generating one or more splits of the first compound term, wherein each split divides the compound term into two or more subterms, wherein at least one subterm is a term in a dictionary that associates terms with scores derived from a respective frequency of use of the subterm;

assigning a score to one or more subterms of each split that are in the dictionary, wherein the score for a subterm is the score stored in the dictionary for the subterm;

determining an overall score for each split from the scores for the subterms of the split;

selecting a first split from the one or more splits according to the overall score for each split; and

augmenting the query with a first synonym phrase, wherein the first synonym phrase is a synonym of a first subterm of the first split.

2. The system of claim 1, wherein selecting the first split according to the overall scores comprises selecting the split with a highest overall score.

3. The system of claim 1, wherein generating one or more splits of the first compound term comprises incrementally analyzing prefixes of increasing length of the first compound term to identify subterms of the prefixes that appear in the dictionary.

4. The system of claim 1, wherein the plurality of splits includes a split in which each subterm is a term in the dictionary.

5. The system of claim 1, wherein the plurality of splits includes a split in which one subterm is a term in the dictionary, and another subterm is not in the dictionary.

6. The system of claim 1, wherein the score for a subterm that is not in the dictionary is a default score.

7. The system of claim 1, wherein the score associated with each term in the dictionary is derived from a frequency with which the term is used in a particular corpus of documents.

8. The system of claim 1, wherein determining an overall score for each split from the scores for the subterms of the split comprises summing the scores for the subterms of the split.

9. The system of claim 1, wherein the operations further comprise augmenting the query with an additional synonym phrase that is a synonym for the first synonym phrase.

10. The system of claim 1, wherein the operations further comprise augmenting the query with a second synonym phrase, wherein the second synonym phrase is a synonym of the first subterm of the first split.

11. The system of claim 1, wherein the operations further comprise augmenting the query with a third synonym phrase, wherein the third synonym phrase is a synonym of a second subterm of the first split.

12. The system of claim 1, wherein the operations further comprise providing search results responsive to the augmented query to the user.

13. A non-transitory computer-readable storage device storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

receiving a query submitted by a user to a search engine, wherein the query includes a first compound term; and

in response to receiving the query, performing the following operations;

generating one or more splits of the first compound term, wherein each split divides the compound term into two or more subterms, wherein at least one subterm is a term in a dictionary that associates terms with scores derived from a respective frequency of use of the subterm;

assigning a score to one or more subterms of each split that are in the dictionary, wherein the score for a subterm is the score stored in the dictionary for the subterm;

determining an overall score for each split from the scores for the subterms of the split;

selecting a first split from the one or more splits according to the overall score for each split; and

augmenting the query with a first synonym phrase, wherein the first synonym phrase is a synonym of a first subterm of the first split.

14. The non-transitory computer-readable storage device of claim 13, wherein selecting the first split according to the overall scores comprises selecting the split with a highest overall score.

15. The non-transitory computer-readable storage device of claim 13, wherein generating one or more splits of the first compound term comprises incrementally analyzing prefixes of increasing length of the first compound term to identify subterms of the prefixes that appear in the dictionary.

16. The non-transitory computer-readable storage device of claim 13, wherein the score for a subterm that is not in the dictionary is a default score.

17. The non-transitory computer-readable storage device of claim 13, wherein the score associated with each term in the dictionary is derived from a frequency with which the term is used in a particular corpus of documents.

18. The non-transitory computer-readable storage device of claim 13, wherein determining an overall score for each split from the scores for the subterms of the split comprises summing the scores for the subterms of the split.

19. The non-transitory computer-readable storage device of claim 13, wherein the operations further comprise augmenting the query with an additional synonym phrase that is a synonym for the first synonym phrase.

20. The non-transitory computer-readable storage device of claim 13, wherein the operations further comprise augmenting the query with a second synonym phrase, wherein the second synonym phrase is a synonym of the first subterm of the first split.

21. The non-transitory computer-readable storage device of claim 13, wherein the operations further comprise augmenting the query with a third synonym phrase, wherein the third synonym phrase is a synonym of a second subterm of the first split.

22. The non-transitory computer-readable storage device of claim 13, wherein the operations further comprise providing search results responsive to the augmented query to the user.

33. The computer-readable storage device of claim 13, wherein the plurality of splits includes a split in which each subterm is a term in the dictionary.

34. The computer-readable storage device of claim 13, wherein the plurality of splits includes a split in which one subterm is a term in the dictionary, and another subterm is not in the dictionary.

23. A computer-implemented method, comprising:

receiving a query submitted by a user to a search engine, wherein the query includes a first compound term; and

in response to receiving the query, performing the following operations;

generating one or more splits of the first compound term, wherein each split divides the compound term into two or more subterms, wherein at least one subterm is a term in a dictionary that associates terms with scores derived from a respective frequency of use of the subterm;

assigning a score to one or more subterms of each split that are in the dictionary, wherein the score for a subterm is the score stored in the dictionary for the subterm;

determining an overall score for each split from the scores for the subterms of the split;

selecting a first split from the one or more splits according to the overall score for each split; and

augmenting the query with a first synonym phrase, wherein the first synonym phrase is a synonym of a first subterm of the first split.

24. The method of claim 23, wherein selecting the first split according to the overall scores comprises selecting the split with a highest overall score.

25. The method of claim 23, wherein generating one or more splits of the first compound term comprises incrementally analyzing prefixes of increasing length of the first compound term to identify subterms of the prefixes that appear in the dictionary.

26. The method of claim 23, wherein the score for a subterm that is not in the dictionary is a default score.

27. The method of claim 23, wherein the score associated with each term in the dictionary is derived from a frequency with which the term is used in a particular corpus of documents.

28. The method of claim 23, wherein determining an overall score for each split from the scores for the subterms of the split comprises summing the scores for the subterms of the split.

29. The method of claim 23, further comprising augmenting the query with an additional synonym phrase that is a synonym for the first synonym phrase.

30. The method of claim 23, further comprising augmenting the query with a second synonym phrase, wherein the second synonym phrase is a synonym of the first subterm of the first split.

31. The method of claim 23, further comprising augmenting the query with a third synonym phrase, wherein the third synonym phrase is a synonym of a second subterm of the first split.

32. The method of claim 23, further comprising providing search results responsive to the augmented query to the user.

35. The method of claim 23, wherein the plurality of splits includes a split in which each subterm is a term in the dictionary.

36. The method of claim 23, wherein the plurality of splits includes a split in which one subterm is a term in the dictionary, and another subterm is not in the dictionary.