How Burrows-Wheeler Compression Works: Compression Explained

1. Introduction and Core Concepts

Burrows-Wheeler compression is not a compression algorithm by itself, but a reversible transformation that makes data far more compressible by standard compressors. Proposed by Michael Burrows and David Wheeler in 1994 at the DEC Systems Research Center, the Burrows-Wheeler Transform (BWT) rearranges the characters of a string into runs of similar characters without losing any information. When combined with subsequent stages like Move-to-Front (MTF), Run-Length Encoding (RLE), and Huffman or Arithmetic coding, it forms the backbone of the bzip2 compressor and many modern bioinformatics tools.

The core insight behind burrows-wheeler compression is that many compression algorithms perform poorly on data with long-range repetitions but excel on data with local clustering. English text, source code, and DNA sequences all contain contexts where the same character tends to follow similar substrings. For example, in English, the letter 'h' often follows 't', and 'u' often follows 'q'. The BWT permutes the input so that characters that appear in similar contexts are grouped together, creating long runs like "EEEEEE" or "TTTT" that are trivial to compress with simple encoders.

Unlike dictionary-based methods such as LZ77 and LZ78 that replace repeated substrings with pointers, the Burrows-Wheeler approach is context-sorting. It is block-based, operating on chunks of data (typically 100KB to 900KB in bzip2) rather than streaming byte-by-byte. This gives it excellent compression ratios, often 10-20% better than gzip on text, at the cost of higher memory usage and slower speed. Understanding burrows-wheeler compression is essential for anyone working on data compression, columnar databases, or compressed full-text indexes, because its principles extend far beyond file archiving.

Why the Transform Matters

The BWT is remarkable because it is perfectly reversible: from the transformed string and a single integer (the primary index), you can reconstruct the original input exactly. It does not discard information or introduce loss. This reversibility is achieved through a property called LF-mapping, which allows the original matrix of rotations to be reconstructed without storing it.

Another key concept is that the BWT itself does not reduce size. In fact, the output is exactly the same length as the input (plus a small index). The compression gain comes entirely from what happens after the transform. By creating a more compressible permutation, the BWT enables the later stages to achieve dramatic size reductions. This pipeline architecture — transform then encode — is a powerful design pattern that appears in many modern codecs.

2. How It Works

The Burrows-Wheeler Transform operates in three conceptual steps: rotation, sorting, and extraction. Given an input string S of length n, we first append a unique end-of-file (EOF) character that is lexicographically smaller than any other character in the alphabet. By convention, this is often '$' or '\x00'. This sentinel guarantees that all rotations are distinct and simplifies inversion.

Next, we generate all n cyclic rotations of the string. For the string "BANANA$" the rotations are "BANANA$", "ANANA$B", "NANA$BA", "ANA$BAN", "NA$BANA", "A$BANAN", and "$BANANA". We then sort these rotations lexicographically to form an n x n matrix. The first column (F) and the last column (L) of this sorted matrix are of particular interest. The last column L is the BWT output. For "BANANA$", the sorted matrix yields L = "ANNB$AA". Notice how the three 'A's, two 'N's, and other characters are now grouped together.

The magic lies in the relationship between the first and last columns. The LF-mapping property states that the k-th occurrence of a character c in column L corresponds to the k-th occurrence of the same character c in column F. This stable correspondence exists because sorting is stable with respect to the context that follows each character. Because F can be obtained simply by sorting L, we can navigate from L to F and back again, which is the basis for inversion without storing the entire matrix.

The Full Compression Pipeline

In practice, burrows-wheeler compression is never used alone. The classic bzip2 pipeline consists of four stages: 1) Burrows-Wheeler Transform, 2) Move-to-Front Transform, 3) Run-Length Encoding of zeros, and 4) Huffman Coding. After the BWT groups similar characters, the Move-to-Front stage converts those runs into a stream of small integers (mostly zeros), which RLE compresses efficiently, and Huffman coding assigns short bit-codes to the most frequent integers.

Move-to-Front is critical. It maintains a list of the alphabet sorted by recency. When a character is seen, its current index in the list is output, and it is moved to the front. A run like "AAAAA" becomes "0,0,0,0,0" after the first 'A' moves 'A' to position 0. A sequence like "ABABAB" with clustered contexts after BWT becomes a stream dominated by low numbers, which is ideal for entropy coding. This is why the BWT's clustering directly translates to compression.

