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.

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.

For full-text indexing of massive data, the suffix and LCP (longest common prefix) arrays have been recognized as fundamental data structures, and there are at least two needs in practice for checking their correctness, i.e., program debugging and verifying the arrays constructed by probabilistic algorithms. Two probabilistic methods are proposed to check the suffix and LCP arrays of constant or integer alphabets in external memory using a Karp-Rabin fingerprinting technique, where the checking is wrong only with a negligible error probability. The first method checks the lexicographical order and the LCP-value of two suffixes by computing and comparing the fingerprints of their LCPs. This method is general in terms of that it can verify any full or sparse suffix/LCP array of any order. The second method uses less space, it first employs the fingerprinting technique to verify a subset of the given suffix and LCP arrays, from which two new suffix and LCP arrays are induced and compared with the given arrays for verification, where the induced suffix and LCP arrays can be removed for constant alphabets to save space.

Computing the Lempel–Ziv factorization (LZ77) of a string is a key step in many applications. However, at the same time, it constitutes a bottleneck of the entire computation. The investigation of time and space efficient computation of the LZ77 has become an important topic. In this paper, we present a lightweight linear-time algorithm called LZone for computing the LZ77, which is designed by improvements on the existing linear-time space efficient LZ77 algorithm BGone for speed acceleration. For an input string T[1..n] over a constant alphabet size of O(1), LZone requires only n words of workspace in addition to the input string and the output factorization, ⌈logn⌉ bits per word. This is the same space requirement for the algorithm BGone. LZone has two versions, LZoneT and LZoneSA, corresponding to BGoneT and BGoneSA, respectively. Our experimental results show that for computing the LZ77 from an input string T, LZoneT and LZoneSA run at around 26% and 57%, respectively, faster than their counterparts in BGone. Moreover, for computing the LZ77 from the suffix array of T, the speed of LZoneSA is on average twice that of BGoneSA. Copyright © 2015 John Wiley & Sons, Ltd.

We present in this article an external memory algorithm, called disk SA-IS (DSA-IS), to exactly emulate the induced sorting algorithm SA-IS previously proposed for sorting suffixes in RAM. DSA-IS is a new disk-friendly method for sequentially retrieving the preceding character of a sorted suffix to induce the order of the preceding suffix. For a size n string of a constant or integer alphabet, given the RAM capacity Ω (( nW ) 0.5 ), where W is the size of each I/O buffer that is large enough to amortize the overhead of each access to disk, both the CPU time and peak disk use of DSA-IS are O ( n ). Our experimental study shows that on average, DSA-IS achieves the best time and space results of all of the existing external memory algorithms based on the induced sorting principle.

We present a new suffix array construction algorithm that aims to build, in external memory, the suffix array for an input string of length n measured in the magnitude of tens of Giga characters over a constant or integer alphabet. The core of this algorithm is adapted from the framework of the original internal memory SA-DS algorithm that samples fixed-size d-critical substrings. This new external-memory algorithm, called EM-SA-DS, uses novel cache data structures to construct a suffix array in a sequential scanning manner with good data spatial locality: data is read from or written to disk sequentially. On the assumed external-memory model with RAM capacity Ω (( nB ) 0.5 ), disk capacity O ( n ), and size of each I/O block B , all measured in log n -bit words, the I/O complexity of EM-SA-DS is O ( n / B ). This work provides a general cache-based solution that could be further exploited to develop external-memory solutions for other suffix-array-related problems, for example, computing the longest-common-prefix array, using a modern personal computer with a typical memory configuration of 4GB RAM and a single disk.

The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O ( N log k ) and a space complexity O ( N ), where N and k are the text size and the context order of the transform, respectively. In this article, we present a novel algorithm that can compute the inverse ST for any k -order contexts in an O ( N ) time and space complexity, a linear result independent of k . The main idea behind the design of this linear algorithm is a set of cycle properties of k -order contexts that we explore for this work. These newly discovered cycle properties allow us to quickly compute the Longest Common Prefix (LCP) between any pair of adjacent k -order contexts that may belong to two different cycles, which eventually leads to the proposed linear-time solution.

We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA algorithm and comparable to that of the KS algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.

We present a linear time and space suffix array (SA) construction algorithm called the SA-IS algorithm.The SA-IS algorithm is novel because of the LMS-substrings used for the problem reduction and the pure induced-sorting (specially coined for this algorithm)used to propagate the order of suffixes as well as that of LMS-substrings, which makes the algorithm almost purely relying on induced sorting at both its crucial steps.The pure induced-sorting renders the algorithm an elegant design and in turn a surprisingly compact implementation which consists of less than 100 lines of C code.The experimental results demonstrate that this newly proposed algorithm yields noticeably better time and space efficiencies than all the currently published linear time algorithms for SA construction.

We show that the edge-face total chromatic number of Halin graphs with maximum vertex degree $\Delta$ not less than 4 is equal to $\max\{5,\Delta\}$. For the cases of $\Delta=4$ and 5, we provide a proper 5-edge-face total coloring algorithm.