一种高频状态匹配方法及系统

摘要

本发明公开了一种高频状态匹配方法，包括如下步骤：获取数据报文的载荷字符；根据预设规则，判断所述载荷字符是否存在于掩码表中；若所述载荷字符存在于所述掩码表中，则获取所述掩码表中的处于置位状态的个数及存在位置；根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置；根据所述偏移位置获取存放所述载荷字符的状态地址。该方法逻辑清晰，安全、有效、可靠且效果显著，能对高频状态下进行状态压缩，有效的节省内存资源，基于该方法的系统也同样能达到相同的效果。

权利要求

1.一种高频状态匹配方法，其特征在于，包括如下步骤：获取数据报文的载荷字符；

根据预设规则，判断所述载荷字符是否存在于掩码表中；

若所述载荷字符存在于所述掩码表中，则获取所述掩码表中的处于置位状态的个数及存在位置；

根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

根据所述偏移位置获取存放所述载荷字符的状态地址；

其中，根据预设规则，判断所述载荷字符是否存在于掩码表中，包括如下步骤：将所述掩码表中的A位状态划分为M个B位状态；

将所述载荷字符除以B，获取商值与余数；

根据所述商值与所述余数确认所述载荷字符状态在所述掩码表中存在；

其中，根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置具体为：根据所述掩码表中的处于置位状态的个数及存在位置，将C位状态划分为N个D位状态，获取D位状态存在累计表与下一跳总个数；

存在状态的累计值计算公式为i=i+1；

所述下一跳总个数具体为所有所述掩码表中的处于置位状态的个数之和；

其中，获取所述偏移位置具体为：根据所述商值与余数获取第K个所述B位状态中余数之后的置位个数；

若所述商值等于N，则所述下一跳总个数减去所述置位个数的结果即为所述偏移位置；

若所述商值小于N，则所述D位状态存在累计表减去所述置位个数的结果即为所述偏移位置。

2.如权利要求1所述的高频状态匹配方法，其特征在于，在获取数据报文的载荷字符之前，还包括如下步骤：

根据用户输入规则生成状态表；

在所述状态表中根据预设提取算法获取高频状态。

3.如权利要求2所述高频状态匹配方法，其特征在于，所述预设提取算法具体为：广度优先算法。

4.一种高频状态匹配系统，其特征在于，包括：获取模块，用于获取数据报文中的载荷字符；

规则模块，用于获取用户输入的计算规则；

计算模块，用于根据所述计算规则，获取偏移位置；

其中，所述根据所述计算规则，获取偏移位置具体为：将掩码表中的A位状态划分为M个B位状态；

将所述载荷字符除以B，获取商值与余数；

根据所述商值与所述余数确认所述载荷字符状态在所述掩码表中存在；

若所述载荷字符存在于所述掩码表中，则获取所述掩码表中的处于置位状态的个数及存在位置；

根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

其中，根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置具体为：根据所述掩码表中的处于置位状态的个数及存在位置，将C位状态划分为N个D位状态，获取D位状态存在累计表与下一跳总个数；

存在状态的累计值计算公式为i=i+1；

所述下一跳总个数具体为所有所述掩码表中的处于置位状态的个数之和；

其中，获取所述偏移位置具体为：根据所述商值与余数获取第K个所述B位状态中余数之后的置位个数；

若所述商值等于N，则所述下一跳总个数减去所述置位个数的结果即为所述偏移位置；

若所述商值小于N，则所述D位状态存在累计表减去所述置位个数的结果即为所述偏移位置；

压缩模块，用于根据所述偏移位置获取存放所述载荷字符的状态地址。

5.如权利要求4所述的高频状态匹配系统，其特征在于，还包括：输入模块，用于获取用户输入规则；

生成模块，用于根据用户输入规则生成状态表；

提取模块，用于设置提取规则，并根据提取算法获取高频状态。

说明书

一种高频状态匹配方法及系统

技术领域

[0001] 本发明涉及计算机技术领域，特别是涉及一种高频状态匹配方法及系统。

背景技术

[0002] 多模式串匹配是计算机领域经典的问题之一，其目的是在任意字符文本中找出已知的一组特定字符出现的所有位置。AC算法是一种经典的多模式匹配算法，有着良好的时
间复杂度，在许多领域有着广泛的应用。在匹配规则比较多的情况下，考虑匹配算法和效
率，AC是最为经典的算法。

