5 ms·
In what way is compressing an array of integers "less general" than a general compression algorithm? Is that not exactly what a normal compression algorithm doe
by andrewflnr 13y ago
In what way is compressing an array of integers "less general" than a general compression algorithm? Is that not exactly what a normal compression algorithm does, or at least can be construed as doing, with, say, 8-bit integers?
- damian2000 13y agoI 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 agoNo. There is no general purpose compression that works on random byte streams.
- DannyBee 13y agoNo, 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 agoThanks for the explanation
- ygra 13y agoFrom 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 agoFor 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).
- ars 13y agoSee: http://lemire.me/blog/archives/2012/02/08/effective-compression-using-frame-of-reference-and-delta-coding/ http://lemire.me/blog/archives/2012/02/08/effective-compress... You can use it for text but it won't work as well. It's designed for numbers that are created by some kind of real process. It compresses by looking for the largest and smallest number and only storing the difference from the smallest number, and only as many bits as needed for the largest. (Good for situations where most of your data lies inside a range.) It stores the difference between successive numbers. (Good for measuring a process that varies slowly.) Also see: http://en.wikipedia.org/wiki/Golomb_coding http://en.wikipedia.org/wiki/Golomb_coding which works on the principle that small numbers show up more than large. None of that makes sense for text which doesn't have those patterns.
- skyebook 13y agoThanks for the explanation, definitely an interesting routine and the performance numbers he touts in the blog post make it something I'd definitely look to test on my own
- gwern 13y agoYou should probably read the original research paper if you're curious: http://arxiv.org/abs/1209.2137 http://arxiv.org/abs/1209.2137
- kkowalczyk 13y agoOne difference is API e.g. for compressing an array of integers in Java, you say int[] compress(int[] toCompress) i.e. it natively works or Java's int[]. While it's true that the layout of data in memory could be re-interpreted as a byte array, you avoid cumbersome casting (which, by itself, might incur cost in languages like Java where you can't just party on memory via pointers). Another difference is that a custom algorithm for compressing integers might gain speed/compression efficiency from exploiting statistical properties of integers e.g. it's a safe bet that in most cases the highest byte of an int is 0 (i.e. integers are are small). Or in many cases a delta encoding is very effective (i.e. {5, 10, 15} => {5, 5, 5} which is easily encoded with run-length encoding). Of course if integers are randomly and uniformly distributed they are just as un-compressible as random, uniform distribution of bytes, but in many real-life uses of integer arrays that is not true.