一种对正则式DFA分组的方法

摘要

本发明提供了一种对正则式DFA分组的方法。A、对所有的正则式两两分组，生成两两之间的状态和；B、将所有正则式置于第一组，置失败标志为0；C、对步骤A的状态和进行排序，在第一组中找出两两之和最大的正则式a；D、将正则式a置于第二组；E、对第二组的正则式生成DFA，如果在DFA状态数目约束条件下生成成功，判断失败标志，如果为0，转到步骤C，如果为1，跳转至步骤G；如果失败则将a置成第三组，置失败标志为1，转到步骤C；F、循环操作步骤C、D、E，直到依次所有正则式都尝试结束；G、将第三组中的正则式放到第一组中，尝试对第一组生成DFA，若成功，则分组结束，若失败则可对第三组重新分组，转到步骤A。本发明利用探测淘汰策略，实现了对正则式的最少分组，实现了在DFA状态数目约束下，生成DFA状态的最大化，可以实现对正则式的高效匹配。

主权项

一种适应于网络信息处理的正则式DFA分组的方法，其特征在于：包括以下步骤：A、对所有的正则式两两分组，生成两两之间的状态和；B、将所有正则式置于第一组，置失败标志为0；C、对步骤A的状态和进行排序，在第一组中找出两两之和最大的正则式a；D、将正则式a置于第二组；E、对第二组的正则式生成DFA，如果在DFA状态数目约束条件下生成成功，判断失败标志，如果为0，转到步骤C，如果为1，跳转至步骤G；如果失败则将a置成第三组，置失败标志为1，转到步骤C；F、循环操作步骤C、D、E，直到依次所有正则式都尝试结束；G、将第三组中的正则式放到第一组中，尝试对第一组生成DFA，若成功，则分组结束，若失败则可对第三组重新分组，转到步骤A。