Java algorithm to Compress small numeric number

Question

I need to compress 20-40 char size of a numeric number to a 6 char size number. So far I have tried Huffman and some Zip algorithms but not getting the desired outcome.

Can some one please advise any other Algorithm/API for this work in Java?

Example:

Input: 98765432101234567890
Desired Output: 123456

Please note: I didn't mean the output has to come as 12345 for the given input. I only mean that if I specify 20 byte number, it should be compressed to a 6 byte number.

Usage: Compressed number will be feeded to a device (which can only take up-to-6 numeric chars). Device will decode the number back to the original number.

Assumption/Limits:

If required both client and device(server) can share some common properties required for encoding/decoding the number.
Only one request can be made to a device i.e. all data should be fed in one request, no chunk of small packets

Thanks.

You can do this if you represent the number in its binary form (raw data). But even then, you will need 9 bytes to store. — nhahtdh
– nhahtdh, Commented Jun 25, 2012 at 10:35
Do you need to actually compress the number? Or is what you need in fact a hash? — biziclop
– biziclop, Commented Jun 25, 2012 at 10:44
Then why dont you just divide the number into 6 byte chunks? Perhaps with some sort of encoding that tells the device how many chunks there are. The only way doing what you want to do is if the numbers in question share some sort of properties, for example if they were all divisible by 100 then you could get away with not storing the last 2 digits. But for generic numbers, no there is no way you can compress an individual # into a smaller # of bytes, at least not unless you have a lot of these numbers you want to store in a single blob — user439407
– user439407, Commented Jun 25, 2012 at 10:55
You specify Java, and you say you have 6 chars. Since a Java char is 16 bits, that gives you 96 bits, enough to encode all numbers with not more than 28 decimal digits. If you need to handle larger numbers and don't have severe restrictions on what numbers are legitimate, it's simply not possible. — Daniel Fischer
– Daniel Fischer, Commented Jun 25, 2012 at 16:26

Marko Topolnik · Accepted Answer · 2012-06-25 11:09:51Z

7

This will be the best you can get assuming that any combination of digits is a legal input:

final String s = "98765432101234567890";
for (byte b : new BigInteger('0'+s).toByteArray()) 
  System.out.format("%02x ", b & 0xff);

Prints

05 5a a5 4d 36 e2 0c 6a d2

Storing a number in binary form is theoretically the most efficient way since every combination of bits is a distinct legal value.

You may have other options only if there is more redundancy in your input, that is there are some constraints on the legal digit combinations.

edited Jun 25, 2012 at 11:09

answered Jun 25, 2012 at 10:40

Marko Topolnik

201k31 gold badges336 silver badges455 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

JSS Over a year ago

Marko: Thanks for your time but try printing the output without .length for the same input and you will notice a strange behaviour (the output for the same input is different all the time).

Marko Topolnik Over a year ago

If by "output" you mean the default toString implementation of Java arrays (that returns its hashCode generated from the physical address in memory), then yes, that output is different every time -- and irrelevant to you.

LiKao · Accepted Answer · 2012-06-25 10:58:06Z

2

The way you specify it, this is not possible. There simply are more 20 digit numbers than there are 6 digit numbers, so if you map 20 digits to only six digits, some 20 digit numbers will have to be mapped to the same six digit number. If you know that not all numbers will be valid or even have the same likelyhood, this can be used for compression, but otherwise this is impossible.

Although a reversible (bijective) mapping from 20 digit numbers to six digit numbers is impossible it is still possible to map long numbers to shorter output. This works by reducing the requirement that the output needs to be a number. The only important consideration is that the output sequence needs to have the same number of possibilities as the input. Here is an example:

There are 10^20 possible 20 digit numbers
If you use a sequence of full 8-bit ASCII (256 characters) of length x you will have 256^x possible outputs. If you solve this for x, you will notice that 256^9 > 10^20 so 9 ASCII characters are enough to encode 20^10 possible numerical inputs.

Marko's answer to the same question will tell you how to convert a number to it's byte representation which may be used as input. But be aware that this input will not be numerical and may contain many strange symbols.

answered Jun 25, 2012 at 10:58

LiKao

10.7k7 gold badges57 silver badges93 bronze badges

2 Comments

Marko Topolnik Over a year ago

Notice that OP has tried Huffman and the like. That produces binary output.

LiKao Over a year ago

@MarkoTopolnik: Yes, agreed. Most likely he wants some binary format, since otherwise this would be impossible. However I also wanted to point out that this is not clear from the description of the requirements. So I did in no way mean to imply that your answer is wrong.

Collectives™ on Stack Overflow

Java algorithm to Compress small numeric number

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related