Inversion reverses the pipeline in opposite order: Huffman decode, RLE decode, inverse MTF, and inverse BWT. The inverse BWT is often implemented using the LF-mapping iteratively. Starting from the row containing the original string (given by the primary index), we can repeatedly apply LF-mapping to reconstruct the original string backwards, one character at a time, in O(n) time.

3. Implementation

A naive implementation of the BWT is straightforward and ideal for learning, though it is not suitable for large blocks due to its O(n^2 log n) time and O(n^2) space. The following Python code generates all rotations explicitly, sorts them, and extracts the last column. It clearly demonstrates the definition of the transform and includes the primary index needed for inversion.

def bwt_transform_naive(s: str):
    """
    Naive Burrows-Wheeler Transform.
    Returns (bwt_string, primary_index).
    s must not contain '$' which is used as EOF.
    """
    if not s:
        return "", 0
    # Append sentinel smaller than all other chars
    s = s + '$'
    n = len(s)
    # Generate all cyclic rotations
    rotations = [s[i:] + s[:i] for i in range(n)]
    # Sort lexicographically
    rotations.sort()
    # Last column is the transform
    bwt = ''.join(row[-1] for row in rotations)
    # Find row that is the original string
    primary_index = rotations.index(s)
    return bwt, primary_index

# Example
bwt, idx = bwt_transform_naive("BANANA")
print(bwt, idx)  # Expected: ANNB$AA 4

Inverting the BWT naively can be done by reversing the construction. If we know only L (the BWT output), we can reconstruct the full matrix by repeatedly prepending L and sorting. After n iterations, the sorted matrix is fully restored and the original string is the row at the primary index. While intuitive, this is O(n^2 log n) and serves mainly as a conceptual proof of reversibility.

def inverse_bwt_naive(bwt: str, primary_index: int):
    """
    Naive inverse BWT by table reconstruction.
    bwt: last column L, primary_index: row of original string
    """
    n = len(bwt)
    # Start with empty table
    table = [''] * n
    for _ in range(n):
        # Prepend BWT as new first column and sort
        table = sorted([bwt[i] + table[i] for i in range(n)])
    # Original string is at primary_index, strip sentinel
    return table[primary_index].rstrip('$')

# Test round-trip
original = inverse_bwt_naive("ANNB$AA", 4)
print(original)  # BANANA

For real-world use, we avoid building the full matrix. An efficient method uses the suffix array of the string. The suffix array is the sorted order of all suffixes, which is equivalent to the sorted order of rotations when a sentinel is present. Once we have the suffix array SA, the BWT character for position i is simply the character preceding the suffix SA[i]. This reduces the problem to suffix array construction, which can be done in O(n log n) with Python's sort or O(n) with SA-IS.

def bwt_via_suffix_array(s: str):
    """
    Efficient BWT using suffix array. O(n log n) time, O(n) space.
    Uses sentinel \x00 which is smaller than any text character.
    """
    if not s:
        return "", 0
    s = s + '\x00'  # Sentinel
    n = len(s)
    # Suffix array: sorted indices by suffix s[i:]
    suffix_array = sorted(range(n), key=lambda i: s[i:])
    # BWT[i] = char before suffix SA[i]
    bwt_chars = []
    for i in suffix_array:
        if i > 0:
            bwt_chars.append(s[i - 1])
        else:
            bwt_chars.append(s[-1])
    bwt = ''.join(bwt_chars)
    primary_index = suffix_array.index(0)
    return bwt, primary_index

def inverse_bwt_lf(bwt: str, primary_index: int):
    """
    Linear-time inverse using LF-mapping.
    """
    n = len(bwt)
    # Count occurrences for LF-mapping
    # F is sorted L
    F = sorted(bwt)
    # For each char, compute first occurrence in F
    from collections import Counter, defaultdict
    # Build rank for L: rank[i] = occurrence number of bwt[i] in L[0:i]
    counts = Counter()
    rank = [0] * n
    for i, ch in enumerate(bwt):
        rank[i] = counts[ch]
        counts[ch] += 1
    # Build first occurrence map for F
    first = {}
    pos = 0
    for ch in sorted(counts.keys()):
        first[ch] = pos
        pos += counts[ch]
    # LF[i] = first[ L[i] ] + rank[i]
    LF = [0] * n
    for i, ch in enumerate(bwt):
        LF[i] = first[ch] + rank[i]
    # Reconstruct backwards
    result = []
    idx = primary_index
    for _ in range(n):
        result.append(bwt[idx])
        idx = LF[idx]
    # Result is reversed and includes sentinel
    reconstructed = ''.join(reversed(result)).rstrip('\x00')
    return reconstructed

