Parallel suffix sorting
Parallel suffix sorting
复制标题
并行后缀排序
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
S. Kurtz
中科院分区：
文献类型：
--
作者：
N. Futamura;S. Aluru;S. Kurtz
提出了一种对字符串后缀按字典顺序排序的并行算法。后缀排序在字符串处理、数据压缩和计算生物学中都有应用。存储在数组中的字符串后缀的有序列表称为后缀数组，是字符串处理和计算生物学中的重要数据结构。我们的重点是推导出一种适用于典型输入的实际实现，而不是针对最坏情况的人工输入实现最佳渐近运行时间。我们在IBM SP-2上使用几种生物体的基因组实验评估了我们的算法。我们的实验表明，该算法提供了良好的可扩展性能。
We present a parallel algorithm for lexicographically sorting the suffixes of a string. Suffix sorting has applications in string processing, data compression and computational biology. The ordered list of suffixes of a string stored in an array is known as Suffix Array, an important data structure in string processing and computational biology. Our focus is on deriving a practical implementation that works well for typical inputs rather than achieving the best possible asymptotic running-time for artificial, worst-case inputs. We experimentally evaluated our algorithm on an IBM SP-2 using genomes of several organisms. Our experiments show that the algorithm delivers good, scalable performance.