基于后缀数组的分布式串匹配算法-中国学术期刊网络出版总库

中国学术期刊网络出版总库

关闭

基于后缀数组的分布式串匹配算法

推荐 CAJ下载

PDF下载

【英文篇名】	Distributed string match algorithm based on suffix arrays
【下载频次】	★★★
【作者】	涂锟; 顾乃杰;
【英文作者】	Tu Kun Gu Naijie (Department of Computer Science and Technology; University of Science and Technology of China Hefei; Anhui 230027; China);
【作者单位】	中国科学技术大学计算机科学与技术系; 中国科学技术大学计算机科学与技术系合肥;
【文献出处】	仪器仪表学报 , Chinese Journal of Scientific Instrument, 编辑部邮箱 2006年 S3期期刊荣誉：中文核心期刊要目总览 ASPT来源刊 CJFD收录刊
【中文关键词】	后缀数组; 分布式存储; 串匹配;
【英文关键词】	suffix array distributed algorithms string match;
【摘要】	文章提出的Uniformed Suffix Arrays Assign算法通过采取均匀的后缀分配方式,使各个处理器可以独立地构造后缀数组,并提出通过播送最长后缀长度(Maxsuffixlen)来降低处理段间匹配时的通信复杂度。算法在构造后缀数组时的平均复杂度为O((N／P)(loglog(N／P))),通信复杂度为O(1)。通过实验分析得出,在(N／P)M的情况下,USAA算法可以在保持计算复杂度的同时大大降低在构造后缀数组过程中的通信消耗。其中N,M分别为文本串和模式串的长度,P为处理器数。
【英文摘要】	In this paper we present the Uniformed Suffix array Assign Algorithm (USAA), in which the suffixes are assigned uniformly so that each processor can construct its own suffix array independently. Besides, by propagating the max suffix length (Maxsuffixlen) USAA can reduce the communication complexity for string matching effectively. The complexity for constructing suffix arrays is O ((N/P) (loglog ( N/P))), with the communication complexity being O(1). To demonstrate the effectiveness of our algorithm, we al...
【基金】	国家自然科学基金重点项目(60533020)
【更新日期】	2007-07-26
【分类号】	TP301.6
【正文快照】	1引言键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许

xxx

【相似文献】

中国期刊全文数据库

中国优秀硕士学位论文全文数据库

中国博士学位论文全文数据库

中国重要会议论文全文数据库

中国重要报纸全文数据库

中国学术期刊网络出版总库

点击下列相关研究机构和相关文献作者，可以直接查到这些机构和作者被《中国知识资源总库》收录的其它文献，使您全面了解该机构和该作者的研究动态和历史。

【文献分类导航】从导航的最底层可以看到与本文研究领域相同的文献，从上层导航可以浏览更多相关领域的文献。

工业技术
　

自动化技术、计算机技术
　　

计算技术、计算机技术
　　　

一般性问题
　　　　

理论、方法
　　　　　

算法理论


	CNKI系列数据库编辑出版及版权所有：中国学术期刊(光盘版)电子杂志社中国知网技术服务及网站系统软件版权所有：清华同方知网(北京)技术有限公司其它数据库版权所有：各数据库编辑出版单位（见各库版权信息）京ICP证040431号互联网出版许可证新出网证（京）字008号

相似文献

文献分类导航