A Finite State Transducer (FST) is a compressed, immutable key-value map that stores sorted byte sequences and their associated output values in a structure that shares common prefixes and suffixes. Unlike a hash map that stores each key independently, an FST exploits the redundancy between similar keys to achieve compression ratios of 10-50x while still supporting O(k) lookups where k is the key length.
FSTs are the backbone of full-text search indexes. Lucene, Elasticsearch, and the BurntSushi/fst library (Vellum-compatible in Go) use FSTs to map terms to posting list offsets. As an example, a typical search engine implements an FST-based term dictionary for its search index, enabling memory-efficient storage of millions of terms with instant prefix, range, and exact-match lookups.
The power of FSTs comes from their dual compression: they share prefixes (like a trie) and also share suffixes (like a DAWG). This makes them dramatically smaller than tries for natural-language term dictionaries where keys like “running”, “runner”, “runs” share both a prefix “run” and common suffix patterns.
An FST is a minimal acyclic deterministic finite automaton with outputs. “Minimal” means no two states are equivalent, “acyclic” means no loops (keys are finite), and “deterministic” means each state has at most one transition per input byte. This minimality is what gives FSTs their compression.
Because FSTs share both prefixes and suffixes, they are smaller than tries for the same key set. A trie with 10M English words might use 500MB; the equivalent FST can fit in 30-50MB. This difference is what makes FSTs practical for in-memory term dictionaries at scale.
FSTs are built incrementally from keys that must arrive in sorted order. The builder maintains a stack of “unfrozen” states representing the current path from root. When a new key diverges from the previous key, the builder “freezes” states that are no longer needed (compiling them into the output), checks if any frozen state is equivalent to an existing one (suffix sharing), and reuses it if so. This single-pass algorithm runs in O(n * k) time where n is the number of keys and k is the average key length.
Output values are distributed across transitions such that the total output for any key equals the sum of outputs along its path. When two keys share a prefix, the common output is pushed as far toward the root as possible, and the remaining difference is placed on the diverging transitions. This ensures each key’s total output is correct while maximizing sharing.
To look up a key, start at the root state and follow transitions matching each byte of the key, accumulating the output values. If at any point no matching transition exists, the key is not in the FST. If the final state is an accepting state, the accumulated output is the associated value. This runs in O(k) time with excellent cache behavior since the FST data is accessed sequentially.
FSTs natively support prefix queries: navigate to the state after the prefix bytes, then enumerate all reachable accepting states. Range queries work by starting the enumeration at the lower bound and stopping at the upper bound. Both operations are streaming — they produce results incrementally without materializing the full result set.
FST construction requires sorted input, which is why search engines build FSTs during the segment merge phase — the keys are already sorted from the merge sort. This constraint is not a limitation in practice; it’s a natural fit for the batch-oriented indexing pipeline.
In a typical inverted index implementation, the FST serves as the term dictionary. Each segment’s term dictionary is an FST mapping term bytes to a pair of (posting list offset, term frequency), enabling both exact lookups and prefix-based autocomplete without separate data structures.
Since FSTs are immutable byte sequences, they are ideal candidates for memory mapping. The FST file is mmap’d into the process address space, and the OS page cache handles caching automatically. Queries access the FST through byte-level pointer arithmetic with zero deserialization cost.
During construction, the builder maintains a registry (hash map) of recently frozen states. When a new state is frozen, it checks the registry for an equivalent state (same transitions, same outputs, same finality). If found, the existing state is reused. The registry has a bounded size to limit memory during construction; evicted entries simply miss the deduplication opportunity.
The Vellum format (from the Go library) encodes each state as a variable-length byte sequence with transitions packed as (input byte, output delta, target state offset) tuples. Single-transition states use a compact one-byte encoding. The format is designed for sequential reading and random access via state offsets.
package search
import (
"bytes"
"encoding/binary"
"sort"
)
type FSTBuilder struct {
// Simplified FST builder for illustration
frozen []fstState
unfrozen []builderState
registry map[uint64]int // hash → state index
lastKey []byte
}
type builderState struct {
transitions []transition
isFinal bool
finalOutput uint64
}
type transition struct {
input byte
output uint64
target int // index into frozen states, -1 if unfrozen
}
type fstState struct {
transitions []transition
isFinal bool
finalOutput uint64
}
func NewFSTBuilder() *FSTBuilder {
return &FSTBuilder{
registry: make(map[uint64]int),
unfrozen: []builderState{{}}, // root state
}
}
func (b *FSTBuilder) Add(key []byte, value uint64) error {
if bytes.Compare(key, b.lastKey) <= 0 && len(b.lastKey) > 0 {
return fmt.Errorf("keys must be added in sorted order")
}
// Find common prefix length with previous key
commonLen := 0
for i := 0; i < len(key) && i < len(b.lastKey); i++ {
if key[i] != b.lastKey[i] {
break
}
commonLen++
}
// Freeze states beyond the common prefix
for i := len(b.unfrozen) - 1; i > commonLen; i-- {
b.freezeState(i)
}
// Add new unfrozen states for the remaining key bytes
for i := commonLen; i < len(key); i++ {
b.unfrozen = append(b.unfrozen, builderState{})
parent := &b.unfrozen[len(b.unfrozen)-2]
parent.transitions = append(parent.transitions, transition{
input: key[i],
output: 0,
target: -1, // points to next unfrozen state
})
}
// Mark the final state and distribute the output value
last := &b.unfrozen[len(b.unfrozen)-1]
last.isFinal = true
last.finalOutput = value
b.lastKey = append(b.lastKey[:0], key...)
return nil
}
// Lookup performs an exact key lookup in the compiled FST
func (fst *FST) Lookup(key []byte) (uint64, bool) {
state := 0 // start at root
var output uint64
for _, b := range key {
found := false
for _, t := range fst.states[state].transitions {
if t.input == b {
output += t.output
state = t.target
found = true
break
}
}
if !found {
return 0, false
}
}
if fst.states[state].isFinal {
return output + fst.states[state].finalOutput, true
}
return 0, false
}const std = @import("std");
pub const FSTReader = struct {
data: []const u8,
root_offset: u64,
pub fn init(mmap_data: []const u8) FSTReader {
// Last 8 bytes store the root state offset
const len = mmap_data.len;
const root = std.mem.readInt(u64, mmap_data[len - 8 ..][0..8], .little);
return .{
.data = mmap_data,
.root_offset = root,
};
}
/// Look up a term and return its posting list offset
pub fn lookup(self: *const FSTReader, term: []const u8) ?u64 {
var state_offset = self.root_offset;
var output: u64 = 0;
for (term) |byte| {
const state = self.readState(state_offset);
const trans = state.findTransition(byte) orelse return null;
output += trans.output;
state_offset = trans.target;
}
const final_state = self.readState(state_offset);
if (final_state.is_final) {
return output + final_state.final_output;
}
return null;
}
/// Enumerate all terms with a given prefix
pub fn prefixIterator(
self: *const FSTReader,
prefix: []const u8,
) ?PrefixIterator {
var state_offset = self.root_offset;
var output: u64 = 0;
// Navigate to the prefix endpoint
for (prefix) |byte| {
const state = self.readState(state_offset);
const trans = state.findTransition(byte) orelse return null;
output += trans.output;
state_offset = trans.target;
}
return PrefixIterator{
.fst = self,
.stack = &.{.{ .offset = state_offset, .output = output }},
.stack_len = 1,
};
}
fn readState(self: *const FSTReader, offset: u64) State {
// Decode variable-length state from the byte array
const ptr = self.data[@intCast(offset)..];
const header = ptr[0];
const is_final = (header & 0x80) != 0;
const num_transitions = header & 0x7F;
var state = State{
.is_final = is_final,
.final_output = 0,
.transitions = undefined,
.num_transitions = num_transitions,
};
var pos: usize = 1;
if (is_final) {
state.final_output = readVarInt(ptr[pos..], &pos);
}
for (0..num_transitions) |i| {
state.transitions[i] = .{
.input = ptr[pos],
.output = readVarInt(ptr[pos + 1 ..], &pos),
.target = readVarInt(ptr[pos..], &pos),
};
pos += 1;
}
return state;
}
};FSTs compress ordered key-value maps by sharing both prefixes and suffixes, achieving 10-50x compression over hash maps while maintaining O(key length) lookup time. They are the data structure of choice for search engine term dictionaries.
The combination of immutability, compact encoding, and sequential byte layout makes FSTs ideal for memory-mapped access. A 50MB FST file serving millions of terms requires zero deserialization — the OS page cache is your caching layer.