并行算法的设计与分析.ppt

并行算法的设计与分析;第9章 串匹配并行算法;串匹配技术的应用;9.1 分布式存储系统的精确串匹配并行算法陈国良，林洁，顾乃杰.软件学报,2000, 11 (6) : 771-778; 9.1.2 改进的KMP 算法、计算next 函数和newnext 函数的算法;9.1.3 分布式并行串匹配算法的思想;　字符串的周期性分析;9.1.3 KMP串匹配的分布式并行算法及其复杂度分析 ;9.1.4 算法实验性能;9.2 可重构光计算模型的多模式串并行匹配算法钟诚，中国科技大学博士学位论文，2003.5;9.2.2 可重构光网孔模型ORM (Optical Reconfigurable Mesh);RMESH结构;9.2.2 可重构光网孔模型ORM (Optical Reconfigurable Mesh); 3D-ORM模型的多模式串并行匹配算法;9.2.3 ORM模型上多模式串并行匹配算法时间复杂度;9.3 CREW-PRAM上允许k- 差别的近似串匹配并行算法钟诚，陈国良.软件学报,2004, 15(2):159-169 ;9.3 CREW-PRAM上允许k- 差别的近似串匹配并行算法 ;例：Pat=bataa，T=cabataabadaa和编辑距离阈值k=1时，通过计算编辑距离矩阵D的元素值来完成近似串匹配的过程。 ;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;Algorithm 1 Parallel Approximate String Matching Algorithm on CREW PRAM Based on Parallel Computing Edit-Distance Matrix in Wave-Front Way输入：模式串Pat[1‥m]，正文T[1‥n]，编辑距离阈值k；输出：编辑距离≤k的模式在正文中的近似匹配终止位置pos ，1≤pos≤n;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验（并行Multipascal编程实现）;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验;波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;Algorithm 2 Parallel Approximate String Matching with k-Differences on CREW PRAM Based on Parallel Computing Edit-Distance Matrix Simultaneously along Diagonal and Horizontal Directions 输入：模式串Pat[1‥m]，正文T[1‥n]，编辑距离阈值k，处理器数α(m+1)  输出：编辑距离≤k的模式在正文中的近似匹配终止位置pos ，1≤pos≤n ;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;9.3 CREW-PRAM模型上允许k- 差别的近似串匹配并行算法;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法钟诚，陈国良.软件学报,2004, 15(2):159-169 ;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.4.3 n个处理器的LARPBS系统上的允许k-误配的近似串匹配并行算法 ; 9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法; 9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.4 LARPBS模型上允许k- 误配的近似串匹配并行算法;9.5 异构机群系统上近似串匹配并行算法钟诚、范大娟，2006全国高性能计算学术年会优秀论文，《计算机研究与发展》;9.5.2 基于单轮分配方式的单模式单正文串近似匹配并行算法;最优正文