Research On Key Technologies Of Massive Amout Multi-pattern Matching Algorithm

The string matching problem is a classical problem. Since the KMP algorithm wasproposed in1971, string matching has developed very much. Now it includes many areassuch as multi string matching, regular matching and approximate matching. With thedevelopment of computer internet technology and the improvement of society, the stringmatching has been used widely. You can find the matching problem in information retrieval,intrusion detection and network data analysis. The boolean expression matching also hasmany applications such as the Boolean query in information retrieval, the featurescombinating of the virus in virus detection system. The experiments people have done beforeare always on the small scale pattern set, there is no available experiments on large scalepattern set like many millions.What this paper studies is divided into two parts:Through studying the features and difficulties of the string matching problem on the largescale pattern set, we proposed many improvements of the wu-manber algorithm: theimprovement by hashing with the shortest keyword length, the improvement by using multihash algorithms to do pre-check, the improvement by comparing two strings with blocks.Through studying the problem of boolean expression matching, we proposed a newproblem called complicated and/or boolean expression matching problem. Beside, we alsoproposed a new method to reduce the number of boolean expression.In summary, on the basis of the algorithms on the pattern matching problem and booleanexpression matching problem, we put our eyes on the study of the pattern matching algorithmon large scale pattern set and the complicated and/or boolean expression matching problem.Then we do expriments to support them. In the last, this article also look forward to the futuretrends in these fields.