[0003] 但AC算法在匹配大规模规则库时，存在空间开销大、存储效率低等问题。目前大部门基本思想是针对自动机的状态转移表，删除以空转移为主的冗余状态转移边，只保存有
用的信息，在搜索过程中通过计算来查找下一跳状态。

[0004] 目前，在高频状态下，AC算法并未进行状态压缩，状态不存在时占用地址表项但是是无效的，即每一个状态结构体内存放下一跳状态个数都是256，在内存资源有限情况下有
很大浪费。

[0005] 因此，提供一种在高频状态下进行状态压缩后，可以有效节省内存资源的匹配方法及系统是本领域技术人员亟待解决的问题。

发明内容

[0006] 本发明的目的在于提供一种高频状态匹配方法及系统，该方法逻辑清晰，安全、有效、可靠且效果显著，能对高频状态下进行状态压缩，有效的节省内存资源，基于该方法的
系统也同样能达到相同的效果。

[0007] 基于以上目的，本发明提供的技术方案如下：

[0008] 一种高频状态匹配方法，包括如下步骤：

[0009] 获取数据报文的载荷字符；

[0010] 根据预设规则，判断所述载荷字符是否存在于掩码表中；

[0011] 若所述载荷字符存在于所述掩码表中，则获取所述掩码表中的处于置位状态的个数及存在位置；

[0012] 根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

[0013] 根据所述偏移位置获取存放所述载荷字符的状态地址。

[0014] 其中，根据预设规则，判断所述载荷字符是否存在于掩码表中，包括如下步骤：

[0015] 将所述掩码表中的A位状态划分为M个B位状态；

[0016] 将所述载荷字符除以B，获取商值与余数；

[0017] 根据所述商值与所述余数确认所述载荷字符状态在所述掩码表中存在。

[0018] 优选地，根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置具体为：

[0019] 根据所述掩码表中的处于置位状态的个数及存在位置，将C位状态划分为N个D位状态，获取D位状态存在累计表与下一跳总个数；

[0020] 其中，存在状态的累计值计算公式为i=i+1；

[0021] 所述下一跳总个数具体为所有所述掩码表中的处于置位状态的个数之和。

[0022] 优选地，获取所述偏移位置具体为：

[0023] 根据所述商值与余数获取第K个所述B位状态中余数之后的置位个数；

[0024] 若所述商值等于N，则所述下一跳总个数减去所述置位个数的结果即为所述偏移位置；

[0025] 若所述商值小于N，则所述D位状态存在累计表减去所述置位个数的结果即为所述偏移位置。

[0026] 优选地，在获取数据报文的载荷字符之前，还包括如下步骤：

[0027] 根据用户输入规则生成状态表；

[0028] 在所述状态表中根据预设提取算法获取高频状态。

[0029] 优选地，所述预设提取算法具体为：广度优先算法。

[0030] 一种高频状态匹配系统，包括：

[0031] 获取模块，用于获取数据报文中的载荷字符；

[0032] 规则模块，用于获取用户输入的计算规则；

[0033] 计算模块，用于根据所述计算规则，获取偏移位置；

[0034] 其中，所述根据所述计算规则，获取偏移位置具体为：将掩码表中的A位状态划分为M个B位状态；

[0035] 将所述载荷字符除以B，获取商值与余数；

[0036] 根据所述商值与所述余数确认所述载荷字符状态在所述掩码表中存在；

[0037] 若所述载荷字符存在于所述掩码表中，则获取所述掩码表中的处于置位状态的个数及存在位置；

[0038] 根据所述掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

[0039] 压缩模块，用于根据所述偏移位置获取存放所述载荷字符的状态地址。

[0040] 优选地，还包括：

[0041] 输入模块，用于获取用户输入规则；

[0042] 生成模块，用于根据用户输入规则生成状态表；

[0043] 提取模块，用于设置提取规则，并根据提取算法获取高频状态。

[0044] 本发明所提供的基于AC算法的高频状态匹配方法，首先提取数据报文中的载荷字符，通过载荷字符按照预设规则可以计算得出偏移位置，根据已计算得出的偏移位置可以
得知压缩后的状态地址，按照此状态地址存放数据报文。本发明提供的方法仅需通过提取
数据报文的载荷字符，按照预设规则即可计算获取偏移位置，通过偏移位置确定数据报文
的状态地址。按照该状态地址存储数据报文即可完成在高频状态下进行状态压缩，可以有
效的节省内存资源，提高工作效率。

附图说明

[0045] 为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本
申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以
根据这些附图获得其他的附图。

