The Research For Single-pattern Matching Algorithm Based On BM And BMHS

With the fast development of the Internet, the network contents"garbage"has already invaded our life.Content filtering can effectively prevent the spread of harmful information,it has become significant problems in network security.Pattern matching algorithm is the core technology of content filtering, the classic pattern matching algorithm-BM algorithm adoptes goodsuffix jump rules and badchar jump rules.BMHS algorithm is a simplication of BM algorithm, only using badchar jump rules.This dissertation introduced the present condition of the content safety and the research contents, analysised the classic single-pattern matching algorithm, proposed a fast single-pattern matching algorithm(FSBM).This algorithm combines the advantages of BM and BMHS algorithm,combines goodsuffix and the information carried by the character which is next after the current window, increase the probability of occurrence of the largest shift (m+1),improves the matching speed effectively.Based on the analysis of Netfilter firewall frame, content filtering module is designed.Testing BM,BMHS and FSBM algorithms in the same network environment.Test shows FSBM algorithm is dominant on matching efficiency and distinctly improves the speed of firewall detecting illegal words.