app_match.c
上传用户:hhyinxing
上传日期:2013-09-10
资源大小:833k
文件大小:9k
源码类别:

并行计算

开发平台:

Unix_Linux

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <sys/stat.h>
  7. #include <sys/types.h>
  8. #include <mpi.h>
  9. typedef struct{
  10. int pedlen;
  11. int pednum;
  12. int psuffixlen;
  13. }pntype;
  14. /*
  15. void gen_string(int stringlen,char *string,int seed)
  16. 输入:待生成的文本串长度: int stringlen;
  17.        
  18. 输出:待匹配的文本串: char *string;
  19. 功能:生成待匹配的文本串
  20. void gen_pattern(char *text,int *patlen,char *pattern,int seed)
  21. 输入:待匹配文本 char *text;
  22.       待生成的匹配串长度: int *patlen;
  23. 输出:生成的匹配串: char *pattern;
  24. 功能:从文本串中选择连续的一段作为待匹配的模式串
  25. int Min(int x,int y,int z)
  26. 输入:三个整型数 int x,int y,int z;
  27. 输出:三个整数中选择最小的一个 int Min();
  28. 功能:从三个整数中选择最小的一个
  29. void ModifiedDP(char *T,char *P,int textlen,int patternlen,int k,int *D)
  30. 输入:待匹配的文本串: char *T;
  31.       匹配串:char *P;
  32.   文本串长:int textlen;
  33.   匹配串长:int patternlen
  34. 输出:模式串P的前缀子串p1…pi与文本串T的任意
  35.       以tj结尾的子串之间的最小误差个数(即最小编辑距离)int *D;
  36. 功能:允许换位操作的动态规划近似串匹配算法
  37. void Next(char *P,int patlen,int *nextval,pntype *pped)
  38. 输入:匹配串 char *P;
  39.       匹配串长: int patlen;
  40. 输出:int *nextval;
  41. 功能:对输入串进行周期分析并生成next以及nextval值
  42. void Search(char *T,char *P,int textlen,int patlen,int *nextval,
  43. pntype *pped,int k,int *D,int SubpatternStart,char *pattern,int patternlen,int *VerifyCount)
  44. 输入:原文本串: char *T;
  45.       匹配串: char *P;
  46.   原文本串长: int textlen;
  47.   匹配串长: int patlen;
  48.   近似匹配允许的最大误差数: int k ;
  49.   最小编辑距离: int *D;
  50. 输出:精确匹配点
  51. 功能:允许换位操作的过滤近似串匹配算法
  52. int SubPatternLength(int patlen,int k,int num)
  53. 输入: 匹配串长: int patlen;
  54.        近似匹配允许的最大误差数: int k ;
  55. 输出:子模式串长
  56. 功能:将模式串划分为2k+1个子模式串
  57. */
  58. /*生成待匹配的文本串*/
  59. void gen_string(int stringlen,char *string,int seed)
  60. {
  61. int i,num;
  62.   srand(seed*100);
  63. for (i=0;i<stringlen;i++) {
  64. num=rand()%26;
  65. string[i]='a'+num;
  66. }
  67. string[stringlen]='';
  68. }
  69. /*从文本串中选择连续的一段作为待匹配的模式串*/
  70. void gen_pattern(char *text,int *patlen,char **pattern,int seed) 
  71. {
  72.   int start;
  73.   if ((*pattern=(char *)malloc((*patlen+1)*sizeof(char)))==NULL) {
  74. printf("Error alloc memory.n");
  75. exit(1);
  76.   }
  77.   srand(seed*100);
  78.   start=rand()%strlen(text)/3;
  79.   strncpy(*pattern,text+start,*patlen);
  80.   *(*pattern+*patlen)='';
  81. }
  82. /*从三个整数中选择最小的一个*/
  83. int Min(int x,int y,int z)
  84. {
  85. int minimum;
  86.   minimum=(x<y?x:y);
  87.   minimum=(minimum<z?minimum:z);
  88.   return minimum;
  89. }
  90. /*允许换位操作的动态规划近似串匹配算法*/
  91. void ModifiedDP(char *T,char *P,int textlen,int patternlen,int k,int *D)
  92. {
  93.   int i,j;
  94.   int *D1,*D2;
  95.   if (((D1=(int *)malloc((textlen+1)*sizeof(int)))==NULL)||
  96. ((D2=(int *)malloc((textlen+1)*sizeof(int)))==NULL)) {
  97. printf("Malloc error.n");
  98. exit(1);
  99.   }
  100.   for (j=0;j<=textlen;j++) {
  101. D1[j]=0;
  102.   D2[j]=0;
  103.   }
  104.   for (i=1;i<=patternlen;i++) {
  105. D[0]=i;
  106.       for (j=1;j<=textlen;j++) {
  107.      if (P[i-1]==T[j-1])
  108.      D[j]=Min(D2[j]+1,D[j-1]+1,D2[j-1]);
  109.   else if (i-2>=0 && j-2>=0 && P[i-1]==T[j-2] && P[i-2]==T[j-1])
  110.      D[j]=Min(D2[j]+1,D[j-1]+1,D1[j-2]+1);
  111.     else
  112.              D[j]=Min(D2[j]+1,D[j-1]+1,D2[j-1]+1);
  113.       }
  114.   for (j=0;j<=textlen;j++) {
  115.           D1[j]=D2[j];
  116.   D2[j]=D[j];
  117.       }
  118.   }
  119.   free(D1);
  120.   free(D2);
  121. }
  122. /*对输入串进行周期分析并生成next以及nextval值*/
  123. void Next(char *P,int patlen,int *nextval,pntype *pped)
  124. {
  125.   int i,j;
  126.   int *next;
  127.   if ((next=(int *)malloc((patlen+1)*sizeof(int)))==NULL) {
  128. printf("No enough memory.n");
  129. exit(1);
  130.   }
  131.   next[0]=nextval[0]=-1;
  132.   j=1;
  133.   while (j<=patlen) {
  134.     i=next[j-1];
  135.     while (i!=-1 && P[i]!=P[j-1])
  136. i=next[i];
  137.     next[j]=i+1;
  138.     if (j!=patlen) {
  139.    if (P[j]!=P[i+1])
  140. nextval[j]=i+1;
  141.    else
  142.   nextval[j]=nextval[i+1];
  143.         }
  144.         j++;
  145.   }
  146.   pped->pedlen=patlen-next[patlen];
  147.   pped->pednum=(int)(patlen/pped->pedlen);
  148.   pped->psuffixlen=patlen%pped->pedlen;
  149.   free(next);
  150. }
  151. /*允许换位操作的过滤近似串匹配算法*/
  152. void Search(char *T,char *P,int textlen,int patlen,int *nextval,pntype *pped,int k,int *D,int SubpatternStart,char *pattern,int patternlen,int *VerifyCount)
  153. {
  154.   int i,j,p;
  155.   int VerifyStart,VerifyEnd,VerifyLength;
  156.   int *TempD;
  157.   if ((TempD=(int *)malloc((patternlen+2*k+1)*sizeof(int)))==NULL) {
  158. printf("Malloc error.n");
  159. exit(1);
  160.   }
  161.   i=0;
  162.   j=0;
  163.   while (i<textlen) {
  164.     while ((j!=-1) && (P[j]!=T[i]))
  165. j=nextval[j];
  166.     if (j==(patlen-1)) {
  167. (*VerifyCount)++;
  168. VerifyStart=i-patlen-SubpatternStart-k+1;
  169.            VerifyEnd=i-patlen-SubpatternStart+patternlen+k;
  170.    VerifyStart=(VerifyStart>0?VerifyStart:0);
  171.            VerifyEnd=(VerifyEnd<textlen-1?VerifyEnd:textlen-1);
  172.    VerifyLength=VerifyEnd-VerifyStart+1;
  173.            ModifiedDP(T+VerifyStart,pattern,VerifyLength,patternlen,k,TempD);
  174.    for (p=1;p<=VerifyLength;p++)
  175. D[VerifyStart+p]=(D[VerifyStart+p]<TempD[p]?D[VerifyStart+p]:TempD[p]);
  176.    
  177.    if (pped->pednum+pped->psuffixlen==1)
  178. j=-1;
  179.    else
  180. j=patlen-1-pped->pedlen;
  181.         }
  182.     j++;
  183.     i++;
  184.   }
  185.   free(TempD);
  186. }
  187. /*将模式串划分为2k+1个子模式串*/
  188. int SubPatternLength(int patlen,int k,int num)
  189. {
  190.   int r;
  191.   r=patlen%(2*k+1);
  192.   if (r==0) 
  193.   return(patlen/(2*k+1));
  194.   else if (num<=r) 
  195.   return(patlen/(2*k+1)+1);
  196.     else 
  197.      return(patlen/(2*k+1));
  198. }
  199. int main(int argc,char *argv[])
  200. {
  201.   char *T,*P;
  202.   int alltextlen,textlen,patternlen,k,subpatlen,startpoint;
  203.   int *nextval,*D;
  204.   pntype pped;
  205.   int i,l,myrank,groupsize;
  206.   int VerifyCount=0;
  207.   int TotalMatchCount=0,MatchCount=0;
  208.   MPI_Status status;
  209. char ch[1];
  210.   MPI_Init(&argc,&argv);
  211.   MPI_Comm_size(MPI_COMM_WORLD,&groupsize);
  212.   MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
  213.  
  214.   alltextlen=atoi(argv[1]);
  215.   patternlen=atoi(argv[2]);
  216.   k=atoi(argv[3]);
  217.   textlen=alltextlen/groupsize;
  218.   if (myrank==0) {
  219.      if (((T=(char *)malloc((textlen+patternlen+k)*sizeof(char)))==NULL)||
  220.    ((D=(int *)malloc((textlen+patternlen+k)*sizeof(int)))==NULL)) {
  221. printf("No enough memory.n");
  222.     exit(1);
  223. }
  224. for (i=0;i<=textlen;i++) D[i]=10000;
  225. /*生成本地文本串与模式串*/
  226.      gen_string(textlen,T+patternlen+k-1,myrank);
  227.      gen_pattern(T+patternlen+k-1,&patternlen,&P,myrank);
  228.      if ((nextval=(int *)malloc((patternlen/(2*k+1)+1)*sizeof(int)))==NULL) {
  229. printf("No enough memory.n");
  230. exit(1);
  231. }
  232.   }
  233. MPI_Barrier(MPI_COMM_WORLD);
  234.   if (groupsize>1) {
  235. if (myrank!=0) {
  236. if (myrank==groupsize-1)
  237. textlen=alltextlen-(groupsize-1)*(alltextlen/groupsize);
  238. if (((T=(char *)malloc((textlen+patternlen+k)*sizeof(char)))==NULL)||
  239.    ((D=(int *)malloc((textlen+patternlen+k)*sizeof(int)))==NULL)||
  240.            ((nextval=(int *)malloc((patternlen/(2*k+1)+1)*sizeof(int)))==NULL)||
  241.            ((P=(char *)malloc((patternlen+1)*sizeof(char)))==NULL)) {
  242.    printf("No enough memory.n");
  243.        exit(1);
  244.     }
  245.         for (i=0;i<=textlen+patternlen+k-1;i++) D[i]=10000;
  246.         /*生成本地文本串*/
  247.         gen_string(textlen,T+patternlen+k-1,myrank);
  248. }
  249. MPI_Barrier(MPI_COMM_WORLD);
  250. /*播送模式串给所有处理器,对应算法14.13步骤(2)*/
  251.      MPI_Bcast(P,patternlen+1,MPI_CHAR,0,MPI_COMM_WORLD);
  252. printf("on node %d the text is %s n",myrank,T+patternlen+k-1);
  253. printf("on node %d the pattern is %s n",myrank,P);
  254. /*播送进程间相关数据给相邻进程,对应算法14.13步骤(3)和(4)*/
  255. if(myrank==0) {
  256. MPI_Send(&T[textlen],patternlen+k-1,MPI_CHAR,myrank+1,myrank,MPI_COMM_WORLD);
  257. }
  258. else if(myrank==groupsize-1) {
  259.   MPI_Recv(&T[0],patternlen+k-1,MPI_CHAR,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  260. }
  261. else {
  262.   MPI_Recv(T,patternlen+k-1,MPI_CHAR,myrank-1,myrank-1,MPI_COMM_WORLD,&status);
  263. MPI_Send(T+textlen,patternlen+k-1,MPI_CHAR,myrank+1,myrank,MPI_COMM_WORLD);
  264. }
  265. }
  266.   MPI_Barrier(MPI_COMM_WORLD);
  267.   /*各进程分别对本地数据执行允许换位操作的过滤近似串匹配算法,对应算法14.13步骤(5)*/
  268.   startpoint=0;
  269. if(myrank==0)
  270.      for (l=1;l<=2*k+1;l++) {
  271.     subpatlen=SubPatternLength(patternlen,k,l);
  272.     if (subpatlen==0) continue; 
  273.     Next(P+startpoint,subpatlen,nextval,&pped);
  274.     Search(T+patternlen+k-1,P+startpoint,textlen,subpatlen,nextval,&pped,k,D,startpoint,P,patternlen,&VerifyCount);
  275.     startpoint=startpoint+subpatlen;
  276. }
  277. else
  278.      for (l=1;l<=2*k+1;l++) {
  279.     subpatlen=SubPatternLength(patternlen,k,l);
  280.     if (subpatlen==0) continue; 
  281.     Next(P+startpoint,subpatlen,nextval,&pped);
  282.     Search(T,P+startpoint,textlen+patternlen+k-1,subpatlen,nextval,&pped,k,D,startpoint,P,patternlen,&VerifyCount);
  283.     startpoint=startpoint+subpatlen;
  284. }
  285.   MPI_Barrier(MPI_COMM_WORLD);
  286.  
  287. if(myrank==0)
  288.      for (i=1;i<=textlen;i++) {
  289.      if (D[i]>=0 && D[i]<=k)
  290.           MatchCount++;
  291. }
  292. else 
  293.      for (i=patternlen+k;i<=textlen+patternlen+k-1;i++) {
  294.      if (D[i]>=0 && D[i]<=k)
  295.           MatchCount++;
  296. }
  297.   MPI_Barrier(MPI_COMM_WORLD);
  298. printf("Total %d matched on node %d n",MatchCount,myrank);
  299.   free(T);
  300.   free(P);
  301.   free(D);
  302.   free(nextval);
  303.   MPI_Finalize();
  304.  
  305.   return;
  306. }