Analysis and Optimization of the Boyer-Moore Pattern Searching Algorithm: Sequential and MPI-based Parallel Implementation

The unprecedented acceleration in textual data generation and the growing complexity of text analysis applications have made it essential to employ pattern searching algorithms that can deliver high speed, reliable accuracy, and broad scalability simultaneously. Addressing this challenge, the selection and enhancement of algorithmic solutions is not merely a technical choice, but a strategic decision for the survival of information processing systems in the era of big data and advanced computing. The Boyer-Moore algorithm, thanks to its intelligent architecture and near-linear performance, has long been the standard reference for pattern searching in large-scale data. However, its sequential version faces fundamental limitations when handling massive datasets and real-time processing demands. In this study, the sequential version of the algorithm was first implemented with an optimized approach and evaluated across a diverse range of real-world data. Subsequently, a parallel version based on the MPI framework was developed and rigorously tested in academic HPC environments and on a multi-core university Linux server supporting up to ۳۲ processing cores. Experimental results showed that the parallel version succeeded in reducing the algorithm’s execution time from ۳۳ milliseconds to less than ۲ milliseconds, achieving parallel speedup of up to ۱۶× and parallel efficiency of up to ۹۵% on the initial cores. Moreover, testing with up to ۳۲ processing cores demonstrated that the parallel algorithm maintained nearly linear scalability and speedup at this scale, with only a gradual decline in efficiency observed at much larger scales. These achievements confirm the unrivaled potential of parallel architectures in advancing pattern search performance and pave the way for even faster and more scalable implementations in future text mining and scientific applications.

Keywords:

Boyer-Moore Algorithm , Pattern Matching , Parallel Computing , MPI