3 ms·

I'm looking at different ways to compress a list of integers, came across [0] and this seems to work best [1] for small ints that I'm working with. [0] https:/

I'm looking at different ways to compress a list of integers, came across [0] and this seems to work best [1] for small ints that I'm working with. [0] https://github.com/invertedtomato/integer-compression https://github.com/invertedtomato/integer-compression [1] https://raw.githubusercontent.com/invertedtomato/integer-compression/master/images/comparison-1.png https://raw.githubusercontent.com/invertedtomato/integer-com...

user-the-name 5y ago
You can improve on this by quite a bit by not writing literal bits to the file, but instead feeding them through an arithmetic or range coder, with some reasonable statistical model. The statistical model can be very simple, even just an exponential moving average per digit will help.
- cinquemb 5y ago
  Yeah, it seems like going with some of solutions listed here[0][1] work pretty well after passing the binary through (better when not passing through fib coding, but mapping most of the ints to characters and compressing them). Still trying to explore though. [0] https://en.wikipedia.org/wiki/Dynamic_Markov_compression https://en.wikipedia.org/wiki/Dynamic_Markov_compression [1] http://mattmahoney.net/dc/text.html#1263 http://mattmahoney.net/dc/text.html#1263
  - user-the-name 5y ago
    No, just keep the fibonacci coding, or whatever code, just feed to output bits from that coder through a simple statistical model and then into a range coder. Here's how LZMA does it, for instance: https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algorithm#Range_coding_of_bits https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algori...
    - cinquemb 5y ago
      Ok I think I misunderstood you if passing it through something like DMC is not what you mean. So I have some fibonacci encoded binary blob[0] (uint8_t for each byte), is there some kind of pseudocode example you could share of how I would pass each bit from the file through the a statistical model (like for exponential moving average, I'm not sure what to do with each bit I iterate over or how to store it after it would pass through from what you are trying to explain to me)? [0] https://gist.github.com/cinquemb/94168c02da2a30b269cc5baef8ca87d5 https://gist.github.com/cinquemb/94168c02da2a30b269cc5baef8c...
      - user-the-name 5y ago
        You should do it all in one go while processing the data, because you want to use the context you have during the encoding process to build your statistical model. The simplest version is, keep an array of exponential moving averages of the bit value for digits 1...N of each code, and use those as the probabilities for the range coder.
        cinquemb 5y ago
        Ok, so as I iterate over the data and generate an fibonacci code, i: - compute the ema for each code - store the ema by mapping that code to a given ema value at the step during iteration - encode that code to the file based on the algo here [0] How much more efficient at compression would this be by actually getting the probabilities first rather than updating it on the fly (one full iteration over the non fibonacci codes to compute the exact probability, then again for actually passing it thru the range coder)? Or is this something that i'll just have to play around with? [0] https://en.wikipedia.org/wiki/Range_encoding#Example https://en.wikipedia.org/wiki/Range_encoding#Example
        user-the-name 5y ago
        It is the EMA for each digit, rather than each code. So you have one EMA for all the first digits of all the codes, one for all the second digits, and so on. You can then make it more intelligent by having even more different EMAs and picking between them in some more intelligent way than just by digit. By digit is just the easiest option. Precalculating the probabilities may or may not be more efficient. You lose a tiny bit of efficiency because you have to include the probabilities at the start of the file rather than being able to re-calculate them when decompressing, but if they are very static you may gain a bit of efficiency. However, if the probabilities change throughout the file, the dynamic version again gains the upper hand since it can adapt to changing data. How quickly you let the EMA change also affects this.

user-the-name 5y ago

You can improve on this by quite a bit by not writing literal bits to the file, but instead feeding them through an arithmetic or range coder, with some reasonable statistical model. The statistical model can be very simple, even just an exponential moving average per digit will help.

cinquemb 5y ago
Yeah, it seems like going with some of solutions listed here[0][1] work pretty well after passing the binary through (better when not passing through fib coding, but mapping most of the ints to characters and compressing them). Still trying to explore though. [0] https://en.wikipedia.org/wiki/Dynamic_Markov_compression https://en.wikipedia.org/wiki/Dynamic_Markov_compression [1] http://mattmahoney.net/dc/text.html#1263 http://mattmahoney.net/dc/text.html#1263
- user-the-name 5y ago
  No, just keep the fibonacci coding, or whatever code, just feed to output bits from that coder through a simple statistical model and then into a range coder. Here's how LZMA does it, for instance: https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algorithm#Range_coding_of_bits https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algori...
  - cinquemb 5y ago
    Ok I think I misunderstood you if passing it through something like DMC is not what you mean. So I have some fibonacci encoded binary blob[0] (uint8_t for each byte), is there some kind of pseudocode example you could share of how I would pass each bit from the file through the a statistical model (like for exponential moving average, I'm not sure what to do with each bit I iterate over or how to store it after it would pass through from what you are trying to explain to me)? [0] https://gist.github.com/cinquemb/94168c02da2a30b269cc5baef8ca87d5 https://gist.github.com/cinquemb/94168c02da2a30b269cc5baef8c...
    - user-the-name 5y ago
      You should do it all in one go while processing the data, because you want to use the context you have during the encoding process to build your statistical model. The simplest version is, keep an array of exponential moving averages of the bit value for digits 1...N of each code, and use those as the probabilities for the range coder.
      - cinquemb 5y ago
        Ok, so as I iterate over the data and generate an fibonacci code, i: - compute the ema for each code - store the ema by mapping that code to a given ema value at the step during iteration - encode that code to the file based on the algo here [0] How much more efficient at compression would this be by actually getting the probabilities first rather than updating it on the fly (one full iteration over the non fibonacci codes to compute the exact probability, then again for actually passing it thru the range coder)? Or is this something that i'll just have to play around with? [0] https://en.wikipedia.org/wiki/Range_encoding#Example https://en.wikipedia.org/wiki/Range_encoding#Example
        user-the-name 5y ago
        It is the EMA for each digit, rather than each code. So you have one EMA for all the first digits of all the codes, one for all the second digits, and so on. You can then make it more intelligent by having even more different EMAs and picking between them in some more intelligent way than just by digit. By digit is just the easiest option. Precalculating the probabilities may or may not be more efficient. You lose a tiny bit of efficiency because you have to include the probabilities at the start of the file rather than being able to re-calculate them when decompressing, but if they are very static you may gain a bit of efficiency. However, if the probabilities change throughout the file, the dynamic version again gains the upper hand since it can adapt to changing data. How quickly you let the EMA change also affects this.