分布式存储的并行串匹配算法的设计与分析

作     者：陈国良 林洁 顾乃杰 CHEN Guo-liang;LIN Jie;GU Nai-jie

作者机构：中国科学技术大学计算机科学技术系合肥230027 

基　　金：国家教育部博士点基金!(No.970 382 5 ) 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2000年第11卷第6期

页      码：771-778页

摘      要：并行串匹配算法的研究大都集中在 PRAM(parallel random access machine)模型上 ,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多 .该文采用将最优串行算法并行化的技术 ,利用模式串的周期性质 ,巧妙地将改进的 KMP(Knuth- Morris- Pratt)算法并行化 ,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法 ,其计算复杂度为 O(n/ p+m) ,通信复杂度为 O(ulogp) ,其中 n为文本串长 ,m为模式串长 ,u为模式串最小周期长 ,p为处理器数 .

主 题 词：串匹配 KMP(Knuth-Morris-Pratt) 分布式算法 可扩放性 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13328/j.cnki.jos.2000.06.009

馆 藏 号：203141554...