一种均衡分两组编译正则表达式的方法

摘要

本发明提供了一种均衡分两组编译正则表达式的方法，充分了利用片外资源，使FPGA能够两路进行匹配，采用最大割的方法来进行分组，使n条正则式生成两组状态数较为均匀的DFA，降低其空间复杂度，这样，在不降低实时性的同时，硬件空间不变，尽可能多的增加了硬件处理正则式的数量。

主权项

一种均衡分两组编译正则表达式的方法，其特征在于：步骤如下：A、读取N条正则式；B、生成两两间状态数矩阵和两两间状态矩阵之和；C、根据步骤B得到的结果，粗分两组1、2；分配的基础是两两间状态数之和最大的规则，将其两两间状态数队列按照由大到小排序，将所有正则式分成两组，1组的正则式数目较2组稍多；D、初始化变量i，将其设置为1组的最后一个正则式的索引；E、将1组元素i移到2组；F、计算1、2间的两两状态数的之和；G、和上一次的1、2间的两两状态数的之和比较。如果大于old_state_sum，则更新old_state_sum为state_num；如果小于等于old_state_sum，则将元素i移回A组；H、变量i减1；I、判断i是否为‑1，如果是则执行下一步骤，如果不是，则回到步骤E，使1组的正则式都能遍历一遍，是否应该移入2组；J、编译1组和2组，得到较均衡的两组DFA，两组状态数量相差不大。