本发明涉及文本搜索技术领域，尤其涉及一种nfa状态关系式的构建方法、字符串处理方法及装置。
背景技术：
在网络包检测技术领域中，需要对网络包中的字符进行搜索匹配，以达到对网络包的安全判断。一般采用正则表达式匹配，先将正则表达式编译为nfa(非确定有穷自动机)。然后，如果内存空间和执行时间允许，再将nfa转换为dfa(确定有穷自动机)。最后，根据匹配模式(“子串搜索”和“全文匹配”)，执行匹配任务。但目前进行字符串匹配处理时，匹配速度较慢，无法实现快速完成对网络包的安全检测。
技术实现要素：
针对现有技术存在的问题，本发明实施例提供一种nfa状态关系式的构建方法、字符串处理方法及装置。
第一方面，本发明实施例提供一种nfa状态关系式的构建方法，包括：
获取用于进行字符串匹配的正则表达式；
对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
进一步地，所述对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式，包括：
获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；和/或，
获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化；
基于经前缀优化处理后的nfa状态关系式，和/或经后缀优化处理后的nfa状态关系式，获得优化后的nfa状态关系式。
进一步地，所述获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对所述nfa状态关系式进行前缀优化，包括：
获取所述nfa状态关系式的头部状态信息，所述头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；
获取所述nfa状态关系式的非头部状态信息，所述非头部状态信息包括输入空跳转边列表和区间跳转边列表；
确定所述头字符类型为非限定开头，则头部状态信息增设区间跳转边；
确定所述头部状态信息的输入空跳转边列表不存在空跳转边时，根据所述头部状态信息的输出空跳转边列表确定对应的非头部状态信息；
确定所述非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定所述非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
进一步地，所述获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化，包括：
获取所述nfa状态关系式的尾部状态信息，所述尾部状态信息包括输出非自身空跳转边列表、输出非自身跳转边列表、区间跳转边和输入空跳转边列表；
获取所述nfa状态关系式的非尾部状态信息，所述非尾部状态信息包括输入空跳转边列表、输入跳转边列表和区间跳转边；
确定所述尾部状态信息的输出非自身空跳转边列表不存在非自身空跳转边，且输出非自身跳转边列表存在跳转边且存在区间跳转边，则删除区间跳转边，并根据输入空跳转边列表确定对应的非尾部状态信息；
确定所述非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使所述非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。
第二方面，本发明实施例提供一种字符串处理方法，包括：
获取待匹配字符串和nfa状态关系式；
将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述nfa状态关系式的构建方法获取到的状态关系式。
第三方面，本发明实施例提供一种nfa状态关系式的构建装置，包括：
第一获取模块，用于获取用于进行字符串匹配的正则表达式；
构建模块，用于对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
进一步地，所述构建模块具体用于：
获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；和/或，
获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化；
基于经前缀优化处理后的nfa状态关系式，和/或经后缀优化处理后的nfa状态关系式，获得优化后的nfa状态关系式。
进一步地，所述构建模块在获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化的过程中，具体用于：
获取所述nfa状态关系式的头部状态信息，所述头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；
获取所述nfa状态关系式的非头部状态信息，所述非头部状态信息包括输入空跳转边列表和区间跳转边列表；
确定所述头字符类型为非限定开头，则头部状态信息增设区间跳转边；
确定所述头部状态信息的输入空跳转边列表不存在空跳转边时，根据所述头部状态信息的输出空跳转边列表确定对应的非头部状态信息；
确定所述非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定所述非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
进一步地，所述构建模块在获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化的过程中，具体用于：
获取所述nfa状态关系式的尾部状态信息，所述尾部状态信息包括输出非自身空跳转边列表、输出非自身跳转边列表、区间跳转边和输入空跳转边列表；
获取所述nfa状态关系式的非尾部状态信息，所述非尾部状态信息包括输入空跳转边列表、输入跳转边列表和区间跳转边；
确定所述尾部状态信息的输出非自身空跳转边列表不存在非自身空跳转边，且输出非自身跳转边列表存在跳转边且存在区间跳转边，则删除区间跳转边，并根据输入空跳转边列表确定对应的非尾部状态信息；
确定所述非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使所述非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。
第四方面，本发明实施例提供一种字符串处理装置，包括：
第二获取模块，用于获取待匹配字符串和nfa状态关系式；
处理模块，用于将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述nfa状态关系式的构建装置获得到的状态关系式。
第五方面，本发明实施例提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如所述nfa状态关系式的构建方法的步骤，或实现如所述字符串处理方法的步骤。
第六方面，本发明实施例提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如所述nfa状态关系式的构建方法的步骤，或实现如所述字符串处理方法的步骤。
第七方面，本发明实施例提供一种计算机程序产品，所述计算机程序产品包括计算机可执行指令，其特征在于，所述指令在被执行时用于实现如所述nfa状态关系式的构建方法的步骤，或实现如所述字符串处理方法的步骤。
本发明实施例提供的一种nfa状态关系式的构建方法、字符串处理方法及装置，通过对所述nfa状态关系式进行前后缀优化处理，获得优化后的nfa状态关系式，进而加快编译成dfa状态关系式，使所述dfa状态关系式降低状态数量和利用率，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明nfa状态关系式的构建方法实施例流程图；
图2为本发明nfa状态关系式的构建方法另一实施例流程图；
图3为本发明前缀预处理之前的nfa状态关系式的示意图；
图4为本发明前缀优化之前的nfa状态关系式的示意图；
图5为本发明前缀优化之后的nfa状态关系式的示意图；
图6为本发明后缀优化之前的nfa状态关系式的示意图；
图7为本发明后缀优化之后的nfa状态关系式的示意图；
图8为本发明前缀优化的流程示意图；
图9为本发明后缀优化的流程示意图；
图10为本发明nfa状态关系式的构建装置实施例结构示意图；
图11为本发明电子设备实施例结构示意图。
具体实施方式
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
图1示出了本发明一实施例提供的一种nfa状态关系式的构建方法，包括：
s11、获取用于进行字符串匹配的正则表达式；
s12、对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
针对步骤s11和步骤s12，需要说明的是，在本发明实施例中，在正则表达式匹配过程中，需要将正则表达式编译为nfa(非确定有穷自动机)状态关系式，再将nfa对字符串进行字符串搜索和全文匹配过程。
对nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，优化后的nfa状态关系式，在转换为dfa时执行的时间较短，也会使得dfa状态关系式的状态数量较少、内存利用率较低，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度。
在本发明实施例中，可仅对nfa状态关系式进行前缀优化处理，以获得优化后的nfa状态关系式；也可仅对nfa状态关系式进行后缀优化处理，以获得优化后的nfa状态关系式；也可先对nfa状态关系式进行前缀优化之后，再进行后缀的优化处理，以获得优化后的nfa状态关系式；或者对nfa状态关系式进行后缀优化之后，再进行前缀的优化处理，以获得优化后的nfa状态关系式。以上仅为示例性说明，本发明实施例对此不做具体限定。
匹配得到匹配结果后，可根据匹配结果确定所述待匹配字符串的风险类别，从而快速完成对网络包的安全检测。
本发明实施例提供的一种nfa状态关系式的构建方法，通过对所述nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
图2示出了本发明一实施例提供的一种nfa状态关系式的构建方法，包括：
s21、获取用于进行字符串匹配的正则表达式；
s22、获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；
s23、获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化；
s24、基于经前缀优化处理后的nfa状态关系式，和/或经后缀优化处理后的nfa状态关系式，获得优化后的nfa状态关系式。
针对步骤s21-步骤s24，需要说明的是，在本发明实施例中，在正则表达式匹配过程中，需要将正则表达式编译为nfa(非确定有穷自动机)状态关系式，再将nfa对字符串进行字符串搜索和全文匹配过程。
对正则表达式进行编译获得nfa状态关系式，每个nfa状态关系式包括多个状态，通常情况下包括一个头部状态和尾部状态，其他状态可根据不同情况分为非头部状态或非尾部状态，状态与状态之间存在跳转关系，即状态关系式中的跳转边。
在本发明实施例中，需对头部状态进行前缀优化处理，对尾部状态进行后缀优化处理。因此，可获取nfa状态关系式的头部状态信息和非头部状态信息，根据头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据尾部状态信息和非尾部状态信息对进行前缀优化后的nfa状态关系式进行后缀优化，获得优化后的nfa状态关系式。
本发明实施例提供的nfa状态关系式的构建方法，通过对所述nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
在上述实施例的进一步实施例中，所述获取所述nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对所述nfa状态关系式进行前缀优化，包括：
s2211、获取所述nfa状态关系式的头部状态信息，所述头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；获取所述nfa状态关系式的非头部状态信息，所述非头部状态信息包括输入空跳转边列表和区间跳转边列表；
s2212、确定所述头字符类型为非限定开头，则头部状态信息增设区间跳转边；
s2213、确定所述头部状态信息的输入空跳转边列表不存在空跳转边时，根据所述头部状态信息的输出空跳转边列表确定对应的非头部状态信息；
s2214、确定所述非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定所述非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
针对步骤s2211-步骤s2214，需要说明的是，首先要获取nfa状态关系式的头部状态信息，头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；获取nfa状态关系式的非头部状态信息，非头部状态信息包括输入空跳转边列表和区间跳转边列表。
在这里，头字符类型为正则表达式中的第一个字符的类型。如用于限定开头的字符^、前缀字符.*。
头部状态信息的输入空跳转边列表为其他状态向头部状态的跳转列表。输出空跳转边列表为头部状态向非头部状态的跳转列表。
非头部状态信息的输入空跳转边列表为头部状态向非头部状态的跳转列表，区间跳转边列表是自身的跳转，在这里，前缀字符代表区间跳转边列表，即区间跳转边00-ff(-)，包含所有字符集。
如果正则表达式正的第一个字符不是“^”,则需要为此正则表达式增加“前缀.*”。例如：搜索模式的正则表达式“abc”，在前缀增加“前缀.*”得到的正则表达式为“.*abc”。
如图3所示为前缀预处理之前的nfa状态关系式的示意图，如图4所示为前缀预处理之后的nfa状态关系式的示意图，也是前缀优化之前的nfa状态关系式。如图5为前缀优化之后的nfa状态关系式，从图3和图4可以看出，0-4是nfa的各种状态，从图5可以看出，0-3是nfa的各种状态。圆圈中的数字是状态的编号，根据nfa状态关系式的不同确定状态的编号。箭头代表跳转，即跳转边。0代表头部状态，3代表尾部状态，方框中[1]的代表正则表达式的编号。括号内的abcd代表正则表达式中的字符，abcd之前的数字对应于字符的编号。00-ff(-)代表区间跳转边，即前缀.*。
图3中的头部状态对应正则表达式的第一个字符，该字符不是限定开头的字符，故增加前缀字符.*。如图4所示的00-ff(-)，增加自身的区间跳转边。
在前缀优化(清除前缀“.*”)过程中，需要判断多个条件，如下：
判断头部状态信息的输入空跳转边列表是否存在空跳转边。如图4中的头部状态0是否有箭头指向它。
判断头部状态信息的输出空跳转边列表是否存在空跳转边。如图4中头部状态0指向非头部状态1(即虚线箭头0→1)。故头部状态信息的输出空跳转边列表存在空跳转边(即虚线箭头0→1)，则能够确定对应的非头部状态1。图4中示出的是输出空跳转边列表中只有一个空跳转边。在复杂的nfa状态关系中，输出空跳转边列表中可能会存在多个空跳转边，因此，需要依次遍历对确定的非头部状态进行前缀优化。
非头部状态确定后，确定非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
以图4中的非头部状态1的输入空跳转边只有虚线箭头0→1，且非头部状态信息的区间跳转边只有自身的00-ff(-)，包含所有字符集，则删除该区间跳转边。使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。将图4和图5进行比较，可以看出状态数少了一个，即头部状态0和非头部状态1合并。
还需要说明的是，当头部状态0和非头部状态1合并之后，成为新的头部状态0。若之前的非头部状态1的输出空跳转边列表中还有空跳转边，如跳转到状态2。此时，在头部状态0和非头部状态1合并之后，就相当于新的头部状态0能够空跳到非头部状态2。
在上述实施例的进一步实施例中，获取所述nfa状态关系式的尾部状态信息和非尾部状态信息，根据尾部状态信息和非尾部状态信息对进行前缀优化后的nfa状态关系式进行后缀优化，包括：
s2311、获取nfa状态关系式的尾部状态信息，尾部状态信息包括输出非自身空跳转边列表、输出非自身跳转边列表、区间跳转边和输入空跳转边列表；获取nfa状态关系式的非尾部状态信息，非尾部状态信息包括输入空跳转边列表、输入跳转边列表和区间跳转边；
s2322、确定尾部状态信息的输出非自身空跳转边列表不存在非自身空跳转边、输出非自身跳转边列表存在跳转边且存在区间跳转边，则删除区间跳转边，并根据输入空跳转边列表确对应的非尾部状态信息；
s2323、确定非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。
如图6为后缀优化之前的nfa状态关系式，图7为后缀优化之后的nfa状态关系式。在后缀优化(清除后缀“.*”)过程中，需要判断多个条件，如下：
判断尾部状态信息的输出非自身空跳转边列表是否存在非自身空跳转边。如图6中的尾部状态2是否有虚线箭头(即空跳转边)指向其他状态。
判断尾部状态信息的输出非自身跳转边列表是否存在跳转边。如图6中尾部状态2有箭头指向方框的编号1，该编号是正则表达式的编号。
判断尾部状态信息是否存在区间跳转边。如图5中尾部状态2不存在区间跳转边。
由于非尾部状态会输入跳转边到尾部状态，因此需根据输入空跳转边列表确对应的非尾部状态信息。即：非尾部状态空跳到尾部状态，则可以确定该非尾部状态。如图5中的状态1虚线箭头指向尾部状态2。此时，可确定状态1为非尾部状态。
非尾部状态确定后，确定非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。如图6中的非尾部状态1不存在头部状态0输入的空跳转边，且只有一条头部状态0输入的跳转边。非尾部状态1具有区间跳转边00-ff(-)，则删除该区间跳转边，使非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。如图6和图7进行比较，可以看出状态数少了一个，即非尾部状态1和尾部状态2合并。
经前缀优化和后缀优化后，形成优化后的nfa状态关系式。
如图8为本发明实施例前缀优化的流程示意图，图9为本发明实施例后缀优化的流程示意图。从图8和图9中可以看出，经上述的原理陈述内容可以对图8和图9达到理解，在此不再赘述。
本发明一实施例提供的一种字符串处理方法，包括：
s31、获取待匹配字符串和nfa状态关系式；
s32、将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述实施例的nfa状态关系式的构建方法获取到的状态关系式。
针对步骤s31-步骤s32，需要说明的是，在本发明实施例中，在正则表达式匹配过程中，需要将正则表达式编译为nfa(非确定有穷自动机)状态关系式和dfa(确定有穷自动机)状态关系式，nfa和dfa分别对字符串进行字符串搜索和全文匹配过程。dfa关系式由nfa关系式转变。字符串匹配时，可用nfa关系式对字符串进行匹配，也可用dfa关系式对字符串进行匹配。
对所述nfa状态关系式进行前后缀优化处理，获得优化后的nfa状态关系式，优化后的nfa状态关系式，在转换为dfa时执行的时间较短，也会使得dfa状态关系式的状态数量较少、内存利用率较低，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度。
匹配得到匹配结果后，可根据匹配结果确定所述待匹配字符串的风险类别，从而快速完成对网络包的安全检测。
本发明实施例提供的一种字符串处理方法，通过对所述nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，进而加快编译成dfa状态关系式，使所述dfa状态关系式降低状态数量和利用率，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
图10示出了本发明一实施例提供的一种nfa状态关系式的构建装置，包括第一获取模块41和构建模块42，其中：
第一获取模块41，用于获取用于进行字符串匹配的正则表达式；
构建模块42，用于对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
由于本发明实施例所述装置与上述实施例所述方法的原理相同，对于更加详细的解释内容在此不再赘述。
需要说明的是，本发明实施例中可以通过硬件处理器(hardwareprocessor)来实现相关功能模块。
本发明实施例提供的一种nfa状态关系式的构建装置，通过对所述nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，进而加快编译成dfa状态关系式，使所述dfa状态关系式降低状态数量和利用率，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
在上述实施例方法的进一步实施例中，所述构建模块具体用于：
获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；和/或，
获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化；
基于经前缀优化处理后的nfa状态关系式，和/或经后缀优化处理后的nfa状态关系式，获得优化后的nfa状态关系式。
在上述实施例方法的进一步实施例中，所述构建模块在获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化的过程中，具体用于：
获取所述nfa状态关系式的头部状态信息，所述头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；
获取所述nfa状态关系式的非头部状态信息，所述非头部状态信息包括输入空跳转边列表和区间跳转边列表；
确定所述头字符类型为非限定开头，则头部状态信息增设区间跳转边；
确定所述头部状态信息的输入空跳转边列表不存在空跳转边时，根据所述头部状态信息的输出空跳转边列表确定对应的非头部状态信息；
确定所述非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定所述非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
在上述实施例方法的进一步实施例中，所述构建模块在获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化的过程中，具体用于：
获取所述nfa状态关系式的尾部状态信息，所述尾部状态信息包括输出非自身空跳转边列表、输出非自身跳转边列表、区间跳转边和输入空跳转边列表；
获取所述nfa状态关系式的非尾部状态信息，所述非尾部状态信息包括输入空跳转边列表、输入跳转边列表和区间跳转边；
确定所述尾部状态信息的输出非自身空跳转边列表不存在非自身空跳转边，且输出非自身跳转边列表存在跳转边且存在区间跳转边，则删除区间跳转边，并根据输入空跳转边列表确定对应的非尾部状态信息；
确定所述非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使所述非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。
本发明一实施例提供的一种字符串处理装置，包括第一获取模块和处理模块，其中：
第二获取模块，用于获取待匹配字符串和nfa状态关系式；
处理模块，用于将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述的nfa状态关系式的构建装置获得到的状态关系式。
本发明实施例提供的字符串处理装置，通过对所述nfa状态关系式进行前缀和/或后缀优化处理，获得优化后的nfa状态关系式，进而加快编译成dfa状态关系式，使所述dfa状态关系式降低状态数量和利用率，从而在对待匹配字符串进行匹配处理时，能够提升匹配速度，实现快速完成对网络包的安全检测。
图11示例了一种电子设备的实体结构示意图，如图11所示，该电子设备可以包括：处理器(processor)51、通信接口(communicationsinterface)52、存储器(memory)53和通信总线54，其中，处理器51，通信接口52，存储器53通过通信总线54完成相互间的通信。处理器51可以调用存储器53中的逻辑指令，以执行如下方法：获取用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
此外，上述的存储器53中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-onlymemory)、随机存取存储器(ram，randomaccessmemory)、磁碟或者光盘等各种可以存储程序代码的介质。
本发明实施例还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现以执行上述各实施例提供的方法，例如包括：获取用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
本发明实施例还提供一种计算机程序产品，所述计算机程序产品包括计算机可执行指令，所述指令在被执行时实现以执行上述各实施例提供的方法，例如包括：获取用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
本发明实施例提供一种电子设备，该电子设备可以包括：处理器(processor)、通信接口(communicationsinterface)、存储器(memory)和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信。处理器可以调用存储器中的逻辑指令，以执行如下方法：获取待匹配字符串和用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式；将优化后的nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果。
此外，上述的存储器中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-onlymemory)、随机存取存储器(ram，randomaccessmemory)、磁碟或者光盘等各种可以存储程序代码的介质。
本发明实施例还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现以执行上述各实施例提供的方法，例如包括：获取待匹配字符串和用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式；将优化后的nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果。
本发明实施例还提供一种计算机程序产品，所述计算机程序产品包括计算机可执行指令，所述指令在被执行时实现以执行上述各实施例提供的方法，例如包括：获取待匹配字符串和用于进行字符串匹配的正则表达式；对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式；将优化后的nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果。
通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如rom/ram、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。
最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。
1.一种nfa状态关系式的构建方法，其特征在于，包括：
获取用于进行字符串匹配的正则表达式；
对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
2.根据权利要求1所述的nfa状态关系式的构建方法，其特征在于，所述对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式，包括：
获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对nfa状态关系式进行前缀优化；和/或，
获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化；
基于经前缀优化处理后的nfa状态关系式，和/或经后缀优化处理后的nfa状态关系式，获得优化后的nfa状态关系式。
3.根据权利要求2所述的nfa状态关系式的构建方法，其特征在于，所述获取nfa状态关系式的头部状态信息和非头部状态信息，根据所述头部状态信息和非头部状态信息对所述nfa状态关系式进行前缀优化，包括：
获取所述nfa状态关系式的头部状态信息，所述头部状态信息包括头字符类型、输入空跳转边列表和输出空跳转边列表；
获取所述nfa状态关系式的非头部状态信息，所述非头部状态信息包括输入空跳转边列表和区间跳转边列表；
确定所述头字符类型为非限定开头，则头部状态信息增设区间跳转边；
确定所述头部状态信息的输入空跳转边列表不存在空跳转边时，根据所述头部状态信息的输出空跳转边列表确定对应的非头部状态信息；
确定所述非头部状态信息的输入空跳转边列表有且只有一条空跳转边，以及确定所述非头部状态信息的区间跳转边列表有且只有一条区间跳转边且区间跳转边包含所有字符集，则删除区间跳转边，使所述非头部状态信息对应的非头部状态与所述头部状态信息对应的头部状态合并，以完成前缀优化。
4.根据权利要求2所述的nfa状态关系式的构建方法，其特征在于，所述获取nfa状态关系式的尾部状态信息和非尾部状态信息，根据所述尾部状态信息和非尾部状态信息对nfa状态关系式进行后缀优化，包括：
获取所述nfa状态关系式的尾部状态信息，所述尾部状态信息包括输出非自身空跳转边列表、输出非自身跳转边列表、区间跳转边和输入空跳转边列表；
获取所述nfa状态关系式的非尾部状态信息，所述非尾部状态信息包括输入空跳转边列表、输入跳转边列表和区间跳转边；
确定所述尾部状态信息的输出非自身空跳转边列表不存在非自身空跳转边，且输出非自身跳转边列表存在跳转边且存在区间跳转边，则删除区间跳转边，并根据输入空跳转边列表确定对应的非尾部状态信息；
确定所述非尾部状态信息的输入空跳转边列表不存在空跳转边，输入跳转边列表有且只有一条跳转边且存在区间跳转边，则删除区间跳转边，使所述非尾部状态信息对应的非尾部状态与所述尾部状态信息对应的尾部状态合并，以完成后缀优化。
5.一种字符串处理方法，其特征在于，包括：
获取待匹配字符串和nfa状态关系式；
将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述权利要求1-4中任一权利要求所述nfa状态关系式的构建方法获取到的状态关系式。
6.一种nfa状态关系式的构建装置，其特征在于，包括：
第一获取模块，用于获取用于进行字符串匹配的正则表达式；
构建模块，用于对所述正则表达式进行编译获得nfa状态关系式，对nfa状态关系式进行前缀，和/或后缀优化处理，获得优化后的nfa状态关系式。
7.一种字符串处理装置，其特征在于，包括：
第二获取模块，用于获取待匹配字符串和nfa状态关系式；
处理模块，用于将nfa状态关系式编译成dfa状态关系式，使所述dfa状态关系式对所述待匹配字符串进行匹配处理获得匹配结果；
其中，所述nfa状态关系式为基于上述权利要求6-9中任一权利要求所述nfa状态关系式的构建装置获得到的状态关系式。
8.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至4任一项所述nfa状态关系式的构建方法的步骤，或如权利要求5所述字符串处理方法的步骤。
9.一种非暂态计算机可读存储介质，其上存储有计算机程序，其特征在于，该计算机程序被处理器执行时实现如权利要求1至4任一项所述nfa状态关系式的构建方法的步骤，或如权利要求5所述字符串处理方法的步骤。
10.一种计算机程序产品，所述计算机程序产品包括计算机可执行指令，其特征在于，所述指令在被执行时用于实现如权利要求1至4任一项所述nfa状态关系式的构建方法的步骤，或如权利要求5所述字符串处理方法的步骤。
技术总结