4 ms·

You don't need to. You compute a static huffman tree over fixed probabilities you've estimated or generated from a corpus.

• chaokunyang 2y ago
  Good suggestion, I was planing it as an optional option. We can crawl some github repos, and extract most types, extract their class names, paths, fields names, and use such data as the corpus
  • ryan-c 2y ago
    Crude static Huffman example, that could definitely be improved: 5 bits 0 0000-1111 acde fghi lmno rstu 7 bits 10 00000-11111 bjkp qvwx yzAB CDEF GHIK LMNO PRST UVWY 7 bits 110 0000-1111 JQXZ 0123 4567 89/. 8 bits 111 00000-11110 !@#$ $%^& *()_ {}[] `~+= |\"' ;:<> ,? (space at the end) 16 bits 11111111 00000000-11111111 plus UTF-8 1 to 256 unicode characters encoded as UTF-8 You could even include some bigrams in this sort of table. There's some code here that could maybe be used for that sort of static huffman tree: https://github.com/ryancdotorg/lztp/blob/main/generate-seed.js https://github.com/ryancdotorg/lztp/blob/main/generate-seed.... Alternatively, have something like this: 00 000000-111111 1-64 characters, 5 bits each 01 000000-111111 1-64 characters, 6 bits each 10 000000-111111 1-64 characters, ~6.4 bits each (character set of 84 characters, every 5 packed into 32 bits) 11 000000-111111 1-64 characters, UTF-8 This is vaguely similar to how data is encoded for QR codes. As pointed out elsewhere, this will not outperform zstd with a dictionary trained on a corpus, but zstd would require pulling in a lot of code.
    • masklinn 2y ago
      > This is vaguely similar to how data is encoded for QR codes. Doesn't QR use variable static encodings (alphabets)? e.g. mode 1 is numerics, mode 2 is uppercase alphanumeric, mode 3 is binary, and mode 4 is jis (japanese).
      • ryan-c 2y ago
        QR codes use a series of (mode, length, characters) segments - a given code can switch between modes. I think for QR codes the length encoding is mode-specific.
  • deleted 2y ago
    [deleted]