# How BWT (Burrows-Wheeler Transform) Works in Kanzi: Implementation Guide

> Discover how Kanzi's BWT implementation uses DivSufSort and parallel processing for efficient compression. Learn when to apply Burrows-Wheeler Transform with this guide.

- Repository: [flanglet/kanzi-cpp](https://github.com/flanglet/kanzi-cpp)
- Tags: how-to-guide
- Published: 2026-03-02

---

**TL;DR:** Kanzi’s `BWT` class implements a fast, block-based Burrows-Wheeler Transform using the DivSufSort algorithm to build suffix arrays, splits data into up to eight parallel chunks with primary indexes stored by `BWTBlockCodec`, and automatically selects between a merge-based inverse for blocks ≤ 2 MiB and a parallel BiPSIv2 algorithm for larger blocks.

The **Burrows-Wheeler Transform (BWT)** in the Kanzi compression library serves as a reversible preprocessing stage that reorders data to improve locality for entropy coding. According to the flanglet/kanzi-cpp source code, the implementation balances memory efficiency with high throughput by leveraging modern parallel processing techniques and optimized suffix-array construction.

## Kanzi BWT Architecture

The BWT implementation consists of three tightly integrated layers: the core transform engine, the suffix-sorting algorithm, and the block codec wrapper that manages metadata.

### Core Components

**`BWT`** ([`src/transform/BWT.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWT.hpp) and [`src/transform/BWT.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWT.cpp)) provides the main `forward()` and `inverse()` methods. The class maintains an internal suffix-array buffer (`_sa`) and an array of eight primary indexes (`_primaryIndexes[8]`) required for lossless reconstruction.

**`DivSufSort`** ([`src/transform/DivSufSort.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/DivSufSort.cpp)) handles the computationally intensive forward transform via the `computeBWT()` method. This algorithm constructs the suffix array while simultaneously writing the transformed bytes to the destination buffer.

**`BWTBlockCodec`** ([`src/transform/BWTBlockCodec.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWTBlockCodec.cpp)) acts as a serialization layer. It prepends a header containing the mode byte and serialized primary indexes before delegating to the raw `BWT` engine, enabling seamless integration into the full compressor pipeline.

### Block Chunking Strategy

Kanzi processes data in blocks that are automatically split into chunks based on size. The `getBWTChunks()` method in [`BWT.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/BWT.hpp) implements the following logic:

```cpp
inline int BWT::getBWTChunks(int size)
{
    return (size < BLOCK_SIZE_THRESHOLD1) ? 1 : 8;
}

```

Blocks smaller than **256 bytes** (`BLOCK_SIZE_THRESHOLD1`) use a single chunk, while larger blocks always use **8 chunks**. Each chunk receives its own primary index—the row of the suffix array containing the original string terminator—which `BWTBlockCodec` serializes into the bitstream using variable-byte encoding.

## Forward BWT Transform

The forward transform begins with input validation via `SliceArray` objects. The `BWT::forward()` method allocates or reuses the internal suffix-array buffer, then invokes the DivSufSort engine:

```cpp
if (_saAlgo.computeBWT(src, dst, _sa, count,
                      _primaryIndexes, getBWTChunks(count)) == false)
    return false;

```

The `computeBWT()` function in [`DivSufSort.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/DivSufSort.cpp) performs three simultaneous operations: building the suffix array (`_sa`), writing the permuted bytes to the destination (`dst`), and recording the primary index for each chunk in the `_primaryIndexes` array. This approach eliminates the need for separate sorting and permutation passes, reducing memory traffic.

## Inverse BWT Algorithms

Kanzi implements two distinct inverse algorithms selected automatically based on block size. The decision occurs in `BWT::inverse()`:

```cpp
if (count <= BLOCK_SIZE_THRESHOLD2)   // 2 MiB
    return inverseMergeTPSI(input, output, count);
else
    return inverseBiPSIv2(input, output, count);

```

**`inverseMergeTPSI`** employs a classic "last-to-first" reconstruction using bucket histograms. This single-threaded algorithm minimizes overhead and memory usage for modest block sizes, making it ideal for real-time streaming scenarios.

**`inverseBiPSIv2`** constructs auxiliary data structures (`_buffer`, `buckets`, `fastBits`) and launches up to eight parallel `InverseBiPSIv2Task` instances when a thread-pool is available. This parallel reconstruction dramatically reduces latency on large blocks while maintaining the same output correctness.

## BWTBlockCodec Wrapper

While the raw `BWT` class requires manual management of primary indexes, `BWTBlockCodec` automates this process by encoding metadata into a compact header. The forward path writes a mode byte followed by the primary index bytes for every chunk:

```cpp
const kanzi::byte mode = kanzi::byte((logNbChunks << 2) | (pIndexSize - 1));
for (int i = 0, idx = 1; i < chunks; i++) {
    const int primaryIndex = _pBWT->getPrimaryIndex(i) - 1;
    int shift = (pIndexSize - 1) << 3;
    while (shift >= 0) {
        dst[idx++] = kanzi::byte(primaryIndex >> shift);
        shift -= 8;
    }
}
dst[0] = mode;

```

During decoding, `BWTBlockCodec` reads the mode byte to determine chunk count and index size, restores the primary indexes via `setPrimaryIndex()`, and then invokes the appropriate inverse method. This abstraction allows the high-level `Compressor` and `Decompressor` classes to treat BWT as a transparent transform stage.

## When to Use BWT in Kanzi

**Use BWT as a preprocessing step** before entropy coding when your data contains repeated substrings. The transform clusters identical byte sequences, creating long runs that entropy coders like ANS, Huffman, or FPAQ can compress more effectively.

**For textual data, logs, and source code**, BWT significantly improves compression ratios by exploiting repetitive lexical patterns. **For binary blobs with localized redundancy**—such as images with palettes or structured archives—the transform still provides benefits by grouping similar byte sequences, though the gains depend on the specific entropy distribution.

**Block size considerations:**
- **Small blocks (< 256 bytes):** Chunking is disabled; BWT works but offers limited parallelism.
- **Medium blocks (256 bytes – 2 MiB):** The single-threaded `inverseMergeTPSI` provides optimal throughput without thread-pool overhead.
- **Large blocks (≥ 2 MiB):** The parallel `inverseBiPSIv2` automatically engages, utilizing up to 8 threads for fast reconstruction while maintaining memory efficiency.

## Code Examples

### Direct BWT Usage

The following example demonstrates low-level access to the `BWT` class without the codec wrapper, requiring manual primary index management:

```cpp
#include "transform/BWT.hpp"
#include "SliceArray.hpp"

using namespace kanzi;

// Forward transform
const int blockSize = 1024;
byte input[blockSize];   // fill with source data
byte output[blockSize];

SliceArray<byte> in(input, blockSize, 0);
SliceArray<byte> out(output, blockSize, 0);

BWT bwt;
bwt.forward(in, out, blockSize);

// Capture primary indexes for later inversion
int chunks = BWT::getBWTChunks(blockSize);
int primary[8];
for (int i = 0; i < chunks; ++i)
    primary[i] = bwt.getPrimaryIndex(i);

// Inverse transform
BWT bwtInv;
for (int i = 0; i < chunks; ++i)
    bwtInv.setPrimaryIndex(i, primary[i]);

byte recovered[blockSize];
SliceArray<byte> rev(recovered, blockSize, 0);
out._index = 0;  // reset read pointer
bwtInv.inverse(out, rev, blockSize);

```

### Using BWTBlockCodec

For integration into compression pipelines, use `BWTBlockCodec` to handle headers automatically:

```cpp
#include "transform/BWTBlockCodec.hpp"
#include "SliceArray.hpp"

using namespace kanzi;

int blockSize = 65536;
byte src[blockSize];
byte dst[blockSize + 64];  // extra space for header

SliceArray<byte> ia(src, blockSize, 0);
SliceArray<byte> oa(dst, sizeof(dst), 0);

Context ctx;
ctx.putInt("jobs", 4);       // enable 4-thread parallelism

BWTBlockCodec codec(ctx);
codec.forward(ia, oa, blockSize);  // writes header + BWT data

// Decode
SliceArray<byte> decIn(dst, oa._index, 0);
byte plain[blockSize];
SliceArray<byte> decOut(plain, blockSize, 0);

codec.inverse(decIn, decOut, blockSize);

```

## Summary

- Kanzi’s `BWT` class implements the Burrows-Wheeler Transform using the **DivSufSort** algorithm for efficient suffix-array construction.
- The implementation automatically partitions blocks into **8 chunks** for parallel processing when data exceeds 256 bytes, storing primary indexes in `_primaryIndexes[8]`.
- **Inverse reconstruction** selects between `inverseMergeTPSI` (single-threaded, ≤ 2 MiB) and `inverseBiPSIv2` (parallel, > 2 MiB) based on block size thresholds defined in [`src/transform/BWT.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWT.cpp).
- **`BWTBlockCodec`** manages header serialization, encoding chunk counts and primary indexes using a compact mode byte format.
- Use BWT when preprocessing data for entropy coding, particularly on text or repetitive binary data, and let the library automatically optimize chunking and threading.

## Frequently Asked Questions

### What is the difference between `BWT` and `BWTBlockCodec` in Kanzi?

**`BWT`** ([`src/transform/BWT.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWT.hpp)) is the low-level transform engine that requires manual handling of primary indexes via `getPrimaryIndex()` and `setPrimaryIndex()`. **`BWTBlockCodec`** ([`src/transform/BWTBlockCodec.cpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/transform/BWTBlockCodec.cpp)) is a higher-level wrapper that automatically serializes primary indexes into a header during forward transformation and restores them during inverse transformation, making it suitable for integration into the full compression pipeline without manual state management.

### How does Kanzi decide which inverse BWT algorithm to use?

The selection occurs in `BWT::inverse()` based on the `BLOCK_SIZE_THRESHOLD2` constant (2 MiB). For blocks **≤ 2 MiB**, Kanzi uses **`inverseMergeTPSI`**, a memory-efficient merge-based reconstruction. For larger blocks, it invokes **`inverseBiPSIv2`**, which builds auxiliary bucket structures and distributes work across up to 8 parallel threads when a thread-pool is available, significantly improving decoding speed on multi-core systems.

### Why does Kanzi split BWT blocks into 8 chunks?

Chunking enables **parallel inverse transformation** and reduces memory latency. The `getBWTChunks()` method returns 1 for blocks under 256 bytes to minimize overhead, and 8 for larger blocks to maximize parallelism in `inverseBiPSIv2`. Each chunk maintains an independent primary index, allowing the inverse algorithm to reconstruct portions of the output simultaneously without synchronization conflicts during the core computation phase.

### Can I use Kanzi's BWT implementation independently of the full compressor?

Yes. While `BWTBlockCodec` integrates seamlessly with Kanzi's `Compressor` and `Decompressor` classes, the `BWT` class itself is self-contained and can be instantiated directly for custom applications. You must manually preserve the primary indexes returned by `getPrimaryIndex()` for each chunk and provide them to `setPrimaryIndex()` before calling `inverse()`, or use `BWTBlockCodec` to automate this metadata handling.