Looking for a Math Genius...?

Question

I have an input byte stream consisting of numbers in the set {0 - 15} exclusively of about 1000 bytes.

What I would like to do is to be able to somehow store that mathematically in ONE unsigned integer and then, having in hand the the last byte value that was "encoded" into that unsigned integer, mathematically reverse it back to the original byte stream.

I am hoping there is a way to mathematically encode the values into an integer and then decoding them back.

Do you know how?

Answer 1

You have 1000 numbers between 0-15 (4-bits). So that is 4000 bits of information. And you want to compress that to an unsigned integer. Unless your system allows you to use 500 bytes for unsigned integers, there is no way to do it!

If you are allowed to use 500 bytes, then you could pack it with two 4-bit nibbles per byte. Otherwise it isn't possible without losing information.

Let's say it was possible to get your information encoded into a single unsigned integer (e.g. 32 bits)... that one integer would have to represent any possible input of 4000 bits... do you see how there aren't enough bits to represent all the possible combinations of 4000 bits?

The only other way would be if you were allowed to use a very, very large look-up dictionary of some sort, or if you knew some information about the pattern of numbers. For example, if you didn't need to know the exact order of numbers and just needed a count of each digit 0-15, then you could compress more.

But with just a raw sequence of 1000 numbers, there is no way to get it down to a single unsigned integer (unless that int is really big).

However, assuming that you did have a 500 byte unsigned integer... you would just do the following:
1) Set the number = 0
2) Multiply the number by 16:
3) Add the next number in the set:
4) While you still have input, go to step 2.

Answer 2

It takes 4 bits to encode an integer in the range 0-15, so you could encode any such stream of 1000 bytes into a single 4000-bit unsigned integer, and nothing less. There is no compression scheme which could guarantee that the compressed result would be smaller than the input.

If you wanted to retrieve a stream based only on the last byte, you would need to require that the last byte be unique, you could store at most 16 such streams, and you could do that in a single 64,000-bit unsigned integer.

I hope I didn't do your homework for you.

Answer 3

I don't think it's possible since you need 4 bits per byte (2^4 = 16) to encode the input byte string.

4 bits/byte *1000 bytes = 4000 bits which exceeds the bit capacity of an unsigned integer by a long shot. For example, unsigned integers in the version of Java linked below only have 31 bits.

Answer 4

The easiest way to do it is to pack two of the numbers into a single byte, so about 500 total bytes would be required. That string of bytes comprises an integer (of about 1500 digits), and hopefully you would not need to do anything with that number except to store it. The nice thing about this packing scheme is that to do the packing and unpacking is trivial.