Regular expression matching
US10242125B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 5, 2013 |
| Grant date | Mar 26, 2019 |
| Priority date | — |
| Expiry date | Oct 18, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F40/289
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Example embodiments relate to regular expression matching. An example method may include generating a data structure based on a non-deterministic finite automaton (NFA) that represents a regular expression. The data structure may include a set of segments where each segment indicates a segment starting state of the NFA. Each segment may represent zero or more consecutive states of the NFA starting at the segment starting state. Different segments of the set of segments may be capable of indicating different segment starting states on the NFA. Each segment may represent a partial match of the regular expression to the string. The method may further include analyzing the string in relation to the NFA. The method may further include modifying the data structure as the string is analyzed. Such modification may include attempting to expand at least one of the segments in the set to represent additional states of the NFA.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.