Clast.Fsst 0.2.0

Clast.Fsst

A C# implementation of FSST (Fast Static Symbol Table) string compression. FSST is a lightweight, byte-oriented dictionary compressor designed for columnar databases — it produces small, randomly-accessible compressed strings with very fast decompression.

This library is part of the clast-project.

Features

• FSST8 — 1-byte codes (up to 255 symbols) plus an escape byte for unmatched literals.
• FSST12 — 12-bit codes packed two-per-three-bytes (up to 4096 symbols, no escape).
• Single-string and batch compress / decompress.
• Versioned binary format for serializing symbol tables.

Target frameworks

The test suite multi-targets net48, net8.0, and net10.0 so the netstandard2.0 build is exercised end-to-end through a .NET Framework 4.8 host.

Quick start

using Clast.Fsst;
using System.Text;

var corpus = new[]
{
    Encoding.UTF8.GetBytes("the quick brown fox jumps over the lazy dog"),
    Encoding.UTF8.GetBytes("the lazy dog sleeps in the shade"),
};

// Build a symbol table from a representative corpus.
SymbolTable table = FsstEncoder.BuildSymbolTable(corpus);

// Compress / decompress a single value.
byte[] compressed   = FsstEncoder.Compress(table, corpus[0]);
FsstDecoder decoder = FsstDecoder.FromSymbolTable(table);
byte[] roundtrip    = decoder.Decompress(compressed);

// Or compress / decompress a batch into caller-supplied buffers (Arrow-style prefix-sum offsets):
var (data, lengths) = FsstEncoder.CompressBatch(table, corpus);
var dst             = new byte[FsstDecoder.MaxDecompressedLength(data.Length)];
var offsets         = new int[corpus.Length + 1];
decoder.TryDecompressBatch(data, lengths, dst, offsets, out int totalWritten);
// Item i is now in dst[offsets[i]..offsets[i+1]].

FSST12

Fsst12Encoder / Fsst12Decoder follow the same shape but use 12-bit codes (no escape, 1.5 bytes per code on average). Prefer FSST12 when the input has a large effective symbol vocabulary; prefer FSST8 when codes must be byte-aligned for cheap random-access decoding.

SymbolMap map         = Fsst12Encoder.BuildSymbolTable(corpus);
byte[] compressed     = Fsst12Encoder.Compress(map, corpus[0]);
Fsst12Decoder decoder = Fsst12Decoder.FromSymbolMap(map);
byte[] roundtrip      = decoder.Decompress(compressed);

Persisting a symbol table

byte[] tableBytes = FsstSerializer.ExportFsst8(table);
// ... store it, send it over the wire ...
SymbolTable restored = FsstSerializer.ImportFsst8(tableBytes);

// Or skip straight to a decoder:
FsstDecoder decoder = FsstSerializer.ImportFsst8Decoder(tableBytes);

The FSST8 export uses the cwida/fsst fsst_export() on-disk format (17-byte header followed by raw symbol bytes in code order), so payloads are interoperable with the reference C++ implementation.

ExportFsst12 / ImportFsst12 / ImportFsst12Decoder are the FSST12 equivalents and use a separate length-prefixed framing (cwida does not publish an FSST12 export format).

Bring-your-own framing

Other consumers (Lance, for example) wrap symbol tables in their own container. FsstDecoder.FromSymbols skips the wire format entirely and takes pre-extracted symbols indexed by code:

// lengths[i] is the byte length of the symbol for code i (0 = unused slot).
// packedValues holds 8 little-endian bytes per code.
FsstDecoder decoder = FsstDecoder.FromSymbols(lengths, packedValues);

Parse your container's framing yourself, hand over the per-code lengths and 8-byte slots, and you get back a decoder.

Project layout

src/Fsst/                   library (Clast.Fsst.dll)
test/Fsst.Tests/            xUnit test suite
benchmarks/Fsst.Benchmarks/ BenchmarkDotNet harness

Build & test

dotnet build
dotnet test

References

• FSST: Fast Random Access String Compression — Peter Boncz, Thomas Neumann, Viktor Leis. PVLDB Vol. 13, 2020.
• Reference C++ implementation: https://github.com/cwida/fsst

License

Licensed under the Apache License, Version 2.0. See LICENSE.