STATISTICAL STEMMING
First Claim
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 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification