Research and improvement of a multi-pattern matching algorithm based on double hash
Yansen Zhou, Cun Gao · 2017
Multi-pattern matching is a matching algorithm that searches multiple pattern parallel in the given text. According to problems of the existing multi-pattern matching algorithm, the paper puts forward a multi-pattern matching algorithm based on double hash. The improved algorithm could reduce the number of comparison each matching by two hashes, whose hash table used to store patterns is a two-dimensional array of pointers. Each node represents head node of a single list in the two-dimensional array, all nodes of a single list with the same length and prefix hash of pattern string. Through the hash physical structure, text substring needs also two hashes in each matching to find the corresponding hash. It needs complete matching if finding node with the same value of hash of two times in this physical structure. Otherwise, the matching pointer of text string moves to the right quickly by jump distance of BM2 algorithm based on the multi-pattern strings. The experiment shows that the time performance of TH_MPMA algorithm is better than that of AC_BM2 algorithm under the same test environment.