朱 俊

（1.合肥工业大学计算机与信息学院，合肥 230009；2.安徽水利水电职业技术学院电子信息工程学院，合肥 231603）

入侵检测系统（Intrusion Detection Systems，IDS）不仅能够识别出网络中的入侵行为，还能检测出网络中的漏洞信息，从而采取相应对策进行处理和防范，阻止入侵行为带来的危害.入侵检测方法主要分为异常检测和误用检测两大类.异常检测主要采用统计分析的方法，常用的有：神经网络、人工免疫、统计模型、数据挖掘等［1］.误用检测主要采用模式匹配的方法，模式匹配技术的过程通常是提前将特征信息提取出来，存放到模式库中，再把收集到的数据与模式库中的特征信息进行比对，从而发现入侵行为.当今，模式匹配技术是入侵检测系统主要采用的方式.随着计算机网络技术的飞速发展，网络带宽的使用量增长迅速，单位时间传输的数据呈几何倍数增加，规则数量随之增加，所带来的最大问题是如何快速地进行检测.构建有限自动机对于模式匹配来说非常有效.构建有限自动机后，对每个文本字符只需要进行一次遍历，因而在时间复杂度上有很大的优势，构建有限自动机所花费的时间复杂度通常为O（n）［1-2］.但是，在输入字符集元素很庞大的情况下，建立有限自动机所花费的时间就会大大地增加.

为了充分发挥确定性有限自动机（deterministic finite automata，DFA）速度快的优势，对其存储空间的算法进行优化具有重要意义.如果有多条正则表达式构造成一个DFA，则各个规则会有相同……