[0046] 图1为本发明实施例提供的一种高频状态匹配方法流程图；

[0047] 图2为本发明实施例提供的一种高频状态匹配方法中步骤S4的流程图；

[0048] 图3为本发明实施例提供的一种高频状态匹配方法中获取偏移位置流程图；

[0049] 图4为本发明实施例提供的一种高频状态匹配系统的结构示意图。

具体实施方式

[0050] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于
本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他
实施例，都属于本发明保护的范围。

[0051] 本发明实施例采用递进的方式撰写。

[0052] 本发明实施例提供了一种基于AC算法的高频状态匹配方法。主要解决现有技术中，未进行状态压缩，状态不存在时占用地址表项但是是无效的，即每一个状态结构体内存
放下一跳状态个数都是256，在内存资源有限情况下有很大浪费的技术问题。

[0053] 一种基于AC算法的高频状态匹配方法，包括如下步骤：

[0054] S1.获取数据报文的载荷字符；

[0055] S2.根据预设规则，判断载荷字符是否存在于掩码表中；

[0056] S3.若载荷字符存在于掩码表中，则获取掩码表中的处于置位状态的个数及存在位置；

[0057] S4.根据掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

[0058] S5.根据偏移位置获取存放载荷字符的状态地址；

[0059] 其中，根据载荷字符按照预设规则获取偏移位置，包括如下步骤：

[0060] A1.将掩码表中的A位状态划分为M个B位状态；

[0061] A2.将载荷字符除以B，获取商值与余数；

[0062] A3.根据商值与余数确认载荷字符状态在掩码表中存在。

[0063] 步骤S1中，获取数据报文的载荷字符。当接收到一个网络数据包时，解析数据包并提取载荷字符。

[0064] 步骤S2中，提取载荷字符后按照提前预设好的规则，可以判断载荷字符是否存在于掩码表中。

[0065] 步骤S3中，若载荷字符存在与掩码表中，则可以获取掩码表中处于置位状态的个数及存在位置。其中，置位状态即该位置不为空。

[0066] 步骤S4中，根据掩码表中的处于置位状态的个数及存在位置，可以计算得出偏移位置。

[0067] 步骤S5中，根据已获取的偏移位置可以计算得出存放载荷字符的状态地址。

[0068] 本发明提供的方法仅需通过提取数据报文的载荷字符，按照预设规则即可计算获取偏移位置，通过偏移位置确定数据报文的状态地址。按照该状态地址存储数据报文即可
完成在高频状态下进行状态压缩，可以有效的节省内存资源，提高工作效率。

[0069] 实际运用过程中，由于是ASCII码是256个字符，每一个状态下一跳最多256种可能，即256种状态，在表示每一个状态的载荷字符上用8个32位的数组，即可以利用每一位表
示下一跳该状态是否存在。输入规则字符对32取除数可以知道该字符表示状态在哪一段32
位内，对32求摸结果用于对该位置位时使用，表示该状态存在。

[0070] 因此，在本实施例中，步骤A1即为将256位划分为8个32位；步骤B2中，对以获取的载荷字符除以32，获取其商值；步骤A3中，即可通过商值确定载荷字符位于哪一端32位内。

[0071] 优选地，数据报文状态具体为数据报文存在个数及存在位置。

[0072] 实际运用过程中，根据商值即可确定数据报文状态，即数据报文存在个数及存在位置。假设ASCII值为165位的载荷字符，商值为5，余数为5，即其位于第6个32位内，位置在
第5位。

[0073] 优选地，根据掩码表中的处于置位状态的个数及存在位置，获取偏移位置具体为：

[0074] 根据掩码表中的处于置位状态的个数及存在位置，将C位状态划分为N个D位状态，获取D位状态存在累计表与下一跳总个数；

[0075] 其中，存在状态的累计值计算公式为i=i+1；

[0076] 下一跳总个数具体为所有掩码表中的处于置位状态的个数之和。

[0077] 实际运用过程中，在载荷字符中用7个8位的数组存放一一对应的前7个表示状态存在的32位数组中有多少个状态存在，每一个8位值数组变量都是在前一个8位数组的基础
上的累计值，总的下一跳个数是所有置位状态的个数。

[0078] 在本实施例中，用于存储对应8个32位数组里每一个32位中有多少个位置位了即表示对应的字符状态存在，而且每一个8位的数组值是累加的，最后一个累计值存放在总的
下一跳个数这个变量里面，这样设计是为了方便在匹配阶段直接获取总偏移值不需要额外
计算。其中，步骤B1中，将56位状态划分为7个8位状态。步骤B2中，根据上述已确定的数据报
文存在个数及存在位置，获取载荷字符处于8位状态存在累计表，与下一跳总个数。

