An Optimal Algorithm for Matching String Patterns in Large Text Databases

摘要

Modern parallel distributed string matching algorithms are always based on networked computation model. Those algorithms depends on the cost optimal design and the theoretical speed. The motive of current research challenges and identified the new directions I.e distributed environment where in which the given text file is divided into subparts and distributed to PI to PN no. of processors organized in parallel environment called as hypercube network. Based on the distributed memory machine string matching algorithms proposed by CHEN and BI-Kun, a optimal algorithm for matching string patterns in large text databases over parallel distributed hypercube networked architecture is proposed in this paper. And also an improved parallel string matching algorithm based on a variant Boyer-Moore algorithm is presented. We implement our hype and integrated algorithms on the above architecture and the experiments are proven that it is truly practical and efficient on parallel distributed Hypercube networked model. Its computation complexity is O(T/p + m-1), where T is text file of length n characters, and m is the length of the pattern, and p is the number of the processors.