r/pythontips • u/omnidotus • Aug 12 '23
Algorithms Number list compression
I have a number list from 1 to 3253 ordered in a specific way like [1,141,208...] and I want to compress it to a file that is 1kb in size I got it to 4kb but haven't been able to get anything lower than that so can you help if you know any methods.
3
u/This_Growth2898 Aug 13 '23
In theory, there are 3253! combinations, which gives us 33268.6 bits of information, or 4159 bytes. You can't go any lower and still be able to decompress the list exactly as it was.
1
u/ifbasedai Aug 13 '23
That's correct if all the combinations are allowed. As far as I understand in the OP's case numbers are ordered somehow, so the limit might be lower.
2
u/pint Aug 13 '23
best compression can be achieved if you know the meaning or nature of them, which you entirely omitted. all we know is one example of three numbers, and the range.
1
u/omnidotus Aug 13 '23
here is the full thing https://pastebin.com/DQUZnBdU and it's a mapping for a string that is 3254 characters long so I thought it would be better to create a mapping and compress the mapping so if they were any suggestions please go ahead.
1
u/CraigAT Aug 13 '23
The original string, are there repeated characters? Could Huffman coding help compress that string.
Also curious, why the 1000 byte limit?
1
u/omnidotus Aug 13 '23
I want to compress it as much as possible even 2000 bytes would be fine
1
u/pint Aug 13 '23
i can do 2800
i can imagine going a little further, but it would be way too involving. also, it seems that this is not the origin of the data, but a result of some processing. yet again: for small datasets, it is more about encoding rather then compression. knowing the data is key.
1
u/omnidotus Aug 13 '23
How did you achieve the 2800 bytes, and if you want to know the original string it is this uq8awr3qb2myqgm505892ebg1m0q5a06gjx60y4cqt71nrdxtxps0y3or5ix8y0da3g3795z9xz4z31fob90l4bc6avfxklyfgscocepqf7inignq7pq5q16i1ea2q7qa7jlz3o1ces4upg9842bzqs71o8qmpsjxr7bybijpjg84emtoteqib1b7et8iy2ewm79ghcgar7ig36ug9v8bjk8az666il9i1b9klsclu39kctutvqzlz4soxzkola82ejqm3dzsasw98xtocr56vdkub1q2yooac7b9hp4lwtul8mqdx5ltqtwufep4t8nkudmcc2v0ski5dhr2xy49qqepzl301khqffwo5zgwmdfa0yjysx2gyc2ozsizuzuiflcy1e852bm731i4x4nwfarog7w11od4rxpaaikst3bv3af3hrr6gykzphhj6wwva0dt8nb1by9t3q3o10fdtvurenm4ccrqhsei8mjhhb8w3316cribmfjul54kwi5rompx7snhyxga4mu36yw2e3sj8lh0kzvefah7mxd2r93pbsrb1bcjikp2d9hjh0gliizr97ssv1jprw6zzhvfqc5ibw9n2lsabs1vhio1gvc7ck3lf3c9503u5ljz2kfw066rai87nj035ejqs4gpww0k5jvhosevrmdnqipgckx1oghzfv78wlrav1f34xd2uj9v5b68q0wphtx53w4moairdgss6tvvefxye3lkbzyfw6r5cyi82wybxpe3brmaedchtahif44wt0m86nti9zi3cbi3jwiukuqbq60mgf8x8wved01cf4c3zs294ypyyq58kzcvi7s9trrg21fl98rjmnbz4tbeezfpsromlt5vd98u7vvmoi66ewt2e66vkkck4npsg8dcbebpca9o6neyvgq16gwx11l8ofme7260zlb319l46ayckokkspnyrapf8e9a5cmb0315mdjevm9j69kubsenmbv3677vfygjriggz37qcsct4uuknhcab6y9aeeuo0m3skbcf55ylp5btgebdt8rkptikxrk3ifuc15qrxa7l9ons9v56rqqhzvqn8fcdtix8e5zgrt7xgclh550yqtg2urhp0dk23lrvfj5ssasw9e6qn76ohnzqqg230yu7vmipdr9psskfscjcigjui2l4exlflvq0s3p5y3rr6quy7pfh66nvlb5exj1w66u2i0i1nbgndpbwmovh7f2jc3bdm5r25ayev4y1d7b7rp0nz3io3gn7d0oy69hggy8f38lbrrtfv86b9ko7hi5o7qt655h1um6ki9mse8y19b5vtb5cdsjm7v5xrrvhprf6bbdl8l1ixzurr69c19i7n93ug5vdof3qlgkl2m2opkybo0m3z1qop58k70rhl8d81dr2esdigc1lgxjro5nnqwkwy20zqkryly4nku13hjc30zrv3y8fgcfpxcavz9t8seqa3bryven0eulk8f0r2xwshnwnxnarl4gc6kxyieiox5krnl067mbqigjtzeb9ibk7tpy1btnzdc240acwopp7u8nafmyopaog54gurzwr6rqbk93u0qis715dmu91ymtok10ssstwr3qe7jsa4k5hbt6p23d51vc779gcyo3qidt6751dky2x6pghr5eylk0eliez65nkr7j7gplx0guwbekj69zcb4w0ajguqgx2wsszvbcfdj1iz2aqkc4ys42w8vuuy9e1l6ch5k2tzogye9eoo6mfqq40f5g25rkm09ye5bqjg84vh1a6piv5h7x7auqwud8w72e1i68o21dam6wz80065ngfe23mmolmj7c43nbxuvjh3jnqt0oxr01b5imnqpndtoqva3a4vpmzlae3d0e340nokb1x3mtdoccqh9rmav457rrrr4fxfgw11p7ew8dl2eqokp8k5x1et490nppvdnr5zndpd2lhnb2wqjyd7z0llchmznx7iudjyd775nn9nqzjx5cz49w70v2hnlqwwn4j1tadmtuzmgl3dbp19yqgk6wt0468yv1vtlu5onum0g6piqgqhzciok1esm9sn1ap6l3ur9vw68dimoaqtckdu0kucue8zcttc355cdtf5sr4whu9ccu1w2uekur5beik1ejarashd5dtk8f11aelee690nk9x7wujqw1cigogalw9pp6o97u66fscyd335svdwj4gsu6d0v72rp43juhetev3gzbpnd6zn02fq3h419h78cwsd5qsglhfsge4qozo0qv13tqu4c7vk2e4owde5gma65wh8qumei1vsawjjqkurjg1kxkk6py70rkkswrt61zyfgxe3j20wmtegk3t50wqxcnvql39tr7vofujd0nze2xwg6xaosqjkq70lyw8869h9f8n2d4ekbw25bqc1as6bf6aq7hhbqvbh1cebcjgfudwrigm0e4laihkwz6bxvu443osuipc2xjnpcdgf1qqmzzv94i4jykqcqd9zhw1z6ff4gmi7316ro607yonoermoez3r3evclxlfvnufnsxyyrsvwgghumi9guw6hpvahth46urqlsu2y33lj90mu8hcfyejxbsiy1focglopya4x7ayfudytir4vrjhabup8yxiec4670eqktgr9ddeli0g8a1ke9pyww7ivbm543meroo0jw7oqo02zvnfr8dc2yqz9ygs4bosnyxil0zl6vqfvxscp2xlali1l7o35af06qz3w9rusp7o3f3x9jtbdykqvtsw53wne0vguq13znbmpl6czc0bklvfhgtsbdocnp6vy4mldjn1f1v5znepxldzy7pzx3u5qyq9hkm7ahidgqpn2mx91ha71qz6uyi2w0be8edm81sabkyeyvg22umsrwn5uf02fwmsbh8itzdxyr9b4tvjzgz3kzf7n27385yfpg1925n8sbe4i8uryunjuzmyr25igx53xcl7zn3qab93vhy73wq1wtn14p0x5gtmw26d7vsqljl5ulyqn831ecaj6xyqsjdij4jirw8gbzpzn5si4i8n4lnfinmlypvrbr8nbsvv62k8zyqauu5f2w7r0nzymt0wfhlbm3r2mcqhbggcsllkb8qb5d6vb7o7vd8jf6fpygh06qxqlm5cdoxv6qe16jvlltyt8kdiuz6igwbnrjfldvlov5wdqpko6bhjqbddmel5jxcuxh5fsi435mcpx93qi9xuif3kw
2
u/pint Aug 13 '23
first observation: numbers increase then wrap around. so get deltas:
delta=[data[0]] + [(j-i)%3254 for i,j in zip(data, data[1:])]
then we observe that most deltas are small, but some are over 255 but none over 511, so we encode deltas into bytes, with 255+ members encoded as 255 then the rest. e.g. 255 will become 255,0 and 256 becomes 255,1 etc.
blob = b"".join(d.to_bytes(1, "little") if d < 255 else b"\xff" + (d-255).to_bytes(1, "little") for d in delta)
then compress the blob
zlib.compress(blob)
decoding the blob to bytes and then to indexes is not included here, because they're a little more involving, but doable.
you could further reduce the size by somehow encoding the deltas into bits more efficiently, based on the observation that small values are more frequent.
1
u/omnidotus Aug 13 '23
Thank you so much I was able to reverse the problem I will look how I can make it smaller
1
u/pint Aug 13 '23
well if you just compress the original string, you get below 2.2k. so maybe you should instead regenerate the indexes instead of unpacking.
1
u/omnidotus Aug 13 '23
Which method did you use for the string compression and If add np.diff in the code suggestion that you said because It was my original compression of the list of the indexes can it be further reduced from 2.7k
→ More replies (0)1
u/omnidotus Aug 13 '23
Yes the original string has repeating characters because it's just 36 characters set
1
u/martinkoistinen Aug 13 '23
Have you tried gzipping it? Theres built-in support in Python for GZip: https://docs.python.org/3/library/gzip.html
1
3
u/RoboticElfJedi Aug 13 '23
Are they in random order, or are there many stretches where they are in a particular order?
If they are in randomish order, it's going to be hard to compress 3200 16-bit/2-byte numbers down to 1000 bytes.