4 ms·

Not sure I understand here - how would (1,1,0,3) disambiguate between different streams of data with bit lengths of (1,2,4,4,4) and (1,4,2,4,4)?

• Dylan16807 6y ago
  If you're sending just the counts then that would be in addition to an ordered list of symbols.
  • twic 6y ago
    It's so odd that this crucial detail is always omitted from this explanation. If you're encoding a byte stream, the receiver already knows what the set of symbols is, although not the order. Is it really more efficient to send the ordered list of symbols plus the histogram of code lengths than it is to send a length per symbol, with an implicit list of symbols? Surely not.
    • jackcviers3 6y ago
      As long as the list of symbols is small then yes, because the symbols are a subset of the entire character list. I imagine some implementations basex encode the bytestring first then indicate the original and basex encoding instead of sending the symbol list.
    • Dylan16807 6y ago
      Like most things in compression, it depends. But DEFLATE sends the list of 288 code lengths, with all the symbols being implicit. It also compresses that list with another layer of repetition encoding and huffman encoding. For example, if you were encoding DEFLATE's default huffman table, you would first write it like (8, repeat 143, 9, repeat 111, 7, repeat 23, 8, repeat 7), and then you would compress that with a separate tiny huffman table. The tiny huffman used on code lengths is itself encoded as a series of 3 bit code lengths, taking up 5-ish bytes, with the order of symbols predefined in the spec.