Suffix sort plays a critical role in various computational algorithms including genomics as well as in frequently used day to day software applications. The sorting algorithm becomes tricky when we have lot of repeated characters in the string for a given radix. Various innovative implementations are available in this area e.g., Manber Myers. We present here an analysis that uses a concept around generalized polynomial factorization to sort these suffixes. The initial generation of these substring specific polynomial can be efficiently done using parallel threads and shared memory. The set of distinct factors and their order are known beforehand, and this helps us to sort the polynomials (equivalent of strings) accordingly.
翻译:后缀类在包括基因组学在内的各种计算算法以及日常常用的软件应用中发挥着关键作用。 当我们给定的射线线字符串中有很多重复字符时, 排序算法就变得棘手了。 该领域有各种创新的实施方法, 比如 Manber Myers 。 我们在这里提出一个分析, 使用一个概念围绕普遍多式多米因子化来排序这些后缀。 这些子字符串特定多面形的初始生成可以使用平行线条和共享的内存来有效完成。 一套不同的因素及其顺序是事先已知的, 这有助于我们相应排序多面形( 等量字符) 。