The space-efficient BWT construction algorithm is in bwt_gen.c. One of the first things you see there is the copyright line:
Copyright (C) 2004, Wong Chi Kwong.
With that name, you can find the relevant papers:
The third paper only mentions BWT briefly in the last section. It deals with compressed suffix arrays, which are space-efficient representations of the inverse function of LF-mapping. But if you have a representation of (the inverse of) the LF-mapping, you have a representation of the BWT. Hence the algorithm can be adapted for BWT construction.
When building BWT, you usually append a unique character
$ to the end of the text, either implicitly or explicitly. This way you can reduce sorting rotations to sorting suffixes. You sort the suffixes in lexicographic order, and then you output the preceding character for each suffix in that order to form the BWT.
Assume that you already have the BWT for string
X, and you want to transform it into the BWT of string
c is a single character. You can do that in three steps (this assumes 0-based array indexing):
- Find the position
i of the full suffix
X, and replace the
$ in the BWT with the inserted character
BWT[i] = c).
- Determine the number of suffixes
j that are lexicographically smaller than
j = LF(i, c) = C[c] + BWT.rank(i, c). Here
C[c] is the number of suffixes that start with a character smaller than
BWT.rank(i, c) is the number of occurrences of
c in the prefix
By iterating this, you can build the BWT for any string slowly but space-efficiently. The algorithm of Hon et al. is based on the same idea, but they make it faster by inserting multiple characters at the same time. Given the BWT of string
X and another string
Y, they produce the BWT of the concatenation
YX. The details are quite complicated, but you can find them in the third paper and in the source code.