peter-ebert

7 ms·

1.
by peter-ebert 2y ago
I've added basic bit packing to the frequencies table, so long as the dictionary doesn't dominate like in a pangram it's slightly smaller than two arithmetic (static and adaptive) examples I could find online. I understand th
2.
by peter-ebert 2y ago
Thanks I'll work on that. One thing though > The linked example can encode _any sequence_, not just ones that have an equal number of ones and zeros. The compression I made can also encode any sequence of bytes, see the testinput fo
3.
by peter-ebert 2y ago
Sure thing! Does this meet your requirements? https://github.com/nayuki/Reference-arithmetic-coding/blob/m... If not could you link one that does? If I implement my own I expect someone to say I did it wrong.
4.
by peter-ebert 2y ago
*I mean input2, sorry long day.
5.
by peter-ebert 2y ago
This arithmetic compression example simply stores the 4 byte values of the frequencies (I used 8 bytes) in a flat table https://github.com/nayuki/Reference-arithmetic-coding/blob/m... For input3 they used 20
6.
by peter-ebert 2y ago
When I get time may compress the table as well then, in looking at example arithmetic encoders they seem to have some flat table implementations as well ( https://github.com/nayuki/Reference-arithmetic-coding/blob&#
7.
by peter-ebert 2y ago
I appreciate the input. I did not mean to imply I could encode a random stream of symbols/characters, that is absolutely valid. I was approaching this as a compression technique for something like a text file, where the symbol counts
8.
by peter-ebert 2y ago
fwiw I was using the same math they did here to get 4.755 bits: https://en.wikipedia.org/wiki/Arithmetic_coding#Sources_of_i... [-(1/3)log2(1/3)-(1/3)log2(1/3)-(1/3)log2(1/3)]*3=4.7548
9.
by peter-ebert 2y ago
Thanks I'll correct, I didn't know you could adjust the symbols as you go with arithmetic coding, got an example of that?
10.
by peter-ebert 2y ago
I was using what I seemed to be the standard with other encoders, storing the ratios is roughly the same cost compared to other compressors, a few extra bits for exact counts. But I do see how this isn't i.i.d. so I'm fixing that
11.
by peter-ebert 2y ago
Got it, I was thinking of the locations as being i.i.d. in that you do not have any information on their location. You and others are saying that adjusting the symbol counts as you go would give the same performance to other algorithms. L
12.
by peter-ebert 2y ago
thanks for the constructive feedback!
13.
by peter-ebert 2y ago
Whenever you're compressing a file on your computer the frequencies are known beforehand. Agree this does not apply to noisy-channel coding, only the Shannon source coding theorem in lossless compression. Good point though I'm n
14.
by peter-ebert 2y ago
ANS requires 1 bit per symbol if the ratio is 1:1, you can confirm this here: https://kedartatwawadi.github.io/post--ANS/
15.
by peter-ebert 2y ago
Yeah this was a big fear in posting. No I'm not experienced in academia or this would be a paper, I code things for fun. Have you tried looking at the math for multinomials vs Shannon? Or running the code? Please do point out my mis
16.
by peter-ebert 2y ago
Here's a simpler example, 2 symbols 1:1 ratio, Shannon would say the entropy is 1 bit per symbol, so this needs 2 bits: 01 or 10 encode both permutations. However I can also just store 1 or 0 to indicate what's stored in the first
17.
by peter-ebert 2y ago
As far as I can tell the symbol counts are not included when measuring the size of the output, I did say that but there is a lot of text :) Huffman, ANS, arithmetic coding, etc do not include the frequency counts as part of the size afaik,
18.
A (hopefully) new compression algorithm that uses binomials(github.com)
29 points by peter-ebert 2y ago|55 comments
19.
by peter-ebert 2y ago
I was initially surprised to find that the size of multinomials is less than the entropy predicted by the Shannon source coding theorem, which is generally accepted as a lower bound. Not sure if this encoder is new, but hopefully others fi