Generating progressively a perfect hash data structure, such as a multi-dimensional perfect hash data structure, and using the generated data structure for high-speed string matching

A computer-implemented method for placing transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table, the computer-implemented method comprising:

• a) modeling the automaton as a graph in which
• 1) each of a first plurality of nodes corresponds to a state in the automaton,
• 2) each of a second plurality of nodes corresponds to a character in the automaton, and
• 3) each of a plurality of edges corresponds to a state transition, via an input character, in the automaton;
• b) decomposing the graph into dependent edge sets, each of the dependent edge sets being associated with a node from a union of the first and second plurality of nodes to generate a sequence of nodes, each node associated with a set of zero or more edges such that each of the plurality of edges is associated with one and only one of the sequence of nodes;
• and
• c) constructing a perfect hash table by, for each of the sequence of selected nodes, hashing the edges associated with the selected node into the hashing table to generate a perfect hashing table.

Apparatus for placing transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table, the apparatus comprising:

• a) at least one processor;
• and
• b) at least one storage device storing processor-executable instructions which, when executed by the at least one processor, cause the at least one processor to perform acts of
• 1) dividing the transitions into multiple independent sets according to their respective source states;
• 2) ordering the sets of transitions based on the number of transitions belonging to the set, thereby defining an order of the sets from largest to smallest;
• and
• 3) constructing a perfect hash table by, for each of the sets of transitions, in the order from largest to smallest, hashing the transitions of the set into the hashing table to generate a perfect hashing table.