一种规则集快速压缩算法  

A Fast Compression Algorithm for Rule Set

作　　者：王坤[1] 顾乃杰[2] 任开新 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]安徽省计算与通讯软件重点实验室,合肥230027 [3]网络与通信联合实验室,合肥230027

出　　处：《小型微型计算机系统》2012年第8期1787-1790,共4页Journal of Chinese Computer Systems

基　　金：核高基重大专项(2009ZX01028-002-003-005)资助

摘　　要：实际应用中的规则集表现出很强的聚集特性,针对这一特性提出一种规则集快速压缩算法.快速压缩算法是一个由粗到细的先分类再合并压缩的过程,首先通过使用Hash函数将提取的规则信息散列并以散列值作为查找关键字构建二叉查找树实现粗略分类,然后在树结点对应的Hash函数冲突列表中逐条比较完成精确分类,最后合并冲突列表中的规则实现压缩.实验结果表明,与逐条规则逐个域比较的简单压缩方法相比,快速压缩算法在保持较高压缩率的前提下,能够将压缩时间平均减少90%以上.Rule set exhibit great aggregation character in practice.We propose a fast compression algorithm for rule set according to this feature in this paper.This algorithm is a coarse-to-fine process that it firstly classifies rules,and then merges them.The algorithm uses the hash function to hash the extracted rule information and constructs binary search tree using the hash value to achieve coarse classification,then completes fine classification in hash function conflict tables of specific tree nodes,and finally merges rules in the table to complete the compression process.The experiments show that the fast compression algorithm has rapid compression speed with little harm to compression rate,and reduces more than 90% compression time for larger rule set,comparing to simple compression solution of exhaustively comparing each rule and each field of the rule.

关 键 词：规则集 快速压缩 HASH函数 二叉查找树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]