The final stage of a complete compressor is the Move-to-Front and Run-Length Encoding pipeline. The code below shows how the BWT output is converted into a stream of small integers that Huffman coding can compress effectively. Notice how runs in the BWT output become runs of zeros after MTF.

def mtf_encode(seq: str):
    """
    Move-to-Front encode. Converts clustered BWT output to small integers.
    Alphabet is 0-255 extended ASCII for demo; for text use sorted unique chars.
    """
    # Initialize alphabet list
    alphabet = [chr(i) for i in range(256)]
    # For efficiency with small alphabets, use unique chars of seq
    # alphabet = sorted(set(seq))  # alternative for text-only
    encoded = []
    for ch in seq:
        # Find index of ch
        idx = alphabet.index(ch)  # O(sigma) - use dict for O(1) in production
        encoded.append(idx)
        # Move to front
        if idx > 0:
            alphabet.pop(idx)
            alphabet.insert(0, ch)
    return encoded

def mtf_decode(encoded, alphabet_size=256):
    alphabet = [chr(i) for i in range(256)]
    decoded_chars = []
    for idx in encoded:
        if idx < 0 or idx >= len(alphabet):
            raise ValueError("Invalid MTF index")
        ch = alphabet[idx]
        decoded_chars.append(ch)
        if idx > 0:
            alphabet.pop(idx)
            alphabet.insert(0, ch)
    return ''.join(decoded_chars)

def rle_zero_encode(nums):
    """
    Run-length encode only zeros: common after MTF on BWT output.
    bzip2 uses a special RLE for runs of zeros.
    """
    out = []
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == 0:
            count = 0
            while i < n and nums[i] == 0:
                count += 1
                i += 1
            # Encode count in a variable-length way (simplified)
            out.append(0)
            out.append(count)  # In bzip2 this is more complex
        else:
            out.append(nums[i])
            i += 1
    return out

# Full pipeline demo
bwt, idx = bwt_via_suffix_array("BANANA")
mtf = mtf_encode(bwt)
print(f"BWT: {repr(bwt)} idx={idx}")
print(f"MTF: {mtf}")

4. Step-by-Step Example

Let us walk through burrows-wheeler compression concretely with the input string "BANANA". This example is small enough to show the entire matrix but contains enough repetition to illustrate clustering. We will follow the exact steps a compressor takes, including the sentinel handling.

Step 1: Append sentinel. We form S = "BANANA$". The '$' is defined to be smaller than 'A', 'B', and 'N', ensuring a unique sorted order. The length n = 7.

Step 2: Generate all rotations. We create 7 strings by cyclically rotating S:

• 0: B A N A N A $
• 1: A N A N A $ B
• 2: N A N A $ B A
• 3: A N A $ B A N
• 4: N A $ B A N A
• 5: A $ B A N A N
• 6: $ B A N A N A

Step 3: Sort rotations lexicographically. Comparing from the first character, with '$' smallest:

1. $ B A N A N A (rotation 6)
2. A $ B A N A N (rotation 5)
3. A N A $ B A N (rotation 3)
4. A N A N A $ B (rotation 1)
5. B A N A N A $ (rotation 0) ← original
6. N A $ B A N A (rotation 4)
7. N A N A $ B A (rotation 2)

Step 4: Extract columns. The first column F is "$AAABNN" (simply sorted characters of S). The last column L, which is the BWT output, is "ANNB$AA". Let us verify: last characters of the sorted rows in order are A, N, N, B, $, A, A. The primary index is 4, the row where the original string appears.

Observe the clustering: the three 'A's that were scattered in "BANANA" are now grouped as "AA" at the end of L, and the two 'N's are adjacent as "NN". For longer English text, this effect is far more pronounced, producing runs of hundreds of identical characters where the input had none.

Inverting the Example

To invert, we are given only L = "ANNB$AA" and primary_index = 4. We know F = sorted(L) = "$AAABNN". Using LF-mapping, we can reconstruct "BANANA$" backwards. We compute for each character its rank (occurrence number) in L and its first position in F.

