Sorting any m target suffixes of an input string X of n characters from a constant alphabet is a key task for building the sparse suffix array SSA(X) for index construction. A number of probabilistic ...and deterministic algorithms have been proposed for sorting sparse suffixes with varying time and space complexities, but only some experimental results are available for performance evaluation of these algorithms. We design a divide-and-conquer algorithm called sSAIS for computing SSA(X) in O(nlogmlog(n/m)) time and O(m) workspace by using the induced sorting principle, and conduct an experimental performance study on real and artificial datasets. This work reveals that to design an efficient deterministic algorithm for sorting sparse suffixes is a tough challenge and the density of target suffixes might be considered as a critical design parameter.
•Sparse suffix arrays are preferred to build succinct indexes for only patterns starting at interesting positions in data.•We design a divide-and-conquer algorithm called sSAIS for computing SSA(X) in O(nlogmlognm) time and O(m) workspace by using the induced sorting principle originally proposed for computing SA(X) recursively in linear time.•While the existing studies on sparse suffix sorting concentrate on designing algorithms theoretically, our proposed experimental results of sSAIS give some more knowledge about the achievable time and space performance of sparse suffix sorting.•As a conclusion learned from this work, to design an efficient deterministic algorithm for sorting sparse suffixes is a tough challenge, and the density of target suffixes might be considered as a critical design parameter.
Many efficient open-source suffix sorters using the induced sorting (IS) method to build the fundamental data structure suffix array (SA) for compressing and indexing data have been proposed. To ...avoid potential faults caused by possible implementation bugs, checking the output SA from any IS sorter without engineering warranty for correctness is a de-facto process. The existing SA checkers commonly perform checking after an SA is built completely, with significant time and space complexities compared with that of builders. This article proposes an efficient solution for building and checking SA simultaneously by enhancing the original IS method with a checking scheme using hash computations to on-the-fly verify the results produced by the last induction phase of IS method. Given an input of constant alphabet, this checking scheme requires linear time and constant RAM space when running on external memory, and its time and space overheads are negligible compared with that for building SA. In our experiments on real-world data, the proposed methods take advantages over the counterparts of existing SA checkers by running faster with less space. This work can help provide a value-added bonus feature for open-source IS sorters to guarantee the correctness of a built SA, and such a feature should be desirable for applications using these sorters.
We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree ...algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.
Computing the Lempel-Ziv Factorization (LZ77) of a string is one of the most important problems in computer science. Nowadays, it has been widely used in many applications such as data compression, ...text indexing and pattern discovery, and already become the heart of many file compressors like gzip and 7zip. In this paper, we show a linear time algorithm called Xone for computing the LZ77, which has the same space requirement with the previous best space requirement for linear time LZ77 factorization called BGone. Xone greatly improves the efficiency of BGone. Experiments show that the two versions of Xone: XoneT and XoneSA are about 27% and 31% faster than BGoneT and BGoneSA, respectively.
Sorting the suffixes of an input string is a fundamental task in many applications such as data compression, genome alignment, and full-text search. The induced sorting (IS) method has been ...successfully applied to design a number of state-of-the-art suffix sorting algorithms. In particular, the SAIS algorithm designed by the IS method is not only linear in time but also fast in practice. However, the parallelization of SAIS remains a challenge due to that the IS process in the algorithm is inherently sequential and the performance bottleneck of the whole algorithm. This article presents our attempt for designing a parallel variant of SAIS on a multicore machine which is considered as a shared memory parallel model, called pSAIS. By a combined use of multithreading and pipelining, the inducing process is accelerated by fully utilizing the machine’s parallel computing power. An experimental study is conducted for performance evaluation of pSAIS with the other existing parallel suffix sorting algorithms, on a set of realistic inputs with varying sizes and alphabets. The experiment results show that our program for pSAIS has a high degree of parallelism and achieves the best average time and space performance among all the parallel algorithms in comparison. While pSAIS is designed for quickly building big suffix arrays in a multicore machine, our study may give some hints for extending the induced sorting method to GPU for constructing small suffix arrays even faster.
PDF
