Why does the last step of Decompression Transformation of the cited report work?

The report referred in the title is the following: A Block-sorting Lossless Data Compression Algorithm, by M. Burrows and D.J. Wheeler, SRC Research Report, 1994

The step I do not understand is step D3, on page 4:

for each i = 0, ... , N - 1: S[N - 1 - i] = L[T^i[I]]

Question is: why does this work, i.e. why does this give us the desired result?

(To be clear, I understand, what T means, and how T^i is constructed. I even coded down the formula above in Python, and it did give me the desired result -- I know, because I coded the other steps as well. I just don't see why it works?)

The algorithm described in the report consists of a "Compression" and a "Decompression" part, my question being about the last step of the "Decompression".

In order to give more context, as requested in the comment, I'll try summarise here the two mentioned parts.

Compression

Input text: S

C1. Take all the cyclic rotations of S, and sort them lexicographically (result: matrix M). Return M and I, where I is the index of the first row of M, which is equal to S.

C2. Let L be the last column of M.

Output of compression: (L, I)

Decompression

Input: (L, I)

D1. Sort L. Result: F.

D2. Calculate vector T, such that

If L[j] is the kth instance of ch in L, then T[j] = i where F[i] is the kth instance of ch in F.

In other words: F[T[j]] = L[j]

D3. Calculate S:

for each i = 0, ... , N - 1: S[N - 1 - i] = L[T^i[I]] where T0[x] = x, and T(i + 1)[x] = T[Ti[x]]

EDIT: Example for further clarification, based on the answer of @KWillets.

Let's take the example abraca used in the paper as well.

As also shown in the paper, the suffixes are the following:

  F|       |L         T        T0   T1   T2   T3   T4   T5
a|a b r a|c         4         0    4    2    5    3    1
a|b r a c|a<--I=1   0         1    0    4    2    5    3<--I=1
a|c a a b|r         5         2    5    3    1    0    4
b|r a c a|a         1         3    1    0    4    2    5
c|a a b r|a         2         4    2    5    3    1    0
r|a c a a|b         3         5    3    1    0    4    2


Think of the source string S as a (array-based) linked list, with one character per node, so that we can output S from left-to-right by traversing pointers.

I (suppose), that I understand this part. In the concrete example this would mean the following:

  position   0      1       2       3       4       5
label      A -->  B  -->  R  -->  A  -->  C  -->  A
index of   1      2       3       4       5       ? (0? "EOF"?)
next node


What I'm not sure about, is if the last position (5) in this case would also have an index to item 0 (thus making a "cyclic" list, or it would just be the end of the list).

But let's also arrange it so that the nodes are suffix sorted, ie each node is assigned a position i such the suffix that begins at that node is greater than the one at i-1, and so on.

The links in this array are T [...]

As far as I understand, this would mean the following (i.e., making the links equal to T):

                       ________________    _________________
|               |  |                 |
|        _______________________     |
V       |       |  |            V    |
position   0      1       2       3  |    4       5    |
label      A <--- A    -> A       B<-     C       R----
index of   4      0    |  5       1       2       3
next node     |___________|_________________^  \
|____________________|


(and traversing them is D3 above, and the label for each node is in F above)

Makes sense, if I traverse this list, in the sequence of T (i.e. 0->4->2->5->3->1), then the result will be ACARBA, i.e. the reverse of the original input string.

Main question, that I still do not understand: why does T have this property?. I.e. why will a list defined as described in D2 happen to be the correct indexes for generating the reverse of the original string?

Specific questions:

L[i] is the character just to the left of suffix i.

What does it mean "the character to the left of suffix i"?

Considering the above example, would this mean that e.g. for i=2 L[2] = 'r' is "to the left of" acaabr? Does this mean that 'r' cyclically precedes the first 'a' in 'acaabr', i.e. if from the first 'a' we went "one step to the left", then we would get the 'r' at the end? Also, how does this help us?

[...] for instance if L[i]='b', that means there is some suffix starting with 'b' that T[i] should point to, but we don't know which one

Let's consider 'a' instead of 'b', since there are more 'a''s. So, for i=3, L[3]='a', that means there is a suffix starting with 'a', to which T[3] should point to. Indeed, T[3]=1, which is the second suffix starting with 'a', so it corresponds to the description of the algorithm.

What I don't understand: how does L[i] come into the picture? Wasn't T supposed to be the ordering among the F's? (I guess this must have something to do with the above mentioned "the character to the left" property, but I do not see the connection, yet.)

Also, how do we know for sure that there must be such a suffix?

• @D.W.: I tried to be more explicit. Regarding your point, see the added main question. – Attilio Nov 3 '16 at 19:15
• L is the last column above as you correctly show, but it's also the character just to the left of whatever suffix starts in the first column. So for "braca" at index 3, L[3]='a'. – KWillets Nov 3 '16 at 20:09
• "how does L[i] come into the picture?" -- I don't understand this question. L is mainly used to build T and then can be discarded except for character counts. (I think you're getting most of it though.) – KWillets Nov 3 '16 at 20:49
• This has a good illustration: web.stanford.edu/class/cs262/presentations/lecture4.pdf . The "Reconstructing BANANA" slide. – KWillets Nov 3 '16 at 22:47
• Thank you very much!!! After reading this resource, I finally understood why it works! So the 'physical meaning' of following T (or LF as called in the slides), is just rotating the whole block (of whom we maybe don't know all the letters yet, when we are reconstructing), one step to the right. – Attilio Nov 5 '16 at 11:40

First, a bit of terminology:

The BWT represents a list of suffixes in lexicographical order (I'll use the term suffix instead of block, since the string is usually terminated with a metacharacter that makes suffix and block sorting equivalent). Each index i in the L and F arrays represents a unique suffix, and it can be illustrative to make a table with both L and F side-by-side.

L[i] is the character just to the left of suffix i, or the last column in a cyclic shift of the string; it basically tells us for any given suffix S[j..n] what S[j-1] is.

T allows a scan of the text without certain overheads which I'll describe. The implementations I've seen use $T^{-1}$, which allows a forward scan of the text, but in D3 it's doing a backward scan.

Structure:

Think of the source string S as a (array-based) linked list, with one character per node, so that we can output S from right-to-left (using T) or left-to-right (using $T^{-1}$) by traversing pointers. But let's also arrange it so that the nodes are suffix sorted, ie each node is assigned a position i such the suffix that begins at that node is greater than the one at i-1, and so on.

The links in this array are $T$ (and traversing them is D3 above, and the label for each node is in F above). But it's a bit bulky, and there are a number of artistic ways to compress it.

The BWT is probably the most difficult way. It's a representation of the links of T, but very indirectly, since for instance if L[i]='b', that means there is some suffix starting with 'b' that T[i] should point to, but we don't know which one -- there's a run of 'b's in F that could be the right index.

To disambiguate 'b' we have to use a property of $T^{-1}$: for a range of suffixes that begin with the same character, their $T^{-1}$ pointers are in ascending order. That is, if 'bat..' and 'bug...' are suffixes, the $T^{-1}$ pointer from 'b' to 'at...' comes before the one from 'b' to 'ug...'. In other words, their order is the same as the order of their suffixes.

That means that for any given 'b' at index i in L, we can figure out which entry in the 'b' range T[i] points to by counting only the b's that precede i in L, ie the rank of the 'b' at i among all the b's in L. That's D2. Basically T[i] = the rank of L[i] amongst other incidences of the same character in L + the start of the range that begins with L[i].

Calculating ranks one i at a time is slow (although there are other data structures that make it fast), so the translation to T is done all at once, by counting and summing in a process similar to counting sort (D1 and D2). But regardless of how, the output T is an array-based linked-list structure that can be decoded much more quickly than the ambiguous back-links in L.

(Also, while traversing T to output S, we can omit the character labels at each node if we use L and output the character just preceding, and adjust everything by 1. That's the L[...] in D3. )

• I just realized my F is called T above. I'm making a quick edit -- will have to check later for consistency. – KWillets Nov 1 '16 at 2:46
• Thank you very much for the detailed answer! I need some time to properly process it. – Attilio Nov 1 '16 at 7:14
• Fixed one error: described T inverse instead of T. Hopefully you can see that T is calculable from L; I didn't want to bury that point in detail. – KWillets Nov 1 '16 at 15:57
• I'm very sorry, as I described the inverse of T as T. Implementations use the inverse usually, and I should have read your description more closely. He's describing a right-to-left scan of the text, and I focused on left-to-right, so that was terribly confusing. – KWillets Nov 1 '16 at 16:39
• Thank you very much for the updated explanation. I'm one step nearer to understand, but I'm not there yet. I have the feeling that your answer correctly describes everything, just I'm struggling to put the pieces together. I updated the main question with a concrete example, and some sub-questions about your points that I do not fully understand. I would be glad if you could give me further clarifications based on those questions. – Attilio Nov 3 '16 at 19:16