[0079] 优选地，获取偏移位置具体为：

[0080] B1.根据商值与余数获取第K个B位状态中余数之后的置位个数；

[0081] B2.若商值等于N，则下一跳总个数减去置位个数的结果即为偏移位置；

[0082] B3.若商值小于N，则D位状态存在累计表减去置位个数的结果即为偏移位置。

[0083] 实际运用过程中，载荷字符对32取余数的结果用于计算从余数开始位置该掩码结果中还有多少位置位，即第K个32为状态中余数之后的置位个数，如果载荷字符对32取除数
结果即K等于7则用总的下一跳个数减去该计算结果得到偏移位置，否则用载荷字符对32取
除数做下标取得的累计表结果减去该计算结果可以知道状态偏移位置。

[0084] 优选地，在获取数据报文的载荷字符之前，还包括如下步骤：

[0085] 根据用户输入规则生成状态表；

[0086] 在状态表中根据预设提取算法获取高频状态。

[0087] 实际运用过程中，在获取数据报文的载荷字符之前，可以提前根据用户输入规则生成状态表，在状态表中提取高频状态的载荷字符。

[0088] 优选地，预设提取算法具体为：广度优先算法。

[0089] 在本实施例中，是遵循广度优先算法提取高频状态的载荷字符。

[0090] 一种高频状态匹配系统，包括：

[0091] 获取模块，用于获取数据报文中的载荷字符；

[0092] 规则模块，用于获取用户输入的计算规则；

[0093] 计算模块，用于根据计算规则，获取偏移位置；

[0094] 其中，根据计算规则，获取偏移位置具体为：将掩码表中的A位状态划分为M个B位状态；

[0095] 将载荷字符除以B，获取商值与余数；

[0096] 根据商值与余数确认载荷字符状态在掩码表中存在；

[0097] 若载荷字符存在于掩码表中，则获取掩码表中的处于置位状态的个数及存在位置；

[0098] 根据掩码表中的处于置位状态的个数及存在位置，获取偏移位置；

[0099] 压缩模块，用于根据偏移位置获取存放载荷字符的状态地址。

[0100] 实际运用过程中，获取模块在高频状态下获取数据报文中的载荷字符后，将载荷字符传输至计算模块；规则模块设置相关的计算规则后，将该计算规则传输至计算模块；计
算模块根据载荷字符以及预设的相关计算规则计算得出偏移位置并传输至压缩模块；压缩
模块根据已获取的偏移位置获取载荷字符的状态地址。

[0101] 优选地，还包括：

[0102] 输入模块，用于获取用户输入规则；

[0103] 生成模块，用于根据用户输入规则生成状态表；

[0104] 提取模块，用于设置提取规则，并根据提取算法获取高频状态。

[0105] 实际运用过程中，在工作开始之前，用户可以通过输入模块输入规则，输入模块将用户输入规则传输至生成模块，生成模块根据用户输入规则生成状态表并将状态表传输至
提取模块；提取模块提前预设提取算法，并根据提取算法在状态表中提取高频状态数据报
文。

[0106] 在本申请所提供的实施例中，应该理解到，所揭露的方法和装置，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，模块的划分，仅仅为一种逻辑
功能划分，实际实现时可以有另外的划分方式，如：多个模块或组件可以结合，或可以集成
到另一个系统，或一些特征可以忽略，或不执行。另外，所显示或讨论的各组成部分相互之
间的耦合、或直接耦合、或通信连接可以是通过一些接口，设备或模块的间接耦合或通信连
接，可以是电性的、机械的或其它形式的。

[0107] 另外，在本发明各实施例中的各功能模块可以全部集成在一个处理器中，也可以是各模块分别单独作为一个器件，也可以两个或两个以上模块集成在一个器件中；本发明
各实施例中的各功能模块既可以采用硬件的形式实现，也可以采用硬件加软件功能单元的
形式实现。

[0108] 本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令及相关的硬件来完成，前述的程序指令可以存储于计算机可读取存储介质中，该
程序指令在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：移动存储设
备、只读存储器(Read Only Memory，ROM)、磁碟或者光盘等各种可以存储程序代码的介质。

[0109] 以上对本发明所提供的一种高频状态匹配方法及系统进行了详细介绍。对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多
种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不
脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本
文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。