3 ms·

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

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.
    - cinquemb 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. Ok cool, so if I'm using uint8_t, ill have an ema for each of the 8 bits. And yeah, I'll start with the easiet just so I can nail the implementation then try playing around with different emas if i'm not satisfied with it (right now I can turn 29kb to 5kb with paq8fthis2 compared to 12kb with snappy, so hopefully using something like this will make it go lower). > 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. Yeah, I suspect this to likely be true. I'll need to probably play around with the ema weights to see how that will change things. Thanks for helping me understand this all! I started out trying to compress the data by representing as a matrix with fewer # row operations to get back to the original, then ended up having to deal with it traditionally… lol

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.
  - cinquemb 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. Ok cool, so if I'm using uint8_t, ill have an ema for each of the 8 bits. And yeah, I'll start with the easiet just so I can nail the implementation then try playing around with different emas if i'm not satisfied with it (right now I can turn 29kb to 5kb with paq8fthis2 compared to 12kb with snappy, so hopefully using something like this will make it go lower). > 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. Yeah, I suspect this to likely be true. I'll need to probably play around with the ema weights to see how that will change things. Thanks for helping me understand this all! I started out trying to compress the data by representing as a matrix with fewer # row operations to get back to the original, then ended up having to deal with it traditionally… lol