【摘要】 本发明涉及一种在深度包检测系统中使用的正则表达式存储压缩方法，包含 两个组成部分：基于正则表达式膨胀率的分片重组方法和基于正则表达式膨胀 率的分群方法，分别从单个正则表达式的角度和正则表达式集合的角度对正则 表达式进行存储空间压缩。其中基于正则表达式膨胀率的分片重组方法通过将 正则表达式切片后分成至多头部，中部和尾部三个部分，而基于正则表达式膨 胀率的分群方法通过将正则表达式选择性分群，在存储空间总量控制的前提下， 将正则表达式集合分成了不同的群，其中群个数远远小于正则表达式个数。 ： 【专利类型】发明申请 【申请人】中国科学院计算机网络信息中心 【申请人类型】机关团体 【申请人地址】100190北京市海淀区中关村南四街四号 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810135202.1 【申请日】2008-08-04 【申请年份】2008 【公开公告号】CN101645069A 【公开公告日】2010-02-10 【公开公告年份】2010 【授权公告号】CN101645069B 【授权公告日】2013-09-11 【授权公告年份】2013.0 【发明人】葛敬国; 徐乾; 鄂跃鹏; 游军玲; 牛广锋; 吕红蕾 【主权项内容】1.一种多模式匹配中使用的正则表达式压缩方法，包含基于正则表达式膨胀率的分片重组和 基于正则表达式膨胀率的分群两个部分： (1)基于正则表达式膨胀率的分片重组操作步骤： 1)将输入的基于正则表达式处理成由ET1和ET2类型片交叉连接而成的串结构。 2)从串结构的最后一个类型片开始，依次将各类型片作为中部，中部前面的所有类 型片重组成头部，中部后面的所有类型片重组成尾部，形成分片方案。 3)对于每种分片方案，分别计算头部、尾部的膨胀率DR，若头部、尾部的膨胀率 DR小于设定的阀值，接受这个分片方案，若头部、尾部的膨胀率DR不小于设定 的阀值，拒绝这个分片方案。 (2)基于正则表达式膨胀率的分群操作步骤： 1)计算规则集合中的所有正则表达式膨胀率DR，按照膨胀率DR升序为正则表达式 进行排序，编号。 2)初始化当前组合状态自动机为空。 3)从规则集合中选择未组合且DR值最小的正则表达式RE，试探加入当前的组合有 穷状态自动机，如果该正则表达式RE的加入没有导致当前组合有穷状态自动机剧 烈膨胀超过阀值且没有导致组合有穷状态自动机状态数超过阀值，标记当前正则 表达式RE为已组合；如果该正则表达式RE的加入导致当前组合有穷状态自动机 剧烈膨胀超过阀值或者导致组合有穷状态自动机状态数超过阀值，则将组合有穷 状态自动机回退到RE加入前的状态。 4)依次试探规则集合中所有正则表达式后，输出当前组合状态自动机中的所有正则 表达式作为一个分群结果，转至步骤2)，直到规则集合中的正则表达式全部完成 了分群。 【当前权利人】中国科学院计算机网络信息中心 【当前专利权人地址】北京市海淀区中关村南四街四号 【统一社会信用代码】12100000400884052P 【被引证次数】TRUE 【家族被引证次数】TRUE
