5 ms·

I found out the other day that zstd supports dictionary compression [0]. It's a pretty neat concept: you can "train" a dictionary on your corpus of text, and us

by salamo 2y ago

I found out the other day that zstd supports dictionary compression [0]. It's a pretty neat concept: you can "train" a dictionary on your corpus of text, and use this dictionary to compress subsequent documents. This is really useful if you have a lot of small documents with a similar distribution of characters. You only have to transmit the dictionary once over the wire once, and then clients can get great compression ratios after that. For example, suppose you have a lot of chess PGNs you'd like to store [1]. If you compress each PGN separately, you won't get nearly as high of a compression ratio as if you stored them all in the same file and compressed that file. But storing games individually is more convenient. Here are the numbers: Original PGN file: 780 bytes Default zstd compression: 508 bytes (35% decrease) With dictionary: 376 bytes (52% decrease) I'm thinking about ways to compress at an even higher ratio. Chess PGNs are a great candidate for this task because they have a huge amount of redundant and repeated text. [0] https://news.ycombinator.com/item?id=35917279 https://news.ycombinator.com/item?id=35917279 [1] https://en.wikipedia.org/wiki/Portable_Game_Notation https://en.wikipedia.org/wiki/Portable_Game_Notation

kevingadd 2y ago
The shared dictionary technique you describe is presently used for modern versions of HTTPS and for Brotli, IIRC. Very effective.
- follower 2y ago
  ...though with the slightly unexpected side effect (for Brotli, at least) that your executable may end up containing (~200KB, from memory) of very unexpected[-1] plain text strings which might (& has[0]) lead to questions from software end-users asking why your software contains "random"[1] text (including potentially "culturally sensitive" words/phrases related to religion such as "Holy Roman Emperor", "Muslims", "dollars", "emacs"[2] or similar). (I encountered this aspect while investigating potential size optimization opportunities for the Godot game engine's web/WASM builds--though presumably the Brotli dictionary compresses well if the transfer encoding is... Brotli. :D ) ---- footnotes ---- [-1] An aspect also previously mentioned on HN: https://news.ycombinator.com/item?id=27160590 https://news.ycombinator.com/item?id=27160590 [0] "This needs to be reviewed immediately #876": https://github.com/google/brotli/issues/876 https://github.com/google/brotli/issues/876 [1] Which, regardless of meaning, certainly bears similarities to the type of "unexpected weird text" commonly/normally associated with spam, malware, LLMs and other entities of ill repute. [2] The final example may not actually be factual. :)
  - RicoElectrico 2y ago
    Just XOR it with 0x55 ;)
    - follower 2y ago
      "Pros always use this one weird trick Brotli compression hates." :)
kjhcvkek77 2y ago
Lichess is open source and has a very clever custom pgn compression. They analyze the chess position and use various features to determine how likely various moves are, then use that distribution to encode the move.

by salamo 2y ago

kevingadd 2y ago

The shared dictionary technique you describe is presently used for modern versions of HTTPS and for Brotli, IIRC. Very effective.

follower 2y ago
...though with the slightly unexpected side effect (for Brotli, at least) that your executable may end up containing (~200KB, from memory) of very unexpected[-1] plain text strings which might (& has[0]) lead to questions from software end-users asking why your software contains "random"[1] text (including potentially "culturally sensitive" words/phrases related to religion such as "Holy Roman Emperor", "Muslims", "dollars", "emacs"[2] or similar). (I encountered this aspect while investigating potential size optimization opportunities for the Godot game engine's web/WASM builds--though presumably the Brotli dictionary compresses well if the transfer encoding is... Brotli. :D ) ---- footnotes ---- [-1] An aspect also previously mentioned on HN: https://news.ycombinator.com/item?id=27160590 https://news.ycombinator.com/item?id=27160590 [0] "This needs to be reviewed immediately #876": https://github.com/google/brotli/issues/876 https://github.com/google/brotli/issues/876 [1] Which, regardless of meaning, certainly bears similarities to the type of "unexpected weird text" commonly/normally associated with spam, malware, LLMs and other entities of ill repute. [2] The final example may not actually be factual. :)
- RicoElectrico 2y ago
  Just XOR it with 0x55 ;)
  - follower 2y ago
    "Pros always use this one weird trick Brotli compression hates." :)

kjhcvkek77 2y ago

Lichess is open source and has a very clever custom pgn compression. They analyze the chess position and use various features to determine how likely various moves are, then use that distribution to encode the move.