FSST
FSST compresses strings with a shared static table of byte-sequence symbols so individual strings can be decoded independently.
Mechanism: FSST8 replaces sequences of 1-8 bytes with single-byte codes. Code 255 escapes the following literal byte, allowing a fixed table to represent unseen input. FSST12 is a different variant. [1] [3]
Access: The decoder needs the selected string's encoded bytes and the matching symbol table, not preceding strings. The caller still supplies its location and encoded length. This is string-level access, not arbitrary character indexing or a disk-read guarantee. [1] [2]
Comparison: Equality on compressed values requires a common table and compatible encoding. Equal code bytes from different tables can decode differently. Whole-value dictionary coding removes repeated complete strings; FSST can additionally compress the dictionary's distinct strings. [1] [4]
Output capacity: In the pinned binary-mode decoder, bytes 00 ff 21 yield ram! with a constructed table. With two output bytes available, only ra is stored while the returned decoded length remains 4. A caller must check that length against capacity before consuming the result. Rebinding code 0 to rom changes the same stream to rom!. [2] [4]
Relations
Advantages
- A read-only decoder table can be shared across decoding threads. [2]
Limitations
- Encoded payload size excludes the shared table and string-location metadata; savings must include those costs. [1, 2]
- The published API controls cover valid streams only and do not establish rejection of malformed or adversarial input. [4]
Citations
- Boncz, Neumann and Leis (2020): FSST: Fast Random Access String Compression, PVLDB 13(11), sections 2-6
- FSST pinned API: symbol table, binary mode, independent decoding and output truncation
- FSST project README at e638d4c: byte codes and FSST12 distinction
- Hesela: pinned FSST decoder controls, source, observations and replay
Sources & caveats
- Source synthesis of the 2020 paper and a pinned author-maintained implementation; no paper throughput or compression-ratio result is claimed for another workload.
- Ten constructed valid-stream cases run at two compiler optimization levels on one machine. Tables are manually populated, not trained; the experiment does not exercise table serialization or malformed input.