机群系统上基于Hashing的多目标串匹配并行算法

基于孙子定理构造均匀的Hash函数并继承Karp-Rabin模式匹配思想，利用“筛选”方法，给出一种机群系统上的多目标串匹配并行算法。通过预处理将字符串映射成惟一的一对整数值，采用比较一对整数值来取代逐个字符比较字符串的方法使得匹配过程快速且比较结果是确定的：“筛选”节省了比较时间。算法分析和实验结果表明该并行算法简明、高效和可扩展。

A Hashing-Based Parallel Algorithm for Multiple Object String Matching on the Cluster Computing Systems

Based on the Chinese Remainder Theorem, a perfect Hash function for processing string is constructed, and a parallel algorithm for multiple object string matching on the cluster computing systems is presented by applying the Karp-Rabin pattern matching approach and the filter technique. In this algorithm, a given string is uniquely mapped to a pair of integer values, the pair of integer values is compared to implement the string matching procedure. The comparison and filter techniques can speed up the matching process and obtain the determinate match results. The algorithm analysis and experimental results show that the parallel algorithm is concise, efficient and scalable.