Skip to content

feat: dictionary builder — FastCOVER algorithm and dictionary finalization #25

Description

@polaz

Summary

The current dict_builder feature implements the COVER algorithm but lacks the FastCOVER variant and dictionary finalization (adding zstd header with entropy tables).

C reference implementation (lib/dictBuilder/)

FastCOVER (fastcover.c)

  • Faster alternative to COVER using frequency array instead of suffix array
  • Parameter f: frequency array size (0 < f ≤ 31)
  • Parameter accel: acceleration factor (1-10, higher = faster, less accurate)
  • Same output quality for ~10x less computation

Dictionary finalization (zdict.c)

  • ZDICT_finalizeDictionary() — adds zstd header to raw content dictionary
  • Header contains: magic number, Huffman table, FSE tables, offset history
  • Result: full zstd dictionary format that enables entropy table sharing

Optimization functions

  • ZDICT_optimizeTrainFromBuffer_cover() — grid search over k,d parameters
  • ZDICT_optimizeTrainFromBuffer_fastCover() — same for FastCOVER
  • Multi-threaded optimization via nbThreads parameter

Current Rust state

  • dictionary/cover.rs — COVER algorithm implemented
  • dictionary/frequency.rs and reservoir.rs — supporting structures
  • No FastCOVER variant
  • No dictionary finalization (only raw content output)
  • No parameter optimization

What needs to be implemented

  1. FastCOVER algorithm — frequency-based alternative to COVER
  2. Dictionary finalization — add zstd header (magic + entropy tables + content)
  3. Parameter optimization — grid search over k,d,f parameters
  4. Configurable parameters — expose k, d, f, accel, splitPoint

Acceptance criteria

  • FastCOVER produces dictionaries matching C quality
  • Finalized dictionaries usable by C zstd for decompression
  • Parameter optimization finds good k,d values automatically
  • Performance: FastCOVER ≥5x faster than COVER

Time estimate

3d

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    P2-mediumMedium priority — important improvementenhancementNew feature or requestperformancePerformance optimization

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions