BWT Compression Pipeline

Burrows-Wheeler as a Reversible Permutation

The Burrows-Wheeler Transform rearranges a sequence without discarding information. For a sequence $S$ of length $n$, form its $n$ cyclic rotations, sort them lexicographically, and read the final symbol of each row. The resulting last column $L$ is the BWT. Record the row containing the unrotated $S$ as the primary index.

The transform does not reduce size by itself: $L$ contains the same symbol multiset as $S$. Its value is structural. Rows beginning with similar contexts become adjacent, so symbols preceding those contexts cluster in $L$. Repetitive or predictable input therefore tends to produce runs that later transforms can exploit.

A unique minimum sentinel is another common convention. It identifies the original row and turns sorted rotations into sorted suffixes. Without a sentinel, the primary index is required; the educational implementation below uses that convention so no alphabet symbol must be reserved.

Worked Example

Build the BWT

Transform banana by sorting its cyclic rotations:

abanan
anaban
ananab
banana — primary row 3 using zero-based indexing
nabana
nanaba

Reading the final column gives nnbaaa, so

$$ \operatorname{BWT}(\texttt{banana})=(\texttt{nnbaaa},3). $$

The output still contains three a symbols, two n symbols, and one b. The rearrangement groups all three a symbols into a run, while the primary index distinguishes banana from its other cyclic rotations.

Inverting with LF-Mapping

Let $F$ be the sorted first column and $L$ the BWT last column. Stable sorting preserves the order of equal symbols: the first a in $L$ corresponds to the first a in $F$, the second to the second, and so on. Labeling each symbol by its occurrence rank makes the correspondence unique.

Define $C[c]$ as the number of symbols in $L$ strictly smaller than $c$, and let $\operatorname{rank}_c(i)$ count occurrences of $c$ in $L[0\dots i)$. Then

$$ \operatorname{LF}(i)=C[L[i]]+\operatorname{rank}_{L[i]}(i). $$

If row $i$ begins at text position $p$, $\operatorname{LF}(i)$ begins at $p-1$ modulo $n$. Starting at the primary row, emit $L[i]$, follow LF, and repeat $n$ times; reversing the emitted sequence recovers the input. The implementation is deliberately transparent. Production compressors construct the BWT with suffix-array or specialized linear-time algorithms rather than materializing every rotation.

from collections import Counter
from collections.abc import Hashable, Sequence
from typing import TypeVar

Symbol = TypeVar("Symbol", bound=Hashable)


def bwt(sequence: Sequence[Symbol]) -> tuple[list[Symbol], int]:
    """Return the cyclic BWT last column and zero-based primary index."""
    n = len(sequence)
    if n == 0:
        return [], 0
    rotations = list(range(n))
    rotations.sort(
        key=lambda start: tuple(sequence[(start + offset) % n] for offset in range(n))
    )
    return [sequence[(start - 1) % n] for start in rotations], rotations.index(0)


def inverse_bwt(last_column: Sequence[Symbol], primary_index: int) -> list[Symbol]:
    """Invert a cyclic BWT using LF-mapping."""
    n = len(last_column)
    if n == 0:
        if primary_index != 0:
            raise ValueError("empty BWT requires primary index 0")
        return []
    if not 0 <= primary_index < n:
        raise ValueError("primary index is outside the BWT")

    frequencies = Counter(last_column)
    cumulative: dict[Symbol, int] = {}
    total = 0
    for symbol in sorted(frequencies):
        cumulative[symbol] = total
        total += frequencies[symbol]

    seen: dict[Symbol, int] = {}
    lf: list[int] = []
    for symbol in last_column:
        rank = seen.get(symbol, 0)
        lf.append(cumulative[symbol] + rank)
        seen[symbol] = rank + 1

    row = primary_index
    output: list[Symbol] = []
    for _ in range(n):
        output.append(last_column[row])
        row = lf[row]
    output.reverse()
    return output


def mtf_encode(sequence: Sequence[Symbol]) -> tuple[list[int], list[Symbol]]:
    alphabet = sorted(set(sequence))
    symbols = alphabet.copy()
    output: list[int] = []
    for symbol in sequence:
        index = symbols.index(symbol)
        output.append(index)
        symbols.insert(0, symbols.pop(index))
    return output, alphabet


