Systems and methods for processing regular expressions
US7512634B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Jun 5, 2006 |
| Grant date | Mar 31, 2009 |
| Priority date | — |
| Expiry date | Jan 26, 2027 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99948
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method for reducing the size of a DFA associated with a regular expression separates the functions of locating subexpressions within the DFA and determining if the located subexpressions satisfy a regular expression. For example, the functions of (1) locating subexpressions in a range asserting expression and, (2) determining whether the subexpressions satisfy the range of the range asserting expression are partitioned. In one embodiment, a first component may locate the subexpressions in a data stream using one or more DFAs, while a second component determines if the located subexpressions satisfy the range. In this embodiment, because the DFAs are not configured to determine a relationship between subexpressions, such as a range between subexpressions, the size of the resultant DFA may be significantly reduced.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.