Invention Grant
US09563399B2 Generating a non-deterministic finite automata (NFA) graph for regular expression patterns with advanced features
有权
生成具有高级特征的正态表达式模式的非确定性有限自动机(NFA)图
- Patent Title: Generating a non-deterministic finite automata (NFA) graph for regular expression patterns with advanced features
- Patent Title (中): 生成具有高级特征的正态表达式模式的非确定性有限自动机(NFA)图
-
Application No.: US14186978Application Date: 2014-02-21
-
Publication No.: US09563399B2Publication Date: 2017-02-07
- Inventor: Rajan Goyal , Satyanarayana Lakshmipathi Billa
- Applicant: Cavium, Inc.
- Applicant Address: US CA San Jose
- Assignee: Cavium, Inc.
- Current Assignee: Cavium, Inc.
- Current Assignee Address: US CA San Jose
- Agency: Hamilton, Brook, Smith & Reynolds, P.C.
- Main IPC: G06F17/30
- IPC: G06F17/30 ; G06F5/14 ; H04L12/24 ; G06F13/28 ; H04L29/06

Abstract:
In an embodiment, a method of compiling a pattern into a non-deterministic finite automata (NFA) graph includes examining the pattern for a plurality of elements and a plurality of node types. Each node type can correspond with an element. Each element of the pattern can be matched at least zero times. The method further includes generating a plurality of nodes of the NFA graph. Each of the plurality of nodes can be configured to match for one of the plurality of elements. The node can indicate the next node address in the NFA graph, a count value, and/or node type corresponding to the element. The node can also indicate the element representing a character, character class or string. The character can also be a value or a letter.
Public/Granted literature
Information query