平衡二叉树在穷举检测器生成算法中的应用

Application of Balanced Binary Tree in Exhaustive Detector Generation Algorithm

在基于人工免疫原理的入侵检测系统中,由于标准的穷举检测器生成算法没有很好地消除重复检测器,从而造成失败率增高等问题。标准的穷举检测器生成算法采用的是链表存储结构。如果在链表存储结构的基础上消除重复检测器,是非常耗时的。针对这个问题,提出了改进的穷举检测器生成算法,该算法利用了平衡二叉树结构存储检测器,以达到在尽可能短的时间内消除重复检测器的目的。经过实验证明,在平衡二叉树结构下消除重复检测器可以比在链表结构下进行同样的操作节省很多时间。

In IDS based on artificial immune principle, the standard exhaustive detector generation algorithm can not avoid generating detectors which are the same, so it makes the IDS not so efficient, and there will be more failures. Linked list is used in the standard exhaustive detector generation algorithm to store detectors. It will waste lots of time if we remove the detectors which are the same in that standard algorithm. For reasons above, an improved exhaustive detector generation algorithm is proposed to overcome these disadvantages. Balanced binary tree structure is used in this algorithm to store detectors to make the detectors distinct from each other in a time as short as possible. It is proved by experiments that the improved algorithm using balanced binary tree can save time to a great extent to remove the same detectors compared with the algorithm using linked list structure.