Statistical stemming

• US 8,352,247 B2
• Filed: 04/23/2012
• Issued: 01/08/2013
• Est. Priority Date: 11/05/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cherepanov, Evgeny A., Grushetskyy, Oleksandr, Orlov, Dmitry N.
• Primary Examiner(s): Hudspeth, David R
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US13/453,473
• Publication Number:
  US 20120209592A1
• Time in Patent Office: 260 Days
• Field of Search: 704 1- 10, 707706-708, 715/254, 715/255
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating suffix rewriting rules. A method includes obtaining a plurality of canonical suffix-rewriting rules each associated with one or more words, generating a suffix tree from the words, selecting a minimum colored subset of the nodes and leaves in the suffix tree, and generating a plurality of final suffix-rewriting rules from the nodes in the minimum colored subset. Another method includes receiving applicable and non-applicable words for a suffix-rewriting rule, generating a suffix tree from the applicable words and the non-applicable words, selecting a minimum colored subset of the nodes and leaves in the suffix tree, and generating a plurality of suffix-rewriting rules, wherein each rule corresponds to a node in the minimum colored subset with a valid status.

Claims

1. A computer-implemented method, comprising:

obtaining a plurality of canonical suffix-rewriting rules, each rule associated with one or more words to which the rule applies, wherein each canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the words associated with the canonical suffix-rewriting rules, the suffix tree comprising a plurality of nodes and a plurality of leaves arranged in a hierarchical structure, wherein each node has one or more children below the node in the tree and each child is either a node or a leaf, and wherein each leaf corresponds to a distinct one of the words associated with the canonical suffix-rewriting rules and each node corresponds to a suffix of its children in the tree;

selecting, using one or more processors a minimum colored subset of the nodes and leaves in the suffix tree, wherein each node and leaf in the minimum colored subset is associated with a respective optimal canonical suffix-rewriting rule, wherein the minimum colored subset and optimal canonical suffix-rewriting rules are selected such that a derived canonical suffix-rewriting rule for each leaf matches the canonical suffix-rewriting rule associated with the word corresponding to the leaf, wherein the derived canonical suffix-rewriting rule for each leaf is the optimal canonical suffix-rewriting rule for a first colored ancestor of the leaf in the tree, and wherein the first colored ancestor for a leaf is the leaf, if the leaf is included in the minimum colored subset, and otherwise is a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of final suffix-rewriting rules, each rule mapping a suffix of a node in the minimum colored subset to the suffix of the node with the suffix replacement specified by the canonical rule for the node.

2. The method of claim 1, wherein obtaining the plurality of canonical suffix-rewriting rules comprises:

obtaining a first plurality of word-variant pairs, each pair comprising a word and a variant for the word; and

associating a canonical suffix-rewriting rule with each of the word-variant pairs, including removing a longest common prefix from the word and the variant, and then generating the canonical suffix-rewriting rule from a remaining suffix of the word and a remaining suffix of the variant.

3. The method of claim 2, wherein the variant for each word is a normalized form of the word, and wherein obtaining the first plurality of word-variant pairs comprises:

obtaining a second plurality of word-variant pairs, each second pair comprising a word and a variant for the word, each second pair associated with a confidence measure;

clustering the words in the second plurality of word-variant pairs according to relationships between words and variants in the word-variant pairs;

determining an optimal normalized form for each word in the second plurality of word pairs, the determining including selecting an optimal normalized form for each cluster; and

generating the first plurality of word-variant pairs, each pair associating a word from one of the second word-variant pairs with the optimal normalized form for the cluster for the word.

4. The method of claim 1, wherein selecting the minimum colored subset of the nodes and leaves in the suffix tree comprises determining optimal conditional rules for each node and leaf in the suffix tree, and then selecting the minimum colored subset and the optimal canonical suffix-rewriting rule for each node and leaf in the subset according to the optimal conditional rules.

5. The method of claim 4, wherein:

the optimal conditional rule for a node or leaf is the rule that is optimal for the condition that a parent node of the node or leaf is associated with a particular canonical suffix-rewriting rule; and

