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.

A number of methods have been proposed for suffix sorting on internal memory of RAM and external memory of hard disks. The current best results for suffix sorting on internal or external memory are achieved by several algorithms using the induced sorting (IS) method in various ways. While these algorithms are efficient, the internal ones are much different from those external in terms of the algorithm designs. A scalable IS method that can be applied for suffix sorting on both internal and external memory is highly desired. This article proposes a blockwise IS method to facilitate pipelined access on internal memory and sequential I/Os on external memory. The detailed algorithm of using this method for a 4-stage pipeline with multiple threads is described, where multiple threads are applied to parallelize not only the pipelined stages of consecutive blocks but also the tasks within each stage wherever possible. This algorithm is evaluated by our experiments on a set of realistic and artificial datasets to achieve better overall time and space performance than the existing best results from pSACAK, pDSS and pKS. Beside sorting suffixes on internal memory in linear time, the proposed method can be ported to external memory for sorting massive suffixes in linear I/O complexity.

Sorting all suffixes of an input string$X$will produce the suffix array that is a fundamental data structure for full-text search on$X$. To utilize the parallel computing power of a multicore machine with shared memory, this article designs a fast linear-time and in-place parallel algorithm called pSACAK, for sorting the suffixes of an input string with a constant alphabet. This algorithm is a parallel variant of the sequential suffix sorting algorithm SACAK which improved the linear-time SAIS to be in-place for constant alphabets, and hence requires only a workspace of$\mathcal {O}(K)$for alphabet size$K$. While our recent work has successfully designed the parallel variant of SAIS on a multicore machine, it remains a challenge to parallelize SACAK due to the strong data dependencies caused by the in-place constraint. A number of new techniques are proposed here to overcome the difficulties for designing pSACAK from the sequential SACAK. An experimental study is conducted to evaluate the performance of pSACAK versus other existing parallel suffix sorting algorithms. Our experimental results show that pSACAK is the most time and space efficient among all in comparison. To the best of our knowledge, pSACAK is the only linear-time and in-place parallel suffix sorting algorithm for constant alphabets reported so far.