LF-mapping table:

• L[0]=A (0th A) maps to F[1]=A
• L[1]=N (0th N) maps to F[5]=N
• L[2]=N (1st N) maps to F[6]=N
• L[3]=B (0th B) maps to F[4]=B
• L[4]=$ maps to F[0]=$
• L[5]=A (1st A) maps to F[2]=A
• L[6]=A (2nd A) maps to F[3]=A

Starting at row 4 (which holds '$' in L), we follow LF repeatedly: 4 → 0 → 1 → 5 → 2 → 6 → 3, reading L at each step gives "$ANANAB" reversed = "BANANA$". Stripping the sentinel recovers "BANANA". This O(n) walk avoids ever materializing the full matrix, which is why the inverse can be fast even for large blocks.

5. Complexity Analysis

The time and space complexity of burrows-wheeler compression depends heavily on the implementation chosen for the transform and the block size. The naive matrix method is simple to understand but impractical for production, while suffix-array-based methods achieve near-linear performance. The subsequent stages (MTF, RLE, Huffman) are linear and add negligible overhead compared to sorting.

Sorting dominates the cost. Comparing two rotations naively takes O(n) time, so sorting n rotations costs O(n^2 log n). Using suffix arrays with efficient sorting (e.g., prefix-doubling or SA-IS) reduces this to O(n log n) or even O(n). The inverse transform, when implemented with LF-mapping and counting sort, is linear O(n) because it requires only counting characters and a single backward traversal.

