Research of a Pattern Matching Algorithm Based on Statistical Eigenvalues

摘要

The pattern matching algorithm has important influence on the performance of intrusion detection engine. Firstly, Paper analyses principle of the classic matching algorithm, including characteristic value and BMHS2 and frequency statistics algorithm. BMHS2 algorithm has a larger right moving distance when mismatching, the eigenvalue algorithm effectively reduces the number of matches by comparing the eigenvalue, the word frequency statistic algorithm can find the mismatch character as soon as possible. The improved single pattern algorithm firstly uses the frequency statistics method, the character of the lowest frequency in the pattern string is matched with the corresponding character of the text string; if matching, eigenvalue algorithm is used to compare the eigenvalue of pattern string and text substring; if it is still matching, the BMHS2 algorithm is used to fully match. In the above matching processes, if there are any mismatches, it uses computed right-move distance of BMHS2 algorithm to move the right. Test experiments show that in the same text string and pattern string, improved algorithm reduces the number of character matching and the matching performance is improved.