基于后缀数组的分布式串匹配算法
文章提出的Uniformed Suffix Arrays Assign算法通过采取均匀的后缀分配方式,使各个处理器可以独立地构造后缀数组,并提出通过播送最长后缀长度(Maxsuffixlen)来降低处理段间匹配时的通信复杂度.算法在构造后缀数组时的平均复杂度为O((N/P)(loglog(N/P))),通信复杂度为O(1).通过实验分析得出,在(N/P)M的情况下,USAA算法可以在保持计算复杂度的同时大大降低在构造后缀数组过程中的通信消耗.其中N,M分别为文本串和模式串的长度,P为处理器数。
后缀数组 分布式存储 串匹配 后缀分配
涂锟 顾乃杰
中国科学技术大学计算机科学与技术系,合肥,230027
国内会议
贵阳、沈阳
中文
2477-2478
2006-08-01（万方平台首次上网日期，不代表论文的发表时间）