节点文献
基于字频的模式匹配算法研究
Research on A Pattern Matching Algorithm Based on Word Frequency
【作者】 洪涛;
【导师】 侯整风;
【作者基本信息】 合肥工业大学 , 计算机系统结构, 2010, 硕士
【摘要】 随着Internet环境的不断复杂以及数量的不断增加,要求防火墙、VPN、PKI、入侵检测等技术更加的快速、高效。模式匹配能有效支持网络内容安全并提高网络设备的性能,是高速网络的关键技术之一。本文介绍了模式匹配的研究背景、发展和研究现状,探讨了防火墙、入侵检测等网络内容安全的关键技术,分析研究了经典模式匹配算法。针对已有模式匹配算法存在的不足,提出了一种基于字频的模式匹配算法——BCFM算法。该算法首先建立一个字符使用频率表,根据使用频率表找出模式串中使用频率最低和次低的字符,并记录它们的相对位置。当模式匹配时,首先查找出文本中使用频率最低的字符,然后直接将其相应位置上的字符与使用频率次低的字符进行匹配,迅速完成匹配过程。BCFM算法对字符定位较准确,从而提高了模式匹配的效率。本文还对防火墙和入侵检测技术进行了分析和研究。最后,通过实验对BCFM和BM算法的性能进行了测试和比较。实验结果表明,BCFM算法具有较好的时间效率,并且在模式串较短、文本较长时作用发挥的更加明显。
【Abstract】 The more rapid and efficient of technology such as firewall, VPN, PKI and intrusion detection is required by the increasing complexity of Internet environment and the increasing number of Internet. Pattern matching which is able to effectively support network content security and improve the performance of network equipments is one of the most important high-speed network.In this thesis, the research background, development and current research status of pattern matching are written first, followed by the related technology of content security as well as firewall and intrusion detection. After that, typical pattern matching algorithms are described and analyzed. To improve the shortage of pattern matching algorithms, a pattern matching algorithm based on word frequency, which is named BCFM, is proposed here. This algorithm establishes a character frequency table firstly, then finds the lowest frequency character and the second lowest frequency character according to this table, and records their relative position. When the pattern matches, it will be find out the lowest frequency characters in the text firstly, then the character on the relative position with the second lowest frequency character to match directly. The matching process is completed quickly. BCFM algorithm is more accurate for character positioning than other algorithms, so it increases the efficiency of pattern matching.Firewall and intrusion detection is also investigated here. Finally, an experiment is completed to test and compare the performance of BM and BCFM. The results indicate that BCFM is provided with preferable efficiency on time. It is more efficiency when pattern is shorter and text is longer.
【Key words】 pattern matching; content security; fire wall; intrusion detection;