MPI并行编程系列之四:KMP算法及并行化 - 飞得更高

时间:2024-04-15 19:32:40

    串匹配问题是计算机科学中的一个基本问题,在文字编辑、图像处理等利于都得到了广泛的应用,串匹配算法在这些应用中起到至关重要的作用。因此研究快速的串匹配算法具有重要的理论和实际意义。

    KMP是一种改进的字符串模式匹配的算法,他能够在o(m+n)时间复杂度内完成字符串的模式匹配算法。本文将详细的介绍KMP算法的思想,串行及并行实现。

一、KMP算法思想

    1、问题描述

     给定主串S[0...n-1]、模式串T[0...m-1],其中m<=n。在主串S中找出所有模式串T的起始位置。

    2、算法思想

    令指针i指向主串S,指针j指向模式串T中当前正在比较的位置。令指针i和指针j指向的字符比较之,如两字符相等,则顺次比较后面的字符;如不相等,则指针i不动,回溯指针j,令其指向模式串T的第pos个字符,使T[0...pos-1] == S[i-pos, i-1],然后,指针i和指针j所指向的字符按此种方法继续比较,知道j == m-1,即在主串S中找到模式串T为止。

    从算法的思想思想中我们可以看出,其算法的难点在于如何求出指针j的回溯值,即:当指针j回溯时,j将指向的位置,我们几位next[j]。下面我们首先对kmp的算法做出详细的描述。   

二、KMP算法描述

      输入:主串S[0...n-1], 模式串T[0...m-1]

     输出:m[0...n-1],当m[i] = 1时,则主串S中匹配到模式串,且i为起始位置

     begin

         i = 0; j = 0;

         while(i < n)

                if(S[i] != T[j])

                   j = next[j]

                   if( j == -1)

                       i++   j++

                  endif;

                 contiue;

               endif

              if (j == m-1)

                   m[i-j+1] = 1

                   j = -1

                   i = i-j+1

              endif

              i++    j++

        end while

    end

   在上面的算法描述中,next函数的编写为整个算法的核心,设计出快速正确的next函数也为KMP算法的重中之重。如何设计我们的next函数呢,我们利用递推思想:

    1)令next[0] = -1,(为什么要等于-1呢,从上面的算法可以看出,当next[j] == -1时,证明字符串匹配要从模式串的第0个字符开始,且第0个字符并不和主串的第i个字符相等,i指针向前移动。)

   2)假设next[j] = k ,说明T[0..k-1] == T[j-k...j-1]

   3)  现在我们来求next[j+1]

             3.1 当T[j] == T[k]时,说明T[0..k] == T[j-k..j],这时分为两种情况讨论:

                    3.1.1 当T[j+1] != T[k+1],显然

                         next[j+1] = k+1;

                    3.1.2 当T[j+1] == T[k+1],当这两个字符相等时,说明T[k+1]和T[j+1]一样,都不和主串的字符相匹配,因此:

                            m = k+1, j=next[m] 直到T[m] != t[j+1]                       

                            next[j+1] = m

             3.2  当T[j] != T[k]时,我们必须在T[0..k-1]中找到next[j+1],这时:

                       k = next[k],直到T[j] ==T[k] 

                       next[j+1] = next[k]

     这样我们就通过数学中递推的方式求得了匹配串T的next函数。

三、串行实现

     有了以上的算法描述,我们可以编写我们的kmp串行实现,本文不想黏贴过多的代码,仅仅给出next函数的实现:

   1:  int *get_next(char *match_string, int match_string_length){
   2:   
   3:      int *next;
   4:      int next_index;
   5:   
   6:      int i;
   7:   
   8:      next = (int *)my_malloc(sizeof(int) * match_string_length);
   9:   
  10:      next[0] = -1;
  11:      i =0;
  12:      next_index = -1 ;
  13:   
  14:      while(i < match_string_length){
  15:   
  16:          if(next_index == -1 || match_string[next_index] == match_string[i]){//对应于3.1
  17:              i++; 
  18:              next_index++;
  19:   
  20:              if(match_string[i] != match_string[next_index])//对应于3.1.1
  21:                  next[i] = next_index;
  22:              else//对应于3.1.2
  23:                  next[i] = next[next_index];
  24:          }
  25:          else//对应于3.2
  26:              next_index = next[next_index];
  27:      }
  28:   
  29:      return next;
  30:  }

四:并行算法

     现在我们考虑如何将KMP算法并行化,我们很容易考虑到得是将主串S平均分成P段(假设有p个处理器),每个处理器处理其中的一段。但这时要考虑一个问题,那就是如何处理每段字符串最后m-1个子字符串的匹配问题,因为这m-1个字符可能会和其后一段的前t个字符共同构成模式串。我们首先考虑到得是每个处理器将其负责字符串的后m-1个字符的字串发送给其后面的处理器,但这样会造成通信过大的问题,每个处理器都要发送m-1个字符。如何减少处理器间的通信呢?起始我们只需发送和模式串前t个字符想匹配的t个字符就可以了。这样就减少了进程间的通信。其算法描述如下:

    输入:主串T[0...n-1],模式串S[0...m-1]

   输出:m[0...n-1],当m[i] = 1时,则主串S中匹配到模式串,且i为起始位置

   条件:t个处理器

  1)p0读取主串和模式串,将模式串广播到起到所有的处理器中,并将主串分段发送到其对应的处理器中

  2)处理器并行计算next函数,这样每个处理器都有统一的next函数和模式串

  3)处理器p0 ,p1,...,pt-1并行计算各自负责字符串的后m-1个字符的字串和模式串的最小匹配串,并将最小匹配串发往下一个处理器

  4)处理器接收上个处理器发送的字符串,并和本身的字符串合并成一个新的字符串

  5)各处理器并行计算匹配结果m

  6)处理器p0对各处理器的匹配结果进行整合,得到最终结果。

   因为kmp并行算法相对简单,也没有用到新的MPI函数,这里不列出其并行实现代码。

   下一篇:图论:单源最短路径的并行算法