feat: optimal parsing compression (btopt/btultra/btultra2 strategies)

[polaz]

Summary

The highest compression ratios in zstd come from optimal parsing strategies (levels 16-22). These use price-based optimal parsing with binary trees — Dijkstra-style shortest path through a match/literal graph.

C reference implementation (zstd_opt.c)

Algorithm

1. Build match graph — at each position, find all possible matches (btree) and literals
2. Price calculation — each edge (match or literal) has a bit cost based on entropy statistics
3. Optimal path — find minimum-cost path through the graph (dynamic programming)
4. Adaptive statistics — frequency tables updated as encoding progresses

Key structures

• optState_t: Frequency tables, match storage, price cache
• ZSTD_optimal_t: Per-position state (price, offset, match_len, literal_len)
• BITCOST_MULTIPLIER = 256: Fractional bit precision (fixed-point)

Strategies

• btopt (levels 16-17): Optimal parsing with moderate search depth
• btultra (levels 18-19): Full search, larger match graph
• btultra2 (levels 20-22): Ultra with additional second pass for parameter tuning

What needs to be implemented

1. Price calculation — fixed-point bit cost based on symbol frequency
2. Match graph construction — all matches at each position via binary tree
3. Dynamic programming solver — minimum cost path selection
4. Adaptive statistics — rescale frequency tables to prevent overflow
5. btopt/btultra/btultra2 variants — different search depths and pass counts

Acceptance criteria

• Levels 16-22 produce valid, decompressible output
• Compression ratio within 5% of C zstd at same level
• Interop: C zstd decompresses output correctly

Dependencies

• feat: implement Best compression level (zstd level 11, btlazy2 strategy) #7 (Best/btlazy2) — binary tree infrastructure
• feat: numeric compression levels (1-22) API #21 (Numeric levels) — level API

Time estimate

5d

Blocked by

• feat: implement Best compression level (zstd level 11, btlazy2 strategy) #7 (Best level — binary tree infrastructure)
• feat: numeric compression levels (1-22) API #21 (Numeric levels API — level mapping)