3 ms·
I haven't done any noodling with compression in some time and I'm tempted to sit down and try this. But I think he must be using a different list than I can fin
by hinkley 5y ago
I haven't done any noodling with compression in some time and I'm tempted to sit down and try this. But I think he must be using a different list than I can find because the numbers don't quite add up.
Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking.
I will say that given that a delta encoding was settled on, bitpacking the words first is probably a mistake, and multiplication should have been used instead. For instance using multiplication you can store the words in 24 bits without chopping off the first character and using pointers to them. That may seem a small difference but it makes the deltas he's looking at narrower. So instead of choosing 8 words in 8 bytes versus 10 words in 8 bytes, it could be 8 vs 11, possibly 12.
- hinkley 5y agoIt looks like the reliance on 5 bits per character versus using 26*5 is that a lot more of his deltas get an extra character. He is encoding 7 bits per byte, so there are about 172 words that spill over into the next byte due to this. With 5 bits per letter, if the second to last character shifts by more than 4, then it automatically spills over. With 26, it also depends on how much the last letter also varies.