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
US9455996B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 1, 2012 |
| Grant date | Sep 27, 2016 |
| Priority date | — |
| Expiry date | Jul 8, 2032 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L63/0245
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A multi-dimensional perfect hash table construction technique is based on which the well-known AC automaton, and can be implemented by very compact perfect hash tables. The technique may place transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table by: (a) dividing the transitions into multiple independent sets according to their respective source states; (b) 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 (c) 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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.