分布存储环境下的基于后缀数组的串匹配算法
要提高基于后缀数组的串匹配算法的性能，关键在于如何快速地构造后缀数组.以往的分布式算法在构造后缀数组时都是先对所有的后缀进行整体上的划分，然后再将划分好的后缀分配到处理器中以达到负载平衡，最后由处理器独立地排序分配到自己的后缀.这样做的优点是可以避免处理段间匹配，但是在对后缀的整体划分和分配过程中存在大量通信.文章提出的USAA算法通过采取均匀的后缀分配方式，使各个处理器可以独立地构造后缀教组，并提出通过播送最长后缀长度(Maxsuffixlen)来降低处理段间匹配时的通信复杂度。通过实验得出，在(N/P)>>M的情况下，USAA算法可以在保持计算复杂度的同时大大降低在构造后缀数组过程中的通信消耗.其中N，M为文本串和模式串的长度，P为处理器数.
后缀数组 分布式存储 串匹配算法
涂锟 顾乃杰 董万利
中国科学技术大学 计算机科学与技术系,合肥 230027;安徽省计算与通讯软件重点实验室,合肥 230027
国内会议
合肥
中文
311-316
2005-12-10（万方平台首次上网日期，不代表论文的发表时间）