Sorting strings and constructing digital search trees in parallel
Sorting strings and constructing digital search trees in parallel
复制标题
并行排序字符串和构建数字搜索树
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
U. Vishkin
中科院分区：
文献类型：
--
作者：
J. JáJá;K. Ryu;U. Vishkin
我们描述了两个简单的最优工作并行算法，用于排序列表/spl Lscr/=（X/sub 1/，X/sub 2/，.，X/sub m/）的任意字母表/spl Sigma/上的m个字符串，其中/spl Sigmasub i= 1 sup mspl verbar/X/sub ispl verbar/=n。第一个算法是一个确定性算法，运行时间为O（（log/sup 2/ m）/（log log m）），第二个算法是一个随机算法，运行时间为O（log m）。这两个算法都使用O（m log（m）+n）操作。与已知的并行字符串排序算法相比，该算法提供了以下改进：算法所使用的操作总数是最优的，而所有以前的并行算法使用的操作数都不是最优的;我们没有对字母表做任何假设，而以前的算法假设字母表被限制为/spl lcub/1，2，. n/sup O（1/）/spl rcub/;与已知的假设任意CRCW PRAM的算法不同，该算法假设的计算模型是公共CRCW PRAM;并且所提出的算法使用O（mlog m+n）空间，而先前的并行算法使用O（n/sup 1+/spl epsiv）空间，其中/spl epsiv/是正常数。我们还提出了最优工作并行算法来构建一个数字搜索树为一组给定的字符串，并搜索一个字符串排序列表中的字符串。我们使用的并行排序算法来解决的问题，确定一个循环字符串的最小起始点相对于字典序。<<ETX>>
We describe two simple optimal-work parallel algorithms for sorting a list /spl Lscr/=(X/sub 1/,X/sub 2/,...,X/sub m/) of m strings over an arbitrary alphabet /spl Sigma/, where /spl Sigmasub i=1sup mspl verbar/X/sub ispl verbar/=n. The first algorithm is a deterministic algorithm that runs in O((log/sup 2/ m)/(log log m)) time and the second is a randomized algorithm that runs in O(log m) time. Both algorithms use O(m log(m)+n) operations. Compared to the best known parallel algorithms for sorting strings, the algorithms offer the following improvements: the total number of operations used by the algorithms is optimal while all previous parallel algorithms use a non-optimal number of operations; we make no assumption about the alphabet while the previous algorithms assume that the alphabet is restricted to /spl lcub/1,2,..., n/sup O(1/)/spl rcub/; the computation model assumed by the algorithms is the Common CRCW PRAM unlike the known algorithms that assume the Arbitrary CRCW PRAM; and the presented algorithms use O(m log m+n) space, while previous parallel algorithms use O(n/sup 1+/spl epsiv) space, where /spl epsiv/ is a positive constant. We also present optimal-work parallel algorithms to construct a digital search tree for a given set of strings and to search for a string in a sorted list of strings. We use the parallel sorting algorithms to solve the problem of determining a minimal starting point of a circular string with respect to lexicographic ordering.<<ETX>>