A fast improved multiple pattern matching algorithm
Al-Khadher Al-Qiari, Yazan Al-Issa · 2018
This paper presents a novel, fast and scalable multiple string searching algorithm that can locate many keywords within a larger text in a single pass. The new Wu-Manber variation can search for millions of patterns with short lengths in a very large text effectively and efficiently. This paper conducts an empirical evaluation that shows that the average running time of the classical Wu-Manber algorithm increases exponentially as the number of patterns increases. On the contrary, the average running time of the proposed algorithm is linear with respect to the number of patterns. In practice, the proposed Quick Pattern Search algorithm is two times better than the classical Wu-Manber algorithm in terms of latency and memory utilization. The new algorithm outperforms the traditional Wu-Manber algorithm regardless of the pattern length. The shorter the pattern length, the higher the gain obtained using the proposed algorithm. The results presented in this paper will have a profound impact on the search engines, bioinformatics, security, virus detection, and network intrusion fields. The Quick Pattern Search algorithm will shorten the response time and improve the overall user experience which will largely benefit the internet industry.