Behavior-driven multilingual stemming

• US 8,793,120 B1
• Filed: 10/28/2010
• Issued: 07/29/2014
• Est. Priority Date: 10/28/2010
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Rose, Daniel E., Goswami, Anjan, Fliedner, Gerhard, Sundaramurthy, Swaminathan, Subramanian, Anuradha
• Primary Examiner(s): YEN, ERIC L
• Application Number:
  US12/914,934
• Time in Patent Office: 1,370 Days
• Field of Search: 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

User behavior data can be used with language-specific rule sets to generate stemming databases useful for such tasks as indexing and search query processing. The terms contained in user queries, as well as user behavior with respect to those queries or results returned for those queries, can be analyzed to determine a relative measure (e.g., relative frequency) of various forms of those terms. When generating a stemming database, language-specific rule sets can be used to determine appropriate stemming rules, and where more than one potential rule is identified the user behavior data can be used to select what is likely the appropriate rule, at least for the respective environment. Whitelists or other such components can be used to handle specific or irregular forms that do not follow the general rules or otherwise are exceptions that might not otherwise be processed correctly.

Claims

1. A computer-implemented method of stemming terms using behavioral data, comprising:

under control of one or more computer systems configured with executable instructions,

capturing behavioral data for a plurality of users with respect to a plurality of terms;

obtaining a rule set for stemming in a language, the language including the plurality of terms;

obtaining a word to be stemmed;

in response to determining that only one rule of the rule set is to be used to stem the obtained word, stemming the obtained word using only one rule;

or

in response to determining that more than one rule of the rule set is to be used to stem the obtained word;

determining a set of forms of the obtained word;

determining an output set of forms corresponding to the set of forms, wherein each rule of the more than one rule corresponds to one of the forms in the output set of forms,

determining, based at least in part upon the captured behavioral data, a relative measurement value of each form in the output set of forms, wherein each of the relative measurement values corresponds to an indication of a frequency of use of a corresponding one of the forms in the output set of forms, and

selecting, based at least in part upon the relative measurement values, at least one form in the output set of forms to be used as a stem for the obtained word.

2. The computer-implemented method of claim 1, wherein the word to be stemmed is obtained from a data store storing the behavioral data.

3. The computer-implemented method of claim 1, wherein the stem for the word is stored to a language-specific stemming database.

4. The computer-implemented method of claim 1, further comprising:

generating a whitelist for a plurality of words not having an appropriate rule in the rule set.

5. The computer-implemented method of claim 1, wherein the plurality of terms correspond to search terms contained in search queries submitted by the users.

6. The computer-implemented method of claim 1, wherein each of the relative measurement values corresponds to an indication of a frequency of use of one of the forms in the output set.

7. The computer-implemented method of claim 6, further comprising:

filtering out forms having a frequency that does not at least meet a minimum frequency threshold.

8. The computer-implemented method of claim 1, further comprising:

processing the obtained word by at least one of tokenizing or stop wording the obtained word, before determining that one or more rules are used to stem the rule.

9. A system for stemming terms using behavioral data, comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the system to;

capture behavioral data for a plurality of users with respect to a plurality of terms;

obtain a rule set for stemming in a language, the language including the plurality of terms;

obtain a word to be stemmed;

in response to determining that only one rule of the rule set is to be used to stem the obtained word, stemming the obtained word using only one rule;

or

in response to determining that more than one rule of the rule set is to be used in stemming the obtained word;

determine a set of forms of the obtained word;

determine an output set of forms corresponding to the set of forms, wherein each rule of the more than one rule corresponds to one of the forms in the output set of forms,

determine, based at least in part upon the captured behavioral data, a relative measurement value of each form in the set of output forms, and

select, based at least in part upon the relative measurement values, at least one form in the output set of forms to be used as a stem for the obtained word.

10. The system of claim 9, wherein the word to be stemmed is obtained from a data store storing the behavioral data.

11. The system of claim 9, wherein the stem for the word is stored to a language-specific stemming database.

12. The system of claim 9, wherein the plurality of terms correspond to search terms contained in search queries submitted by the users.

13. The system of claim 9, wherein each of the relative measurement values corresponds to an indication of a frequency of use of one of the forms in the output set based on the captured behavioral data.

14. The system of claim 9, wherein the memory device further cause the system to generate a whitelist for a plurality of words not having an appropriate rule in the rule set.

15. The system of claim 9, wherein the memory device further cause the system to filter out forms having a frequency that does not at least meet a minimum frequency threshold.

16. The system of claim 9, wherein the memory device further cause the system to process the obtained word before determining the rule by at least one of tokenizing or stop wording the obtained word.

17. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor, cause the at least one processor to:

capture behavioral data for a plurality of users with respect to a plurality of terms;

obtain a rule set for stemming in a language corresponding to the plurality of terms;

obtain a word to be stemmed;

in response to determining that only one rule of the rule set is to be used to stem the obtained word, stemming the obtained word using only one rule;

or

in response to determining that more than one rule of the rule set is to be used in stemming the obtained word;

determine a set of forms of the obtained word;

determine an output set of forms corresponding to the set of forms, wherein each rule of the more than one rule corresponds to one of the forms in the output set of forms,

determine, based at least in part upon the captured behavioral data, a relative measurement value of each form in the set of output forms, and

select, based at least in part upon the relative measurement values, at least one form in the output set of forms to be used as a stem for the obtained word.

18. The non-transitory computer-readable storage medium of claim 17, wherein the word to be stemmed is obtained from a data store storing the behavioral data.

19. The non-transitory computer-readable storage medium of claim 17, wherein the plurality of terms correspond to search terms contained in search queries submitted by the users.

20. The non-transitory computer-readable storage medium of claim 17, wherein each of the relative measure values corresponds to an indication of a frequency of use of one of the forms in the output set based in part on the captured behavioral data.

21. The non-transitory computer-readable storage medium of claim 17, wherein the stem for the word is stored to a language-specific stemming database.

22. The non-transitory computer-readable storage medium of claim 17, further cause the at least one processor to generate a whitelist for a plurality of words not having an appropriate rule in the rule set.

23. The non-transitory computer-readable storage medium of claim 17, further cause the at least one processor to filter out forms having a frequency that does not at least meet a minimum frequency threshold.

24. The non-transitory computer-readable storage medium of claim 17, further cause the at least one processor to process the obtained word before determining the rule by at least one of tokenizing or stop wording the obtained word.