Statistical stemming

• US 8,554,543 B2
• Filed: 12/10/2012
• Issued: 10/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): SPOONER, LAMONT M
• Application Number:
  US13/710,055
• Publication Number:
  US 20130173250A1
• Time in Patent Office: 302 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:

receiving, for a canonical suffix-rewriting rule, a plurality of applicable words and a plurality of non-applicable words, wherein each applicable word is a word to which the rule should be applied, and each non-applicable word is a word to which the rule should not be applied, and wherein the canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the applicable words and the non-applicable words, 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 nodes or one or more leaves below the node in the tree, wherein each leaf corresponds to either a unique applicable word or a unique non-applicable word, 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 has an associated optimal status, wherein the minimum colored subset and the optimal status of each node and leaf in the minimum colored subset are selected such that a derived status for each leaf is valid when the leaf corresponds to an applicable word, and the derived status for each leaf is not valid when the leaf corresponds to a non-applicable word, wherein the derived status for each leaf is the optimal status for the leaf if the leaf is included in the minimum colored subset, and otherwise is the optimal status of a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of suffix-rewriting rules, wherein each rule corresponds to a node in the minimum colored subset with a valid status, and maps the suffix of the node to the suffix of the node with the replacement specified by the suffix-rewriting rule.

2. The method of claim 1, wherein the optimal status for each node or leaf in the minimum colored subset is valid or invalid.

3. The method of claim 1, wherein selecting the minimum colored subset of the nodes and leaves and the optimal status for each node and leaf in the minimum colored subset comprises determining optimal conditional statuses for each node and leaf in the suffix tree, and then determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses.

4. The method of claim 3, wherein:

the optimal conditional statuses include a optimal conditional status for the node for the condition where a parent node of the node has a valid status and an optimal conditional status for the condition where a parent node of the node has an invalid status; and

determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses comprises;

determining whether the root of the suffix tree has an invalid or valid status from the optimal conditional status for the root; and

determining, for each remaining node and leaf in the tree, whether the node or leaf has a valid status, invalid status, or uncolored status according to the optimal conditional status for the node or leaf that corresponds to whether a parent node is valid or invalid; and

wherein nodes and leaves having valid and invalid status are in the minimum colored subset.

5. The method of claim 1, further comprising receiving a plurality of uncolored words that are neither applicable nor non-applicable words for the rule, and wherein:

each leaf corresponds to an applicable word, a non-applicable word, or an uncolored word; and

the minimum colored subset and the optimal status of each node and leaf in the minimum colored subset are selected such that a derived status for each leaf corresponding to an uncolored word is either valid or invalid.

6. The method of claim 1, wherein receiving the plurality of applicable words and the plurality of non-applicable words for the canonical suffix-rewriting rule comprises:

obtaining a plurality of applicable pairs and a plurality of non-applicable pairs, wherein each applicable pair includes a word and a valid variant of the word, and each non-applicable pair includes a word and a non-valid variant of the word;

identifying one or more applicable pairs for the canonical suffix-rewriting rule and one or more non-applicable pairs for the suffix-rewriting rule, wherein identifying a pair for the canonical suffix-rewriting rule comprises matching the suffix replacement of the canonical suffix-rewriting rule to the word and the variant of the pair; and

associating the word in each applicable pair for the canonical suffix-rewriting rule with the rule as an applicable word, and associating the word in each non-applicable pair for the canonical suffix-rewriting rule with the rule as a non-applicable word.

7. The method of claim 1, wherein generating a suffix-rewriting rule for a node in the minimum colored subset with a valid status further comprises determining a confidence measure for the rule, wherein the confidence measure is derived from confidence measures of valid leaves below the node in the suffix tree.

8. The method of claim 1, wherein the suffix-rewriting rules include rules that correspond to a node with an invalid status and maps the suffix of the invalid node to the suffix of the invalid node with the replacement specified by the suffix-rewriting rule, and wherein each rule that corresponds to a node with an invalid status has a confidence measure below a threshold.

9. 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, for a canonical suffix-rewriting rule, a plurality of applicable words and a plurality of non-applicable words, wherein each applicable word is a word to which the rule should be applied, and each non-applicable word is a word to which the rule should not be applied, and wherein the canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the applicable words and the non-applicable words, 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 nodes or one or more leaves below the node in the tree, wherein each leaf corresponds to either a unique applicable word or a unique non-applicable word, 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 has an associated optimal status, wherein the minimum colored subset and the optimal status of each node and leaf in the minimum colored subset are selected such that a derived status for each leaf is valid when the leaf corresponds to an applicable word, and the derived status for each leaf is not valid when the leaf corresponds to a non-applicable word, wherein the derived status for each leaf is the optimal status for the leaf if the leaf is included in the minimum colored subset, and otherwise is the optimal status of a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of suffix-rewriting rules, wherein each rule corresponds to a node in the minimum colored subset with a valid status, and maps the suffix of the node to the suffix of the node with the replacement specified by the suffix-rewriting rule.

