An Improved WM Pattern Matching Algorithm Based on Cuckoo Filter

Pattern matching algorithms are widely used in fields such as traffic classification and management, user behavior analysis, and more. The increasingly large and complex network traffic poses significant challenges to feature matching processes. The cuckoo filter, capable of quickly determining whether an element is in a set, can be combined with pattern matching algorithms to accelerate feature matching. Building upon previous research, we propose an improved Wu-Manber (WM) algorithm that further reduces the size of the hash table generated during preprocessing, decreases the number of hash computations, and incorporates a cuckoo filter to eliminate unmatched text prefixes. This improved WM algorithm considers factors affecting algorithm performance, such as the large scale of the pattern set and the prevalence of repeated pattern string suffixes. Experimental results demonstrate that our proposed algorithm, Fast Parallel Wu-Manber (FSPRWM), significantly enhances matching speed while effectively reducing memory consumption.