Complete this reconstruction. Before getting to the details of the compression, it may be interesting to understand why Equation (8.1) reconstructs S from L. The following arguments explain why this process works:
1. T is constructed such that F[T[i]] = L[i] for i = 0, . . . , n.
2. A look at the sorted matrix of Figure 8.1b shows that in each row i, symbol L[i] precedes symbol F[i] in the original string S (the word precedes has to be understood as precedes cyclically). Specifically, in row I (8 in our example), L[I] cyclically precedes F[I], but F[I] is the first symbol of S, so L[I] is the last symbol of S. The reconstruction starts with L[I] and reconstructs S from right to left.
3. L[i] precedes F[i] in S for i = 0, . . . , n − 1. Therefore L[T[i]] precedes F[T[i]], but F[T[i]] = L[i]. The conclusion is that L[T[i]] precedes L[i] in S.
4. The reconstruction therefore starts with L[I] = L[8] = s (the last symbol of S) and proceeds with L[T[I]] = L[T[8]] = L[7] = s (the next-to-last symbol of S). This is why Equation (8.1) correctly describes the reconstruction.