selecting an optimal canonical suffix-rewriting rule for each node according to the optimal conditional rules for the node comprises;

determining an optimal canonical suffix-rewriting rule for a root of the suffix tree; and

determining an optimal canonical suffix-rewriting rule for each remaining node in the tree, wherein the optimal canonical suffix-rewriting rule for a node in the tree is the optimal conditional rule for the canonical suffix-rewriting rule associated with a parent of the node.

6. The method of claim 1, further comprising generating a normalized form of a word using one of the plurality of final suffix-rewriting rules.

7. The method of claim 1, further comprising generating a variant for a word using one of the plurality of final suffix-rewriting rules.

8. A computer readable storage medium encoded with a computer program, the computer program comprising computer instructions that, when executed by one or more data processing apparatus, cause the data processing apparatus to perform operations comprising:

obtaining a plurality of canonical suffix-rewriting rules, each rule associated with one or more words to which the rule applies, wherein each canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the words associated with the canonical suffix-rewriting rules, the suffix tree comprising a plurality of nodes and a plurality of leaves arranged in a hierarchical structure, wherein each node has one or more children below the node in the tree and each child is either a node or a leaf, and wherein each leaf corresponds to a distinct one of the words associated with the canonical suffix-rewriting rules and each node corresponds to a suffix of its children in the tree;

selecting a minimum colored subset of the nodes and leaves in the suffix tree, wherein each node and leaf in the minimum colored subset is associated with a respective optimal canonical suffix-rewriting rule, wherein the minimum colored subset and optimal canonical suffix-rewriting rules are selected such that a derived canonical suffix-rewriting rule for each leaf matches the canonical suffix-rewriting rule associated with the word corresponding to the leaf, wherein the derived canonical suffix-rewriting rule for each leaf is the optimal canonical suffix-rewriting rule for a first colored ancestor of the leaf in the tree, and wherein the first colored ancestor for a leaf is the leaf, if the leaf is included in the minimum colored subset, and otherwise is a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of final suffix-rewriting rules, each rule mapping a suffix of a node in the minimum colored subset to the suffix of the node with the suffix replacement specified by the canonical rule for the node.

9. The computer storage medium of claim 8, wherein obtaining the plurality of canonical suffix-rewriting rules comprises:

obtaining a first plurality of word-variant pairs, each pair comprising a word and a variant for the word; and

associating a canonical suffix-rewriting rule with each of the word-variant pairs, including removing a longest common prefix from the word and the variant, and then generating the canonical suffix-rewriting rule from a remaining suffix of the word and a remaining suffix of the variant.

10. The computer storage medium of claim 9, wherein the variant for each word is a normalized form of the word, and wherein obtaining the first plurality of word-variant pairs comprises:

obtaining a second plurality of word-variant pairs, each second pair comprising a word and a variant for the word, each second pair associated with a confidence measure;

clustering the words in the second plurality of word-variant pairs according to relationships between words and variants in the word-variant pairs;

determining an optimal normalized form for each word in the second plurality of word pairs, the determining including selecting an optimal normalized form for each cluster; and

generating the first plurality of word-variant pairs, each pair associating a word from one of the second word-variant pairs with the optimal normalized form for the cluster for the word.

11. The computer storage medium of claim 8, wherein selecting the minimum colored subset of the nodes and leaves in the suffix tree comprises determining optimal conditional rules for each node and leaf in the suffix tree, and then selecting the minimum colored subset and the optimal canonical suffix-rewriting rule for each node and leaf in the subset according to the optimal conditional rules.

12. The computer storage medium of claim 11, wherein:

the optimal conditional rule for a node or leaf is the rule that is optimal for the condition that a parent node of the node or leaf is associated with a particular canonical suffix-rewriting rule; and

selecting an optimal canonical suffix-rewriting rule for each node according to the optimal conditional rules for the node comprises;

determining an optimal canonical suffix-rewriting rule for a root of the suffix tree; and

