5
$\begingroup$

This question refers to steps Q2, Q4 and Q6 of Algorithm Q, described in the paper "A Block-sorting Lossless Data Compression Algorithm", by M. Burrows and D.J. Wheeler, SRC Research Report, 1994.

My question is: how can in step Q6, the sorting work, if we only compare the values in the array W, which are just the first few characters of each suffix? Is this because the suffixes are already presorted by their two first characters at this point? (That does not seem to matter at all in this case.) Or am I misunderstanding the step, and we should somehow use the whole suffix? In this case, why bother generating W?

To make the question complete and self-contained, I'll report the algorithm from the paper, along with an example input to better illustrate my point.

Let S be the input, and k the word size on the machine, N the number of characters of the input. For the example, I'll use S=aaaaabxxxxaaaaacxxxx (N=20 and k=4. Let's denote EOF, by $.

Q1. Let S' = S + k * EOF.

With the above data S'=aaaaabxxxxaaaaacxxxx$$$$

Q2.

Initialize an array W of N words W[0, ... N-1], such that W[i] contains the characters S'[i, ..., i+k-1], arranged so that integer comparisons on the words agree with lexicographic comparisons on the k-character strings.

In our example,

W =
    aaaa
    aaaa
    aaab
    aabx
    abxx
    bxxx
    xxxx
    xxxa
    xxaa
    xaaa
    aaaa
    aaaa
    aaac
    aacx
    acxx
    cxxx
    xxxx
    xxx$
    xx$$
    x$$$

Q3. Initialize array V of N integers, such that V[i] = i.

In our example:

V = [0, 1, 2, ..., 19]

Q4.

Sort the elements of V, using the first two characters of each suffix as the sort key. This can be done efficiently using radix sort.

With the above data, V after sorting will be: V = [0, 1, 2, 3, 10, 11, 12, 13, 4, 14, 5, 15, 9, 19, 6, 7, 8, 16, 17, 18], which corresponds to the following sorting of the suffixes:

aaaaabxxxxaaaaacxxxx$$$$
aaaabxxxxaaaaacxxxx$$$$
aaabxxxxaaaaacxxxx$$$$
aabxxxxaaaaacxxxx$$$$
aaaaacxxxx$$$$
aaaacxxxx$$$$
aaacxxxx$$$$
aacxxxx$$$$
abxxxxaaaaacxxxx$$$$
acxxxx$$$$
bxxxxaaaaacxxxx$$$$
cxxxx$$$$
xaaaaacxxxx$$$$
x$$$$
xxxxaaaaacxxxx$$$$
xxxaaaaacxxxx$$$$
xxaaaaacxxxx$$$$
xxxx$$$$
xxx$$$$
xx$$$$

Q5.

For each character ch in the alphabet, perform steps Q6 and Q7.

Q6.

For each character ch' in the alphabet: Apply quicksort to the elements of V starting with ch followed by ch'. In the implementation of quicksort, compare the elements of V by comparing the suffixes they represent by indexing intothe array W. At each recursion step, keep track of the number of characters that have compared equal in the group, so that they need not be compared again. All the suffixes starting with ch have now been sorted into their final positions in V.

At this point, I do not understand, how the sort can work correctly, if we use only the suffix portions in W, and not the whole suffixes? Consider e.g. the example above, there are 4 suffix-portions in W, whose value is aaaa, but of course the corresponding whole suffixes are different:

aaaa                    aaaaabxxxxaaaaacxxxx$$$$
aaaa                    aaaabxxxxaaaaacxxxx$$$$
aaab                    aaabxxxxaaaaacxxxx$$$$
aabx                    aabxxxxaaaaacxxxx$$$$
[...]
aaaa                    aaaaacxxxx$$$$
aaaa                    aaaacxxxx$$$$
[...]

E.g., how will aaaaacxxxx$$$$ and aaaabxxxxaaaaacxxxx$$$$ sorted correctly among each other, if we only know that both start with aaaa?

Or do we use the whole suffix? (Since they say something about recursion, it might be the case that we somehow just go on, if the end of W is reached, and the two strings are still equal.) In this case, however, what is the benefit of W?

Q7. Omitted, because I don't think it is relevant for this question (I don't see how it could "fix" the problem, after Q6).

Remark: I tried searching online, for other resources which explain this part. I found an implementation, where the whole suffix is used at setp Q6, not just the W part of it. In file bwxform.c, function ComparePresorted is implemented as follows:

static unsigned char block[BLOCK_SIZE];     /* block being (un)transformed */
static size_t blockSize;                    /* actual size of block */

/* ... SNIP ***  */

/***************************************************************************
*   Function   : ComparePresorted
*   Description: This comparison function is designed for use with qsort
*                and "block", a global array of "blockSize" unsigned chars.
*                It compares two strings in "block" starting at indices
*                s1 and s2 and ending at indices s1 - 1 and s2 - 1.
*                The strings are assumed to be presorted so that first two
*                characters are known to be matching.
*   Parameters : s1 - The starting index of a string in block
*                s2 - The starting index of a string in block
*   Effects    : NONE
*   Returned   : > 0 if string s1 > string s2
*                0 if string s1 == string s2
*                < 0 if string s1 < string s2
***************************************************************************/
static int ComparePresorted(const void *s1, const void *s2)
{
    unsigned int offset1, offset2;
    unsigned int i;



    /***********************************************************************
    * Compare 1 character at a time until there's difference or the end of
    * the block is reached.  Since we're only sorting strings that already
    * match at the first two characters, start with the third character.
    ***********************************************************************/
    offset1 = *((unsigned int *)s1) + 2;
    offset2 = *((unsigned int *)s2) + 2;

    for(i = 2; i < blockSize; i++)       /*  <--- (1)  */
    {
        unsigned char c1, c2;

        /* ensure that offsets are properly bounded */
        if (offset1 >= blockSize)
        {
            offset1 -= blockSize;
        }

        if (offset2 >= blockSize)
        {
            offset2 -= blockSize;
        }

        c1 = block[offset1];
        c2 = block[offset2];

        if (c1 > c2)
        {
            return 1;
        }
        else if (c2 > c1)
        {
            return -1;
        }

        /* strings match to here, try next character */
        offset1++;
        offset2++;
    }

    /* strings are identical */
    return 0;
}

At line (1) (annotation by me), it can be seen, that the whole block will be read (which is like reading the whole suffix in our case).

P.S.: For the records, I already asked another question on BWT, now I'm one step further :)

$\endgroup$
  • $\begingroup$ Once more into the breach -- the general idea of "recursive" suffix sorting is to put some suffixes in correct order with string comparisons, and then sort the other suffixes that point to them (via $T^{-1}$) by just comparing their pointers (O(1) comparison instead of up to O(n) string comp.). I think Q7 is the latter. There is a whole genre of papers about doing this in various ways. $\endgroup$ – KWillets Nov 6 '16 at 20:20
  • $\begingroup$ Also, W is confusing as hell here -- in Q6 it's just a wide character comparison, but then it's packed with recursive indices in Q7. In Q6, the initial sort is I believe a multikey quicksort, with W being read instead of S -- W is a pre-SIMD multcharacter comparator; it's Terrible. $\endgroup$ – KWillets Nov 6 '16 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.