def mtf_decode(indices: Sequence[int], alphabet: Sequence[Symbol]) -> list[Symbol]:
    symbols = list(alphabet)
    output: list[Symbol] = []
    for index in indices:
        if not 0 <= index < len(symbols):
            raise ValueError("MTF index is outside the alphabet")
        output.append(symbols[index])
        symbols.insert(0, symbols.pop(index))
    return output


def rle_encode(values: Sequence[int]) -> list[tuple[int, int]]:
    if not values:
        return []
    runs: list[tuple[int, int]] = []
    value, length = values[0], 1
    for current in values[1:]:
        if current == value:
            length += 1
        else:
            runs.append((value, length))
            value, length = current, 1
    runs.append((value, length))
    return runs


def rle_decode(runs: Sequence[tuple[int, int]]) -> list[int]:
    output: list[int] = []
    for value, length in runs:
        if length <= 0:
            raise ValueError("run lengths must be positive")
        output.extend([value] * length)
    return output


if __name__ == "__main__":
    last, primary = bwt("banana")
    assert "".join(last) == "nnbaaa"
    assert primary == 3
    assert "".join(inverse_bwt(last, primary)) == "banana"

    mtf, alphabet = mtf_encode(last)
    assert alphabet == ["a", "b", "n"]
    assert mtf == [2, 0, 2, 2, 0, 0]
    assert mtf_decode(mtf, alphabet) == last
    runs = rle_encode(mtf)
    assert runs == [(2, 1), (0, 1), (2, 2), (0, 2)]
    assert rle_decode(runs) == mtf

    for sample in ["a", "aaaa", "abracadabra", "mississippi"]:
        transformed, index = bwt(sample)
        assert "".join(inverse_bwt(transformed, index)) == sample
    assert bwt("") == ([], 0)
    assert inverse_bwt([], 0) == []

Move-to-Front and Run Formation

The BWT makes symbols with similar following contexts adjacent. Move-to-front converts this locality into small integers: maintain an ordered alphabet, emit each symbol’s current index, and move that symbol to the front. Repeated symbols become zeros, while recently seen symbols receive small positive indices.

For banana, nnbaaa becomes [2,0,2,2,0,0] from initial alphabet [a,b,n]. Run-length encoding then gives [(2,1),(0,1),(2,2),(0,2)]. Real BWT compressors often specialize zero-run encoding because long zero runs are common after MTF; bzip2, for example, uses dedicated run symbols before Huffman coding.

Entropy Coding and Evaluation

An entropy coder assigns short representations to frequent tokens. Huffman coding uses integral-length prefix codes and is simple to decode; arithmetic or range coding approaches fractional ideal lengths and supports adaptive contexts. In a BWT pipeline, the coder consumes MTF values or specialized run tokens rather than original symbols.

Evaluation must count all decoding metadata: primary index or sentinel policy, alphabet, block length, run format, code tables or model state, and integrity checks. Large blocks expose more context and usually compress better; smaller blocks reduce memory, latency, corruption scope, and random-access cost. Measure compressed bytes, encode/decode throughput, peak memory, and varied corpora. BWT and MTF preserve item count, RLE may grow or shrink, and only the entropy stage necessarily packs the representation into fewer bits.

Stage	Exact representation for `banana`	Logical payload	Naive packed payload	Required local metadata	Main contribution
Original UTF-8	`banana`	6 symbols	48 bits	Length or external framing	Baseline
BWT	`nnbaaa`	6 symbols	48 bits	Primary index 3, requiring 3 bits for six rows	Groups symbols preceding similar contexts
MTF with alphabet `[a,b,n]`	`[2,0,2,2,0,0]`	6 ranks	12 bits at 2 bits per rank	Ordered alphabet plus primary index	Converts locality into small values and zeros
Generic RLE	`[(2,1),(0,1),(2,2),(0,2)]`	4 pairs	16 bits using 2-bit values and counts	Pair format, alphabet, primary index	Exposes runs but expands this tiny example
Static Huffman over MTF	`0` and `2` each use a 1-bit code	6 coded ranks	6 payload bits	Codebook, count, alphabet, primary index	Removes statistical redundancy
Complete framed block	Header plus coded payload	Format-dependent	More than 6 bits	Magic, sizes, model, primary index, checksum	Enables reliable independent decoding

Cookie Consent