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.
C1. Take all the cyclic rotations of
S, and sort them lexicographically (result: matrix
I is the index of the first row of
M, which is equal to
L be the last column of
Output of compression: (
D2. Calculate vector
T, such that
kth instance of
T[j] = iwhere
kth instance of
In other words:
F[T[j]] = L[j]
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
From 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 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
________________ _________________ | | | | | _______________________ | 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?
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
L = 'r' is "to the left of"
Does this mean that
'r' cyclically precedes the first
'acaabr', i.e. if from the first
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
'a' instead of
'b', since there are more
'a''s. So, for
L='a', that means there is
a suffix starting with
'a', to which
T should point to. Indeed,
T=1, which is the second suffix
'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
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?