# US 2016/0253378 A1 · Practical modular finite automation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253378 A1
- Document ID: US20160253378A1
- Status: Published application
- Kind: A1
- Application number: 14/632,470
- Filed: 2015-02-26
- Published: 2016-09-01
- Earliest claimed: 2015-02-26
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Itay Marom; Hanoch Haim; Nicholas Read Leavy; Kobi Kobi Vaknin
- Web page: https://patentgrep.com/patent/US20160253378A1

## CPC

- G06F 16/245: Query processing
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system, computer-readable media, and methods are disclosed for searching a data stream for one or more regular expressions. The method can include receiving a data stream and a regular expression and parsing the regular expression to create a prefix portion and a suffix portion. The method can also include executing a first search of at least a portion of the data stream for the prefix portion using a first search algorithm, the first search algorithm being stored in a computer readable medium and executed by a processor. The method also include executing a second search of at least a portion of the data stream for the suffix portion using a second search algorithm, the second search algorithm being stored in a computer readable medium and executed by a processor. Further, the method includes determining whether the data stream contains the regular expression based on the first search and the second search.

## Claims

### Claim 1

A system for searching a data stream for one or more regular expressions, comprising:
a network interface configured to receive the data stream;
a processor configured to:
obtain a regular expression;
parse the regular expression to create a prefix portion and a suffix portion;
execute a first search of at least a portion of the data stream for the prefix portion using a first search algorithm;
execute a second search of at least a portion of the data stream for the suffix portion using a second search algorithm; and
determine whether the data stream contains the regular expression based on the first search and the second search.

### Claim 2 (depends on 1)

The system of claim 1, wherein the first search algorithm comprises a deterministic finite automaton.

### Claim 3 (depends on 1)

The system of claim 1, wherein the second search algorithm comprises a nondeterministic finite automaton.

### Claim 4 (depends on 1)

The system of claim 1, wherein the processor is further configured to scan the regular expression to identify one or more characters that are used to identify a transition from the prefix to the suffix, the one or more characters indicating a wildcard within the regular expression.

### Claim 5 (depends on 1)

The system of claim 1, wherein the suffix portion comprises a plurality of suffix portions.

### Claim 6 (depends on 1)

The system of claim 1, wherein the processor is further configured to replace the first search algorithm with an updated version without changing the second search algorithm.

### Claim 7 (depends on 1)

The system of claim 1, wherein the processor is further configured to, in parallel, obtain a plurality of regular expressions, parse the plurality of regular expressions, and execute a first and second search using prefix and suffix portions of the plurality of regular expressions.

### Claim 8

A method for searching a data stream for one or more regular expressions, comprising:
receiving a data stream and a regular expression;
parsing the regular expression to create a prefix portion and a suffix portion;
executing a first search of at least a portion of the data stream for the prefix portion using a first search algorithm, the first search algorithm being stored in a computer readable medium and executed by a processor;
executing a second search of at least a portion of the data stream for the suffix portion using a second search algorithm, the second search algorithm being stored in a computer readable medium and executed by a processor; and
determining whether the data stream contains the regular expression based on the first search and the second search.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first search algorithm comprises a deterministic finite automaton.

### Claim 10 (depends on 8)

The method of claim 8, wherein the second search algorithm comprises a nondeterministic finite automaton.

### Claim 11 (depends on 8)

The method of claim 8, wherein parsing the regular expression comprises:
scanning the regular expression to identify one or more characters that are used to identify a transition from the prefix to the suffix, the one or more characters indicating a wildcard within the regular expression.

### Claim 12 (depends on 8)

The method of claim 8, wherein the suffix portion comprises a plurality of suffix portions.

### Claim 13 (depends on 8)

The method of claim 8, wherein the first search algorithm comprises a modular component, and wherein the method further comprises replacing the first search algorithm with an updated version of the first search algorithm.

### Claim 14 (depends on 8)

The method of claim 8, further comprising receiving a plurality of regular expressions and executing the method simultaneously using the plurality of regular expressions.

### Claim 15

A computer readable medium comprising instructions which, when executed by a processor, perform a method for searching a data stream for one or more regular expressions, comprising:
receiving a data stream and a regular expression;
parsing the regular expression to create a prefix portion and a suffix portion;
executing a first search of at least a portion of the data stream for the prefix portion using a first search algorithm, the first search algorithm being stored in a computer readable medium and executed by a processor;
executing a second search of at least a portion of the data stream for the suffix portion using a second search algorithm, the second search algorithm being stored in a computer readable medium and executed by a processor; and
determining whether the data stream contains the regular expression based on the first search and the second search.

### Claim 16 (depends on 15)

The computer readable medium of claim 15, wherein the first search algorithm comprises a deterministic finite automaton.

### Claim 17 (depends on 15)

The computer readable medium of claim 15, wherein the second search algorithm comprises a nondeterministic finite automaton.

### Claim 18 (depends on 15)

The computer readable medium of claim 15, further comprising instruction which, when executed by the processor, scan the regular expression to identify one or more characters that are used to identify a transition from the prefix to the suffix, the one or more characters indicating a wildcard within the regular expression.

### Claim 19 (depends on 15)

The computer readable medium of claim 15, wherein the first search algorithm comprises a modular component that is replaced without changing the second search algorithm.

### Claim 20 (depends on 15)

The computer readable medium of claim 15, further comprising receiving a plurality of regular expressions and executing the method simultaneously using the plurality of regular expressions.