10. The system of claim 9, wherein the optimal status for each node or leaf in the minimum colored subset is valid or invalid.

11. The system of claim 9, wherein selecting the minimum colored subset of the nodes and leaves and the optimal status for each node and leaf in the minimum colored subset comprises determining optimal conditional statuses for each node and leaf in the suffix tree, and then determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses.

12. The system of claim 11, wherein:

the optimal conditional statuses include a optimal conditional status for the node for the condition where a parent node of the node has a valid status and an optimal conditional status for the condition where a parent node of the node has an invalid status; and

determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses comprises;

determining whether the root of the suffix tree has an invalid or valid status from the optimal conditional status for the root; and

determining, for each remaining node and leaf in the tree, whether the node or leaf has a valid status, invalid status, or uncolored status according to the optimal conditional status for the node or leaf that corresponds to whether a parent node is valid or invalid; and

wherein nodes and leaves having valid and invalid status are in the minimum colored subset.

13. The system of claim 9, wherein the operations further comprise receiving a plurality of uncolored words that are neither applicable nor non-applicable words for the rule, and wherein:

each leaf corresponds to an applicable word, a non-applicable word, or an uncolored word; and

the minimum colored subset and the optimal status of each node and leaf in the minimum colored subset are selected such that a derived status for each leaf corresponding to an uncolored word is either valid or invalid.

14. The system of claim 9, wherein receiving the plurality of applicable words and the plurality of non-applicable words for the canonical suffix-rewriting rule comprises:

obtaining a plurality of applicable pairs and a plurality of non-applicable pairs, wherein each applicable pair includes a word and a valid variant of the word, and each non-applicable pair includes a word and a non-valid variant of the word;

identifying one or more applicable pairs for the canonical suffix-rewriting rule and one or more non-applicable pairs for the suffix-rewriting rule, wherein identifying a pair for the canonical suffix-rewriting rule comprises matching the suffix replacement of the canonical suffix-rewriting rule to the word and the variant of the pair; and

associating the word in each applicable pair for the canonical suffix-rewriting rule with the rule as an applicable word, and associating the word in each non-applicable pair for the canonical suffix-rewriting rule with the rule as a non-applicable word.

15. The system of claim 9, wherein generating a suffix-rewriting rule for a node in the minimum colored subset with a valid status further comprises determining a confidence measure for the rule, wherein the confidence measure is derived from confidence measures of valid leaves below the node in the suffix tree.

16. The system of claim 9, wherein the suffix-rewriting rules include rules that correspond to a node with an invalid status and maps the suffix of the invalid node to the suffix of the invalid node with the replacement specified by the suffix-rewriting rule, and wherein each rule that corresponds to a node with an invalid status has a confidence measure below a threshold.

17. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving, for a canonical suffix-rewriting rule, a plurality of applicable words and a plurality of non-applicable words, wherein each applicable word is a word to which the rule should be applied, and each non-applicable word is a word to which the rule should not be applied, and wherein the canonical suffix-rewriting rule specifies a suffix replacement;

generating a suffix tree from the applicable words and the non-applicable words, 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 nodes or one or more leaves below the node in the tree, wherein each leaf corresponds to either a unique applicable word or a unique non-applicable word, 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 has an associated optimal status, wherein the minimum colored subset and the optimal status of each node and leaf in the minimum colored subset are selected such that a derived status for each leaf is valid when the leaf corresponds to an applicable word, and the derived status for each leaf is not valid when the leaf corresponds to a non-applicable word, wherein the derived status for each leaf is the optimal status for the leaf if the leaf is included in the minimum colored subset, and otherwise is the optimal status of a first node above the leaf in the tree that is in the minimum colored subset; and

generating a plurality of suffix-rewriting rules, wherein each rule corresponds to a node in the minimum colored subset with a valid status, and maps the suffix of the node to the suffix of the node with the replacement specified by the suffix-rewriting rule.

18. The computer program product of claim 17, wherein the optimal status for each node or leaf in the minimum colored subset is valid or invalid.

19. The computer program product of claim 17, wherein selecting the minimum colored subset of the nodes and leaves and the optimal status for each node and leaf in the minimum colored subset comprises determining optimal conditional statuses for each node and leaf in the suffix tree, and then determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses.

20. The computer program product of claim 19, wherein:

the optimal conditional statuses include a optimal conditional status for the node for the condition where a parent node of the node has a valid status and an optimal conditional status for the condition where a parent node of the node has an invalid status; and

determining whether to include each node and leaf in the minimum colored subset and determining the optimal status for each node and leaf in the minimum colored subset according to the optimal conditional statuses comprises;

determining whether the root of the suffix tree has an invalid or valid status from the optimal conditional status for the root; and

determining, for each remaining node and leaf in the tree, whether the node or leaf has a valid status, invalid status, or uncolored status according to the optimal conditional status for the node or leaf that corresponds to whether a parent node is valid or invalid; and

wherein nodes and leaves having valid and invalid status are in the minimum colored subset.