String Algorithms in C by Thomas Mailund

Author:Thomas Mailund
Language: eng
Format: epub
ISBN: 9781484259207
Publisher: Apress

The skew algorithm

The Kärkkäinen-Sanders, DC3, or skew algorithm—it has many names—is a divide-and-conquer approach to building a suffix array. It splits the string into two parts, one containing one-third of the suffixes and one containing the rest. It constructs a shorter string from the two-thirds suffixes and recursively sort it and then use it to combine the two initial array of suffixes into the correct array.

You can find the full source code for the algorithm at https://github.com/mailund/stralg/blob/master/stralg/skew.c. Let us dig into the details. Given an initial string, split it into the suffixes that have index i with i % 3 = 0, those that have modulus one or two, i % 3 ≠ 0. Let us call these arrays sa3 and sa12. We put all the suffix indices into them such that those indices i % 3 ≠ 0 go into sa12 and the rest into sa3. We first construct sa12 and sort it lexicographically according to the suffixes it holds. We do this recursively using the method we are building now (as one does in divide-and-conquer algorithms). Once we have sa12, we can then construct a sorted sa3 from the result. All indices i % 3 = 1 are sorted in sa12, so if we insert i % 3 = 0 in the order that i + 1 appear in sa12, we have the indices in sa3 sorted with respect to the suffix following their index. If we then do a stable sort of the first letters of the suffixes in sa3, we will have binned these suffixes, so the first letters are in order, and within each bin, the suffixes are sorted with respect to the suffix following the first letter. This means that we have sorted the suffixes in sa3. We can sort sa3 in linear time if we use a radix sort. I go into details about this in a few pages.

Figure 4-2Overview of the skew algorithm

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.