Deterministic finite automata graph traversal with nodal bit mapping
US8473523B2 · kind B2 · utility
44Cited by
26References
41Claims
0Family size
Assignee
Inventor
Key dates
| Filing date | Nov 24, 2008 |
| Grant date | Jun 25, 2013 |
| Priority date | — |
| Expiry date | Dec 30, 2030 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L63/1416
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An apparatus, and corresponding method, for generating a graph used in performing a search for a match of at least one expression in an input stream is presented. The graph includes a number of interconnected nodes connected solely by valid arcs. A valid arc may also include a nodal bit map including structural information of a node to which the valid arc points to. A walker process may utilize the nodal bit map to determine if a memory access is necessary. The nodal bit map reduces the number of external memory access and therefore reduces system run time.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.