4 ms·
I know how it works. Like I said, I don't know the motivation for why that is the best way to connect LZ and Huffman coding together.
by edflsafoiewq 3y ago
I know how it works. Like I said, I don't know the motivation for why that is the best way to connect LZ and Huffman coding together.
- lifthrasiir 3y agoI should note that it's hardly the best way, but it's easier to think DEFLATE as a layered algorithm: you catch repetitions via LZSS and code the remaining information with Huffman. You have two kinds of code because they have a very different distribution so it's beneficial to split them (and it's not surprising to have tens or hundreds of distributions in more sophiscated formats). And extra bits are there because longer distances in LZSS are typically opportunistic so individual values have a low frequency (i.e. Zipfian). So exact distance 1280 and 1281 can appear only once, but maybe distances 1200--1299 appear frequently enough that you can have a distinct code for that plus two-digit adjustments. There are much more other ways to model distance distributions; for example, a set of codes for most recently used distances is common but DEFLATE is too old for that.