Well written. This is the preparation algorithm that makes [http://www.bzip.org/|bzip2] so strong. "Briefly, our algorithm transforms a string S of N characters by forming the N rotations (cyclic shifts) of S, sorting them lexicographically, and extracting the last character of each of the rotations. A string L is formed from these characters, where the <var>i</var>th character of L is the last character of the <var>i</var>th sorted rotation. In addition to L, the algorithm computes the index I of the original string S in the sorted list of rotations. Surprisingly, there is an efficient algorithm to compute the original string S given only L and I."