OptFSST: Optimized FSST String Compression

Strings constitute a substantial fraction of the data processed by modern analytical systems, so lightweight compression that still permits fast random access is a critical building block for efficient query processing. Fast Static Symbol Table (FSST) was designed for exactly this setting: it replaces frequent byte sequences with compact codes while preserving the ability to decompress individual strings independently of one another. This independence is what makes FSST attractive for field-level and columnar compressors, where a query may need to materialize only a handful of values rather than an entire block.

However, the authors (Hedi Chehaidar, Mihail Stoian, Moritz Stargalla, and Andreas Kipf) observe that FSST's compression effectiveness is limited by two greedy decisions: greedy symbol selection during table construction and greedy encoding at compression time. Both leave measurable encoding gains on the table. OptFSST is proposed as an optimized FSST variant that recovers these gains while preserving the static-symbol-table design and random-access decompression semantics. The work also extends the same techniques to FSST12, yielding OptFSST12.

The evaluation covers **92 real-world string datasets**. The headline numbers are:

- OptFSST improves the compression factor of FSST by **up to 47.7%**, with an **average improvement of 7.3%**.
- OptFSST12 improves the compression factor of FSST12 by **up to 91.5%**, with an **average improvement of 17.0%**.
- OptFSST12 additionally improves FSST12's **decompression speed by $1.2\times$ on average**.

All of these gains are achieved while retaining the fine-grained random-access properties of the original design. The compression-factor improvements are expressed relative to the baseline FSST/FSST12 factors, so a 91.5% improvement on a particular dataset corresponds to a substantially smaller compressed representation than FSST12 produces on that same dataset.