4 ms·

I was thinking the same myself - couldn't it work just as well on a random byte stream by just passing in every 4 bytes as a 32-bit integer?

by damian2000 13y ago

recursive 13y ago
No. There is no general purpose compression that works on random byte streams.
DannyBee 13y ago
No, because everything would be an outlier, so it would save nothing. Here is a basic explanation (there are niggly little details i'm not going to go over, since the papers do a better job) The way FOR (i'll get to PFORDELTA in a sec) codecs work is by taking numbers say 128 at a time, finding the max number of bits necessary (so if all numbers are between 0 and 32, it would be 5), and then encoding them as 5 bit numbers FOR has the problem that if you have a list of numbers like 1 2 2 2 3 728 3 2 1, the 728 screws you. PFORDELTA instead finds the number of bits it takes to represent, say, 90% percent of the numbers (IE it finds the b such that 90% of numbers are < 2^b), encodes those numbers in fixed size blocks of b bits, and along the way, "patches" out the 10% of outliers, and encodes them at the end. It is normally used on posting lists. In a sufficiently large random byte stream, for random 4 byte streams, either b == 32 all the time, or over time, the outliers will take more space than you save elsewhere. (where the amount of "more space" will be whatever the control overhead of the outlier encoding is). So you will either save nothing, or grow in size. This is guaranteed by the pigeonhole principle.
- damian2000 13y ago
  Thanks for the explanation
- ygra 13y ago
  From what you're writing it seems like this might work for bytes when you treat them as such and not group four of them together as integers. Especially text probably has pretty much the same patterns (lots of code points in a range [lower-case letters] with a few outliers [upper-case letters and spaces]). But then again, for text there probably are much better-suited alforithms.
  - gizmo686 13y ago
    For text, you would probably want an encoding hard coded into the algorithm. Because (in a given language) the distribution of characters is relativly consistent, you do not loose much by deciding which characters only need 2 bits and which ones need 10; and you save on having to put this information in the compressed data. But you are right that their are far better algorithms for text compression (although if doing this character re-encoding makes sense, I would imagine most implementations include it along with the main algorithm, and several other bonus compression algorithms).

I was thinking the same myself - couldn't it work just as well on a random byte stream by just passing in every 4 bytes as a 32-bit integer?

recursive 13y ago

No. There is no general purpose compression that works on random byte streams.

DannyBee 13y ago

No, because everything would be an outlier, so it would save nothing. Here is a basic explanation (there are niggly little details i'm not going to go over, since the papers do a better job) The way FOR (i'll get to PFORDELTA in a sec) codecs work is by taking numbers say 128 at a time, finding the max number of bits necessary (so if all numbers are between 0 and 32, it would be 5), and then encoding them as 5 bit numbers FOR has the problem that if you have a list of numbers like 1 2 2 2 3 728 3 2 1, the 728 screws you. PFORDELTA instead finds the number of bits it takes to represent, say, 90% percent of the numbers (IE it finds the b such that 90% of numbers are < 2^b), encodes those numbers in fixed size blocks of b bits, and along the way, "patches" out the 10% of outliers, and encodes them at the end. It is normally used on posting lists. In a sufficiently large random byte stream, for random 4 byte streams, either b == 32 all the time, or over time, the outliers will take more space than you save elsewhere. (where the amount of "more space" will be whatever the control overhead of the outlier encoding is). So you will either save nothing, or grow in size. This is guaranteed by the pigeonhole principle.

damian2000 13y ago
Thanks for the explanation
ygra 13y ago
From what you're writing it seems like this might work for bytes when you treat them as such and not group four of them together as integers. Especially text probably has pretty much the same patterns (lots of code points in a range [lower-case letters] with a few outliers [upper-case letters and spaces]). But then again, for text there probably are much better-suited alforithms.
- gizmo686 13y ago
  For text, you would probably want an encoding hard coded into the algorithm. Because (in a given language) the distribution of characters is relativly consistent, you do not loose much by deciding which characters only need 2 bits and which ones need 10; and you save on having to put this information in the compressed data. But you are right that their are far better algorithms for text compression (although if doing this character re-encoding makes sense, I would imagine most implementations include it along with the main algorithm, and several other bonus compression algorithms).