An improved W-M algorithm for multi-pattern match
Yuhong Zhang · Mechanical & Electrical Engineering Magazine · 2008
Wu-Manber algorithm is one of the multi-pattern match algorithm based on the suffix searching.The algorithm speeds up matching by looking up tables to ignore certain characters that will not be matched.W-M algorithm is sensitive to minimum length of pattern which determines the maximum number of characters that can be ignored.Aimed at the shortage of W-M algorithm the improvement was proposed.A new table of last character of each pattern was added,the times of hash calculation were reduced,more characters were ignored and the matching process was speeded up.In the contrast experiments that setting the minimum length of pattern and the length of text,the efficiency of improved algorithm is much better than original algorithm,especially when there are very short patterns.