Pattern Recognition Using Transition Table Templates
First Claim
1. A computer-implemented method, comprising:
- receiving, in a data processing apparatus, a transition table for a current state of a finite automaton, the finite automaton configured to match patterns in input data, the transition table storing, for each possible next element in the input data, a corresponding next state of the finite automaton;
determining, with the data processing apparatus, whether the transition table for the current state is similar to any transition table template in a set of transition table templates, each transition table template being a transition table for a respective different state of the finite automaton, where the transition table is similar to a transition table template when a difference region for the transition table and the transition table template has a size satisfying a threshold, the difference region being a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template;
in response to determining that the transition table is similar to a transition table template in the set of transition table templates, generating, with the data processing apparatus, a condensed representation of the transition table, the condensed representation including a reference to the similar transition table template, an identification of the difference region, and the next states in the difference region of the transition table; and
in response to determining that the transition table is not similar to any transition table template in the set of transition table templates, adding, in the data processing apparatus, the transition table to the set of transition table templates.
11 Assignments
0 Petitions
Accused Products
Abstract
Methods, systems, and apparatus, including computer programs encoded on computer storage media, for using transition table templates. In one aspect, a method includes receiving a transition table for a current state of a finite automaton and determining whether the transition table for the current state is similar to a transition table template in a set of transition table templates. The method further includes generating a condensed representation of the transition table if the transition table is similar to a transition table template and otherwise adding the transition table to the set of transition table templates. In another aspect, a method includes receiving an input element and determining whether a next state corresponding to the input element is in the difference region of a condensed transition table. The method further includes retrieving the next state from the difference region, or a transition table template, based on the determination.
-
Citations
22 Claims
-
1. A computer-implemented method, comprising:
-
receiving, in a data processing apparatus, a transition table for a current state of a finite automaton, the finite automaton configured to match patterns in input data, the transition table storing, for each possible next element in the input data, a corresponding next state of the finite automaton; determining, with the data processing apparatus, whether the transition table for the current state is similar to any transition table template in a set of transition table templates, each transition table template being a transition table for a respective different state of the finite automaton, where the transition table is similar to a transition table template when a difference region for the transition table and the transition table template has a size satisfying a threshold, the difference region being a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; in response to determining that the transition table is similar to a transition table template in the set of transition table templates, generating, with the data processing apparatus, a condensed representation of the transition table, the condensed representation including a reference to the similar transition table template, an identification of the difference region, and the next states in the difference region of the transition table; and in response to determining that the transition table is not similar to any transition table template in the set of transition table templates, adding, in the data processing apparatus, the transition table to the set of transition table templates. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A system, comprising:
-
a processor; and a computer storage medium coupled to the processor and including instructions, which, when executed by the processor, causes the processor to perform operations comprising; receiving a transition table for a current state of a finite automaton, the finite automaton configured to match patterns in input data, the transition table storing, for each possible next element in the input data, a corresponding next state of the finite automaton; determining whether the transition table for the current state is similar to any transition table template in a set of transition table templates, each transition table template being a transition table for a respective different state of the finite automaton, where the transition table is similar to a transition table template when a difference region for the transition table and the transition table template has a size satisfying a threshold, the difference region being a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; in response to determining that the transition table is similar to a transition table template in the set of transition table templates, generating a condensed representation of the transition table, the condensed representation including a reference to the similar transition table template, an identification of the difference region, and the next states in the difference region of the transition table; and in response to determining that the transition table is not similar to any transition table template in the set of transition table templates, adding the transition table to the set of transition table templates.
-
-
10. A computer storage medium encoded with a computer program, the computer program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform actions comprising:
-
receiving a transition table for a current state of a finite automaton, the finite automaton configured to match patterns in input data, the transition table storing, for each possible next element in the input data, a corresponding next state of the finite automaton; determining whether the transition table for the current state is similar to any transition table template in a set of transition table templates, each transition table template being a transition table for a respective different state of the finite automaton, where the transition table is similar to a transition table template when a difference region for the transition table and the transition table template has a size satisfying a threshold, the difference region being a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; in response to determining that the transition table is similar to a transition table template in the set of transition table templates, generating a condensed representation of the transition table, the condensed representation including a reference to the similar transition table template, an identification of the difference region, and the next states in the difference region of the transition table; and in response to determining that the transition table is not similar to any transition table template in the set of transition table templates, adding the transition table to the set of transition table templates.
-
-
11. A computer-implemented method, comprising:
-
storing, in a data processing apparatus, a current state of a finite automaton and a condensed transition table for the current state, the finite automaton configured to match patterns in input data, the condensed transition table indicating, for each possible next element in the input data, a corresponding next state of the finite automaton, the condensed representation including a reference to a transition table template, an identification of a difference region for the transition table and the transition table template, and a difference table storing the next states of the difference region of the transition table, where the difference region is a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; receiving, in the data processing apparatus, an input element; determining, with the data processing apparatus, a next state for the finite automaton, the determining including; determining whether a next state corresponding to the input element is in the difference region; in response to determining that the next state corresponding to the input element is not in the difference region, retrieving the next state from the transition table template; and in response to determining that the next state corresponding to the input element is in the difference region, retrieving the next state from the difference table; and updating the current state of the finite automaton to be the next state. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A system, comprising:
-
a processor; and a computer storage medium coupled to the processor and including instructions, which, when executed by the processor, causes the processor to perform operations comprising; storing a current state of a finite automaton and a condensed transition table for the current state, the finite automaton configured to match patterns in input data, the condensed transition table indicating, for each possible next element in the input data, a corresponding next state of the finite automaton, the condensed representation including a reference to a transition table template, an identification of a difference region for the transition table and the transition table template, and a difference table storing the next states of the difference region of the transition table, where the difference region is a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; receiving an input element; determining a next state for the finite automaton, the determining including; determining whether a next state corresponding to the input element is in the difference region; in response to determining that the next state corresponding to the input element is not in the difference region, retrieving the next state from the transition table template; and in response to determining that the next state corresponding to the input element is in the difference region, retrieving the next state from the difference table; and updating the current state of the finite automaton to be the next state.
-
-
20. A computer storage medium encoded with a computer program, the computer program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform actions comprising:
-
storing a current state of a finite automaton and a condensed transition table for the current state, the finite automaton configured to match patterns in input data, the condensed transition table indicating, for each possible next element in the input data, a corresponding next state of the finite automaton, the condensed representation including a reference to a transition table template, an identification of a difference region for the transition table and the transition table template, and a difference table storing the next states of the difference region of the transition table, where the difference region is a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; receiving an input element; determining a next state for the finite automaton, the determining including; determining whether a next state corresponding to the input element is in the difference region; in response to determining that the next state corresponding to the input element is not in the difference region, retrieving the next state from the transition table template; and in response to determining that the next state corresponding to the input element is in the difference region, retrieving the next state from the difference table; and updating the current state of the finite automaton to be the next state.
-
-
21. An article of manufacture, comprising:
-
a computer readable medium; and information stored in the computer readable medium that, when processed by a computer, defines a data structure storing a condensed representation of a transition table for a current state of a finite automaton, the finite automaton configured to match patterns in input data, the transition table including, for each possible next element in the input data, a corresponding next state of the finite automaton, the data structure comprising; a reference to a transition table template for the transition table; an identification of a difference region for the transition table and the transition table template, the difference region being a contiguous region in the transition table containing all next states that are different from the corresponding next states in the transition table template; and the next states corresponding to the difference region in the transition table. - View Dependent Claims (22)
-
Specification