AN IMPROVED PATTERN MATCHING ALGORITHM USING BIT-PARALLELISM TECHNIQUE


. Bit-parallelism algorithms play an important role in pattern matching due to the length of pattern sizes that can be processed in parallel. The major drawbacks of the existing bit-parallelism algorithms are in terms of input pattern length and limitation of computer word size in searching pattern length in a given text. Hence, this paper developed an improved pattern matching (IPM) algorithm for searching an exact pattern in a given text using the bit-parallelism method. IPM algorithm consists of two stages: pre-processing and searching stages. In the pre-processing stage, the algorithm calculates an alignment matrix by shifting the window of pattern m over the text, computes the shift ch to shift values, and mask the matrix of input pattern by encoding the alignment matrix in binary numbers, which serve as input data to the searching stage that locates the position of the pattern in a given text. The implementation of the algorithm was carried out to determine the run times for computer word size (64 bits, CWS) with pattern length ranging from 8 to 72 characters. The performance of IPM algorithm was evaluated and compared with the existing Backward non-deterministic matching (BNDM) and two variants of BNDM algorithm using 64 bits and 72 pattern characters. The evaluation results for IPM algorithm at 64 bits and 72 pattern characters showed a lower running time of 42ms compared to running time of 75ms, 69ms and 60ms for existing BNDM, SBNDM and FSBNDM algorithms respectively