determining an optimal canonical suffix-rewriting rule for each remaining node in the tree, wherein the optimal canonical suffix-rewriting rule for a node in the tree is the optimal conditional rule for the canonical suffix-rewriting rule associated with a parent of the node.

13. The computer storage medium of claim 12, further operable to cause data processing apparatus to perform operations comprising generating a normalized form of a word using one of the plurality of final suffix-rewriting rules.

14. The computer storage medium of claim 13, further operable to cause data processing apparatus to perform operations comprising generating a variant for a word using one of the plurality of final suffix-rewriting rules.

15. A system, comprising:

a processor; and

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

obtaining a plurality of canonical suffix-rewriting rules, each rule associated with one or more words to which the rule applies, wherein each canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the words associated with the canonical suffix-rewriting rules, the suffix tree comprising a plurality of nodes and a plurality of leaves arranged in a hierarchical structure, wherein each node has one or more children below the node in the tree and each child is either a node or a leaf, and wherein each leaf corresponds to a distinct one of the words associated with the canonical suffix-rewriting rules and each node corresponds to a suffix of its children in the tree;

selecting a minimum colored subset of the nodes and leaves in the suffix tree, wherein each node and leaf in the minimum colored subset is associated with a respective optimal canonical suffix-rewriting rule, wherein the minimum colored subset and optimal canonical suffix-rewriting rules are selected such that a derived canonical suffix-rewriting rule for each leaf matches the canonical suffix-rewriting rule associated with the word corresponding to the leaf, wherein the derived canonical suffix-rewriting rule for each leaf is the optimal canonical suffix-rewriting rule for a first colored ancestor of the leaf in the tree, and wherein the first colored ancestor for a leaf is the leaf, if the leaf is included in the minimum colored subset, and otherwise is a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of final suffix-rewriting rules, each rule mapping a suffix of a node in the minimum colored subset to the suffix of the node with the suffix replacement specified by the canonical rule for the node.

16. The system of claim 15, wherein obtaining the plurality of canonical suffix-rewriting rules comprises:

obtaining a first plurality of word-variant pairs, each pair comprising a word and a variant for the word; and

associating a canonical suffix-rewriting rule with each of the word-variant pairs, including removing a longest common prefix from the word and the variant, and then generating the canonical suffix-rewriting rule from a remaining suffix of the word and a remaining suffix of the variant.

17. The system of claim 16, wherein the variant for each word is a normalized form of the word, and wherein obtaining the first plurality of word-variant pairs comprises:

obtaining a second plurality of word-variant pairs, each second pair comprising a word and a variant for the word, each second pair associated with a confidence measure;

clustering the words in the second plurality of word-variant pairs according to relationships between words and variants in the word-variant pairs;

determining an optimal normalized form for each word in the second plurality of word pairs, the determining including selecting an optimal normalized form for each cluster; and

generating the first plurality of word-variant pairs, each pair associating a word from one of the second word-variant pairs with the optimal normalized form for the cluster for the word.

18. The system of claim 15, wherein selecting the minimum colored subset of the nodes and leaves in the suffix tree comprises determining optimal conditional rules for each node and leaf in the suffix tree, and then selecting the minimum colored subset and the optimal canonical suffix-rewriting rule for each node and leaf in the subset according to the optimal conditional rules.

19. The system of claim 18, wherein:

the optimal conditional rule for a node or leaf is the rule that is optimal for the condition that a parent node of the node or leaf is associated with a particular canonical suffix-rewriting rule; and

selecting an optimal canonical suffix-rewriting rule for each node according to the optimal conditional rules for the node comprises;

determining an optimal canonical suffix-rewriting rule for a root of the suffix tree; and

determining an optimal canonical suffix-rewriting rule for each remaining node in the tree, wherein the optimal canonical suffix-rewriting rule for a node in the tree is the optimal conditional rule for the canonical suffix-rewriting rule associated with a parent of the node.

20. The system of claim 15, further operable to perform operations comprising generating a normalized form of a word using one of the plurality of final suffix-rewriting rules.

21. The system of claim 15, further operable to perform operations comprising generating a variant for a word using one of the plurality of final suffix-rewriting rules.