公开(公告)号：US20160275205A1

公开(公告)日：2016-09-22

申请号：US15032851

申请日：2013-12-05

Applicant: HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP

Inventor： David Lehavi ,  Omer Barkol

IPC: G06F17/30 ,  G06F17/27

CPC classification number: G06F17/30985 ,  G06F17/2775 ,  G06F17/30

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.

Abstract translation: 示例实施例涉及正则表达式匹配。 示例性方法可以包括基于表示正则表达式的非确定性有限自动机（NFA）生成数据结构。 数据结构可以包括一组段，其中每个段指示NFA的段起始状态。 每个段可以表示从段开始状态开始的NFA的零个或多个连续状态。 该组段的不同段可能能够指示NFA上不同段的起始状态。 每个段可以表示正则表达式与字符串的部分匹配。 该方法还可以包括分析与NFA相关的字符串。 该方法还可以包括在分析字符串时修改数据结构。 这种修改可以包括尝试扩展集合中的至少一个段以表示NFA的附加状态。

公开(公告)号：US10242125B2

公开(公告)日：2019-03-26

申请号：US15032851

申请日：2013-12-05

Applicant: Hewlett Packard Enterprise Development LP

Inventor： David Lehavi ,  Omer Barkol

IPC: G06F17/30 ,  G06F17/27

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.