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, 1994The 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.CompressionInput text: SC1. 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)DecompressionInput: (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    2From the answer of @KWillets: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 wouldalso have an index to item 0 (thus making a cyclic list, or it wouldjust 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 willa 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 oneLet's consider 'a' instead of 'b', since there are more 'a''s. So, for i=3, L[3]='a', that means there isa suffix starting with 'a', to which T[3] should point to. Indeed, T[3]=1, which is the second suffixstarting 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 orderingamong 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?
Why does the last step of Decompression Transformation of the cited report work?
algorithms;data compression
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.  )