Improved Rabin-Karp Algorithm Using Bloom Filter
Masoumeh Moeini, Hadi Shahriar Shahhoseini · 2022
String matching algorithms are used widely in computer science that is a very important issue in text processing. Also, string matching algorithms are used as basic components in the practical software in operating systems. A lot of research is performed in this field that hash based matching algorithms like Rabin-Karp is one of their fastest, but due to the rapid growth of data volumes, traditional algorithms are not sufficient. To solve this problem, combining Bloom filter features with string matching algorithms, makes it possible to reduce the execution time. In present paper, a modified version of the Rabin-Karp algorithm is presented by using a Bloom filter as preprocessing phase that can early detect pattern absence. In addition, this approach maximize speed up and reduce the number of patterns needed for the exact Rabin-Karp matching phase. Accordingly, the proposed results as well as the Rabin-Karp implementations have been compared to verify the impact of the proposed method.