Pattern recognition using transition table templates

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.

A non-transitory 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.

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.

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.

A non-transitory 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.

An article of manufacture, comprising:

• a non-transitory 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.