The Burrows Wheeler transform has applications in data compression as well as full text indexing. Despite its important applications and various existing algorithmic approaches the construction of the transform for large data sets is still challenging. In this paper we present a new semi external memory algorithm capable of constructing the transform in time O(n log2 log n) on average if sucient internal memory is available to hold a fixed fraction of the input text. In the worst case the run-time is O(n log n log log n).
The Burrows-Wheeler transform (BWT) was introduced to facilitate the lossless
compression of data (cf. [
Definitions For a string s = s0s1s2 . . . sm 1 of length |s| = m we define s[i] = si for 0 i < m and for s = s0s1 . . . we define s[i] = si for 0 i. For a finite word u and a finite or infinite word v we write their concatenation as uv. For any finite words u, x and finite or infinite words w, v such that w = uxv we call u a prefix, v a sux and x a factor of w. The empty word consisting of no symbols is denoted by ✏. For a string s and indices 0 i j < |s| we denote the factor s[i]s[i + 1] . . . s[j] by s[i, j]. For any i, j such that i > j the term s[i, j] denotes the empty word. A finite word w has period p i↵ w[i] = w[i + p] for i = 0, . . . , |w| p 1 and an infinite word w has period p i↵ w[i] = w[i + p] for i = 0, 1, . . .. For a finite word u and k 2 N the k’th power uk of u is defined by u0 = ✏ and ui+1 = uiu for i 2 N. A word w is primitive if it is not a power of a word u such that |u| < |w|. A word u is a root of w if w = uk for some k 2 N. A word w is a square if there is a word u such that w = u2. Throughout this paper let ⌃ = {0, 1, . . . , 1} denote a finite alphabet for some > 0 and let t = t0t1 . . . tn 1 2 ⌃ n denote a finite string of length n > 0. We define the semi infinite string t˜ by t˜[i] = t[i b i/ncn] for i 0. We define the sux t˜i of t˜ as t˜i = t˜[i]t˜[i + 1] . . . and t˜i < t˜j for i, j 2 N, i 6= j i↵ either t˜i = t˜j and i < j or for the smallest ` 0 such that t˜[i + `] 6= t˜[j + `] we have t˜[i + `] < t˜[j + `]. The sux array A of t is defined as the permutation of the numbers 0, 1, . . . , n 1 such that t˜A[i] < t˜A[i+1] for i = 0, 1, . . . , n 2 and the Burrows-Wheeler transform (BWT) B = b0b1 . . . bn 1 of t is given by bi = t˜[A[i] + n 1] for i = 0, 1, . . . , n 1. 3
We give a short high level description of the algorithm by Ferragina et al. in [
The algorithm by Ferragina et al processes each single block relying on knowledge about the priorly fully processed following block, in case of the last block the terminator. For our algorithm we need to be able to sort a single block without knowing the complete sorted order of the next block. For this purpose we need to be able to handle repetitions, one of the major challenges along the way, eciently. For our block sorting only repetitions with a period not exceeding the maximum block size are relevant. Consider a block of b suxes t˜i+j for some i 2 N+, 0 j < b. We say it generates a repetition with period p, 1 p b i↵ t˜[b p, b 1] = t˜[b, b + p 1] and propagates a repetition with period p, 1 p b i↵ t˜i[0, b + 2p 1] has period p. If it propagates repetitions of any periods, then there is a unique minimal period dividing all other propagated periods. This unique minimal period can then be computed in time O(b) and space O(b log ) bits using minor modifications of standard string algorithms. As there is a unique minimal period propagated by a block if any and we are only interested in generated periods which are propagated by the next block we can compute the relevant generation properties of a block in the same time and space bounds. Given a target block size b0 we partition the given text into a set of blocks of size either b = d d(n/nb0)e e b0 or b 1 where the first n mod b blocks have length b and the rest length b 1. For the propagation of repetitions we extend the blocks of length b 1 to size b by adding the (circularly) next character to the right. Using this information about short period repetitions in the input string, we are able to handle the sorting of a single block of suxes extending beyond the end of the block eciently by reducing long repetitions. Lemma 4.1 A block of b circular suxes of t˜ can be sorted in lexicographical order using time O(b) and space O(b log b) bits using precomputed repetition propagation data.
For forward searching using the sux array it is useful to in addition have the longest common prefix (LCP) array. For two strings u, v let LCP(u, v) = argmaxlm=i0n{|u|,|v|} u[0, ` 1] = v[0, ` 1]. For a block t˜[i, i + b 1] for i, b 2 N, b > 0 let A denote the permutation of i, i + 1, . . . , i + b 1 such that t˜A[j] < t˜A[j+1] for j = 0, 1, . . . , b 2. Then the LCP array of the block is defined by LCP[0] = 0 and LCP[i] = LCP(t˜A[i 1], t˜A[i]) for i = 1, 2, . . . , b 1. Using a repetition reduction method similar to the sux sorting case we obtain the following result. Lemma 4.2 The LCP array for a block of b circular suxes on t˜ can be computed in time O(b) and space O(b log b) bits using precomputed repetition propagation data. 5
Merging Pairs of Adjacent Blocks
In our modified algorithm we replace the completely skewed binary merge tree used
in [
5. The gap array G.
The first three are equivalent to those used in [
The gt array for the merged block can be composed by concatenating the gt array for the left block and an array storing the respective information for the right block computed while performing the backward search for filling the gap array. For this purpose we need to know the rank of the leftmost sux in the left block. This can either be computed using forward search on the sux arrays of the basic blocks or extracted from a sampled inverse sux array which can be computed along the way. The sampled inverse sux arrays of two blocks can just like the BWTs of the two blocks be merged using the gap array. This is also an operation based on stream accesses, so it can be done in external memory in time O(b). 6
BWT Computation by Balanced Tree Block Merging Using the building blocks described above we can now describe the complete algorithm for computing the BWT of t by merging basic blocks according to a balanced binary tree.
1. Choose a target block size b0 2 O( long n ) and deduce a block size b = d d bn0 e e n n n such that the number of blocks c satisfies c = d b e = d b0 e and n can be split into blocks of size b and b 1 only. Split t such that the blocks of size b appear before those of size b0. This step takes constant space and time. 2. Compute which blocks in t propagate repetitions of period at most b and for each block which is followed by a block propagating a repetition whether it is generating this repetition. This takes time O(n) in total and space O(b log ) = O( nlologgn ) ✓ O(n) bits. The result data can be stored in external memory. 3. Compute a balanced merge tree for the blocks. Start with a root representing all blocks. If a node containing a single block is considered produce a leaf and stop. Otherwise for an inner node representing k > 1 blocks produce a left k k subtree from the d 2 e leftmost blocks and a right subtree from b 2 c rightmost blocks in t. The tree has O(log n) nodes. Each node stores at most two (start and end) block indices taking O(log log n) bits and two node pointers also taking space O(log log n) bits. So the total tree takes space O(log n log log n) bits. It can be computed in time O(log n). 4. Sort the blocks and store the resulting BWT, gt and sampled inverse sux arrays in external memory. Using the sux and LCP arrays of the basic blocks also compute the start ranks necessary for the backward searches when merging the blocks together. This takes time O(n log n log log n) in the worst case and O(n) on average and space O(b log b) = O( long n log long n ) = O(n) bits of internal memory. 5. Process the merge tree. Mark all leafs as finished and all inner nodes as unfinished. While there are unfinished nodes choose any unfinished node with only finished children, merge the respective blocks and mark the node as finished. There are O(log n) leafs and the tree is balanced, so it has O(log log n) levels. Each single level can be processed in time O(n log log n). So the total run time for the tree merging phase is O(n log2 log n). The maximum internal memory space usage appears when performing the merge operation at the root of the tree. Here we need space blHk + o(bl log ) bits where bl denotes the sum of the length of the blocks in the left subtree which is O(n) and Hk denotes the k’th order entropy of the text comprising those text blocks.
Summing over all steps the run-time of the algorithm is O(n log n log log n) in the
worst case and O(n log2 log n) on average. In practice this means we can compute
the BWT of a text as long as we are able to hold the text (more precisely the text
for the left subtree of the merge tree) in internal memory. If we can hold a fixed
fraction of the text in main memory, then we can still compute the BWT of the
text in the same run-time by resorting to the original iterative merging scheme
from [
Conclusion
We have presented a new semi external algorithm for computing the
BurrowsWheeler transform. On average our new algorithm is faster then the algorithm of
Ferragina et al published in [