Multiple Patterns Match Algorithm Research

The character string pattern matching algorithm is in the computer science a key field, widely applies in the search engine, computer virus domains and so on condition code match, network invasion examination.First, this dissertation introduced the pattern matching research's background, the significance and the research present situation, have outlined the pattern matching technology, including pattern matching principle, pattern matching examination rule, pattern matching system characteristic, pattern matching algorithm classification and so on.This dissertation then summarized the classical pattern matching algorithm, including the single model type matching algorithm BM algorithm, BF algorithm and so on and multi-pattern matching algorithm AC algorithm, AC-BM algorithm and so on. Has analyzed the AC algorithm, proposed one kind of improvement's multi-pattern matching algorithm IAC algorithm, described the improvement algorithm basic philosophy, has analyzed the improvement algorithm pretreatment stage, the match stage and the motion rule, and to improved the algorithm the time order of complexity and the spatial order of complexity has carried on the analysis, finally has carried on the test to the improvement algorithm. The test result indicated that compares with the standard AC algorithm, the improvement algorithm has certain reduction in the comparison number of times, improves in the time behavior.At last, this dissertation has made the summary and the forecast to the pattern matching algorithm.