主权项 |
在包括一个或多个处理器和系统存储器的计算机系统中,一种用于在有向非循环图(134)中表示一个或多个正则表达式(111、112)的方法,所述方法包括:访问从第一正则表达式(111)分解的一个或多个关键字图(113)的动作,一个或多个关键字图的每一个具有根节点、一个或多个中间节点、以及叶节点,所述一个或多个中间节点以及所述叶节点的每一个标识部分地匹配所述第一正则表达式(111)的字符模式,所述一个或多个中间节点的每一个以及所述根节点具有单个子节点,所述中间节点之一具有所述叶节点作为子节点,每个叶节点被标记为所述第一正则表达式(111)的匹配状态;访问表示第二正则表达式(121)的至少一部分的第二图(123)的动作,所述第二图(123)具有根节点、一个或多个中间节点、以及一个或多个叶节点,所述一个或多个中间节点以及所述一个或多个叶节点的每一个标识部分地匹配所述第二正则表达式(123)的字符模式;将所述一个或多个关键字图(113)和所述第二图(123)合并成有向非循环图(134)的动作,所述有向非循环图(134)共同表示所述第一正则表达式(111)和所述第二正则表达式(121)两者,所述合并动作包括对于所述一个或多个关键字图的每一个进行:单独选择所述关键字图(113A、113B、113C)的动作;标识所选关键字图(113A,113B,113C)和第二图(123)内具有至少部分重叠字符模式的任何相似定位的中间节点的动作;以及对于相似定位且具有部分重叠字符模式的所选关键字图(113A,113B,113C)中的任何所标识中间节点和所述第二图(123)中的所标识中间节点,在所标识中间节点处合并所选关键字图和所述第二图以在所述有向非循环图(134)中表示来自所选关键字图(113A,113B,113C)和所述第二图(123)中的等效匹配状态的动作,所述合并使得所述关键字图变成所述第二图的一部分。 |