Space is also block-dependent. The BWT requires storing the block plus auxiliary arrays (suffix array, rank arrays). For a block size of 900KB (bzip2's maximum), this can mean several megabytes of RAM during compression, which is why bzip2 is more memory-intensive than gzip. Decompression needs less memory, typically just the block and a few integer arrays.

Here σ denotes alphabet size (typically 256 for bytes). The best, average, and worst cases for BWT are often similar because sorting dominates regardless of input distribution, though highly repetitive strings can cause many long common prefixes and degrade naive comparison-based sorts. Modern libraries mitigate this with induced sorting and prefix-doubling.

In practice, the block size is the primary tuning knob for the time-space tradeoff. Larger blocks improve compression ratio because the BWT has more context to cluster, but they increase memory and latency. bzip2 offers levels 1-9 corresponding to 100KB-900KB blocks. For streaming or low-memory environments, smaller blocks or alternative algorithms like LZ4 are preferred.

6. Variations and Optimizations

Several important variations improve upon the classic Burrows-Wheeler pipeline. The most significant is the choice of suffix array construction algorithm. The original bzip2 uses a modified Bentley-Sedgewick quicksort with fallback to a more robust sort for repetitive data. Modern implementations use SA-IS (Suffix Array Induced Sorting) or DivSufSort, which guarantee linear or O(n log n) worst-case performance and handle highly repetitive inputs without pathological slowdowns.

Another optimization is block size adaptation and partitioning. Instead of fixed 900KB blocks, some compressors use content-defined chunking or dynamically choose block boundaries to avoid splitting contexts. For example, compressing a file containing multiple concatenated documents may benefit from resetting the BWT at document boundaries. The FM-index, a compressed full-text index built on the BWT, uses sampled suffix array positions and rank dictionaries to support fast substring search without decompressing the whole block.

Alternative transforms after BWT also exist. While Move-to-Front is standard, more advanced encoders use Weighted Frequency Counting, Distance Coding, or Inversion Frequencies. These maintain a more sophisticated model of recency than simple move-to-front. Some variants replace Huffman coding with Arithmetic Coding or Asymmetric Numeral Systems (ANS) for better entropy coding, especially when the MTF output distribution is skewed.

Bijective and Tuned Variants

The Bijective Burrows-Wheeler Transform (BBWT) eliminates the need for a sentinel and primary index by sorting all Lyndon factors of the string. This can simplify handling of binary data where every byte value may appear. Another variant, the Sort Transform, sorts only fixed-length contexts rather than full rotations, trading some clustering for faster sorting.

For DNA and protein sequences, alphabet-specific optimizations matter. With σ=4 for DNA (A,C,G,T), the BWT matrix is highly compressible and specialized rank structures using bitvectors can accelerate LF-mapping. Tools like BWA and Bowtie use the FM-index over the BWT of the human genome to align billions of short reads efficiently, demonstrating that the same transform that compresses files can also index them.

7. Real-World Applications

The most famous application of burrows-wheeler compression is bzip2, which has been a standard Unix compressor since 1996. bzip2 is widely used for distributing source code tarballs, compressing log files, and in data archival where decompression speed is less critical than ratio. Many Linux distributions still ship man pages and kernel sources compressed with bzip2, and the format is supported by virtually every decompression library.

Beyond file archiving, the BWT is foundational in bioinformatics. The FM-index, which combines the BWT with auxiliary rank and select structures, is the core data structure in modern read aligners such as BWA, Bowtie, and SOAP2. These tools index the 3-billion-base human genome in under 4GB of memory and can locate a 100-base read in microseconds by performing backward search directly on the compressed BWT, without decompression. This has enabled large-scale genomics and personalized medicine.

Columnar databases and compressed text indexes also leverage the BWT. Systems like MonetDB and Apache Parquet use BWT-like reordering to improve compression of sorted columns with low cardinality. Full-text search engines such as those powering Wikipedia's search use BWT-based compressed suffix arrays to provide fast substring queries over huge document collections while keeping the index in RAM. In networking, the BWT has been explored for compressing HTTP responses with highly repetitive headers, though LZ-based methods dominate there due to streaming requirements.

When to Choose BWT-Based Compression

BWT-based compressors excel on text, source code, and structured data with strong local context but long-range repetition. They are ideal for offline batch compression where ratio matters more than speed, such as backups, scientific datasets, and genomic databases. They are less suitable for real-time streaming, small messages, or data that is already compressed or encrypted, where the transform overhead outweighs any gain.

For web servers and databases, the choice often comes down to latency versus storage. gzip (DEFLATE) remains faster for on-the-fly HTTP compression, while bzip2 or xz (LZMA) is chosen for archival. However, the FM-index variant of BWT is increasingly used inside databases themselves to provide both compression and indexing in a single structure, blurring the line between storage and search.

8. Comparison with Alternatives

To understand where burrows-wheeler compression fits, it helps to compare it against the major families of lossless compressors: Huffman coding, dictionary methods (LZ77, LZ78, LZW), DEFLATE (LZ77+Huffman), and modern context-modeling methods like PPM and LZMA. Each family makes different tradeoffs between speed, memory, ratio, and streaming capability.

Huffman coding alone is an entropy coder that assigns shorter codes to frequent symbols but does not exploit context or repetition beyond single-symbol frequencies. LZ77 and its derivatives replace repeated substrings with (distance, length) pointers, which is fast and streaming-friendly but can miss long-range context that BWT captures. PPM (Prediction by Partial Matching) builds explicit context models and often achieves the best ratio on text, but is slow and memory-heavy. LZMA combines dictionary and context modeling for excellent ratio at the cost of large dictionaries.

BWT occupies a middle ground: it provides context clustering similar to PPM but with simpler subsequent coding, and it achieves better ratio than LZ77 on text while remaining faster than PPM. However, it is block-based and not streaming, requiring the entire block to be buffered before output, which increases latency. Modern compressors like zstd and Brotli have largely superseded bzip2 for general use by combining fast LZ77 with large dictionaries and entropy coding, but BWT remains superior for highly repetitive text and for building searchable compressed indexes.

In practice, many systems choose hybrid approaches. For example, Brotli uses LZ77 with a large static dictionary and Huffman/ANS, achieving ratios close to bzip2 at much higher speed. For applications that also need to search the compressed data, however, no alternative matches the BWT's ability to serve as both a compressor and an index via the FM-index.

9. Common Mistakes and Best Practices

One of the most frequent mistakes when implementing burrows-wheeler compression is mishandling the sentinel character. The EOF marker must be lexicographically smaller than any character that can appear in the input and must be unique. Using '$' works for alphabetic text but fails for binary data that may contain '$'. For bytes, use '\x00' and ensure the input is treated as bytes, or use a bijective variant that avoids a sentinel altogether. Forgetting to store or transmit the primary index is another common error that makes inversion impossible.

Another pitfall is implementing the naive O(n²) matrix sort for large blocks. This will exhaust memory and time on inputs larger than a few kilobytes. Always use a suffix-array-based approach for blocks larger than a few KB, and consider using a well-tested library like DivSufSort rather than rolling your own sort. Similarly, implementing MTF with a linear scan over a 256-element alphabet is acceptable for teaching but should be optimized with a linked list or indexed structure for production.

Developers often expect the BWT alone to compress data. Remember that the BWT output is the same size as the input; without MTF/RLE and entropy coding, there is no size reduction. Conversely, applying BWT to already compressed, encrypted, or random data will not help and may even expand it slightly due to the primary index overhead. Always test compressibility first and bypass the BWT stage for incompressible blocks, as bzip2 does.

Best Practices

• Choose block size deliberately: 100KB for speed, 900KB for ratio. Profile on your data.
• Treat data as bytes, not strings, to handle arbitrary binary inputs correctly.
• Escape or handle sentinel collisions; consider bijective BWT for binary safety.
• Implement inverse BWT with LF-mapping and counting sort for O(n) performance, not naive table reconstruction.
• Combine BWT with MTF and a strong entropy coder (Huffman or ANS); do not use BWT in isolation.
• For repetitive data, use a robust suffix sorter (SA-IS, DivSufSort) to avoid worst-case O(n² log n) behavior.
• Add integrity checks (CRC32) per block, as bzip2 does, to detect corruption before inversion.

10. Interview Questions

Q1: Why is the Burrows-Wheeler Transform reversible even though we only store the last column and a primary index?

Because of the LF-mapping property. The first column F is just the sorted last column L, so it can be reconstructed. LF-mapping states that the k-th occurrence of a character in L corresponds to the k-th occurrence of the same character in F, preserving order. This allows us to navigate from a row in L to its predecessor in the original string. By starting at the primary index and repeatedly applying LF, we can reconstruct the entire original string backwards in O(n) time without ever storing the full matrix. The primary index tells us which row corresponds to the original string, anchoring the reconstruction.

Q2: How does Move-to-Front improve compression after the BWT?

The BWT groups identical characters that appear in similar contexts, creating runs like "AAAA" and "TTTT". Move-to-Front converts these runs into runs of zeros. It maintains a list of symbols ordered by recency; when a symbol is seen, its index is output and it is moved to the front. After the first occurrence of 'A' in a run, 'A' stays at position 0, so subsequent 'A's encode as 0. This transforms a clustered but still high-entropy string into a low-entropy stream dominated by small integers (especially 0), which is then efficiently compressed by Run-Length Encoding and Huffman coding. Without MTF, the BWT's clustering would not translate into bit savings.

Q3: What is the time complexity of BWT and how would you optimize it for large inputs?

Naively generating and sorting all rotations costs O(n² log n) time and O(n²) space, which is infeasible beyond tiny inputs. The optimized approach builds the suffix array, which can be done in O(n log n) with standard sorting or O(n) with SA-IS. Once the suffix array is known, the BWT is derived in O(n) by taking the character before each suffix. The inverse is O(n + σ) using LF-mapping with counting sort. For large blocks (e.g., 900KB in bzip2), I would use a linear-time suffix array library like DivSufSort, process data in blocks to bound memory, and implement MTF and Huffman in linear time. I would also mention block-size tuning as a tradeoff between ratio and memory.

Q4: Compare BWT-based compression (bzip2) with LZ77-based compression (gzip). When would you choose one over the other?

bzip2 (BWT) achieves 10-20% better ratio on text and structured data because it captures long-range context via sorting, and it can also serve as a searchable FM-index. However, it is block-based, slower, uses more memory (megabytes per block), and is not streaming-friendly. gzip (LZ77+ Huffman) is much faster, uses a small 32KB sliding window, streams byte-by-byte with low latency, and is ideal for web servers and real-time compression. I would choose bzip2 for offline archival, log compression, and genomics where ratio or indexability matters, and gzip (or zstd) for HTTP, databases, and real-time pipelines where speed and streaming are critical.

Q5: What is the FM-index and how does it relate to the BWT?

The FM-index (Ferragina-Manzini index) is a compressed full-text index built on top of the BWT. It stores the BWT string plus auxiliary structures: rank dictionaries (to count occurrences of a character up to a position in L) and a sampled suffix array. Using backward search, it can count and locate occurrences of a pattern P in O(|P|) time by iteratively applying LF-mapping, without decompressing the text. This makes it possible to index the human genome in a few gigabytes and search it in microseconds, which is why it powers bioinformatics aligners like BWA and Bowtie. It demonstrates that the BWT is not just a compressor but also an index.