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

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 and 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) 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) 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 implements the following logic:

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:

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

The computeBWT() function in 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():

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:

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:

#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:

#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.
• 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) is the low-level transform engine that requires manual handling of primary indexes via getPrimaryIndex() and setPrimaryIndex(). BWTBlockCodec (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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}