3
$\begingroup$

I have a string like this:

11,512,64,23,46,12,67,85,84

And I'm sure it's following these rules below:

  1. Only , and 0123456789 in it.
  2. No number will be bigger than 999, that means they are all 1,2 or 3 digits number.

Are there any simple algorithms that I can have to compress/decompress the data?

For instance, a very stupid way I can think is to convert each number into base-16 or even base base-36 numbers.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Why not integers in a list? I am pretty sure they used the most efficient way to implement those standard types. $\endgroup$ – Asqiir Nov 17 '18 at 8:49
  • $\begingroup$ The idea behind "the best way" is in fact largely independent of the programming languages. Can you edit your question so as not to emphasize the usage of Javascript? $\endgroup$ – John L. Nov 18 '18 at 17:28
  • 1
    $\begingroup$ @Apass.Jack Sure. I removed it. I am using LZMA but I don't know whether there are better ways. $\endgroup$ – AGamePlayer Nov 19 '18 at 4:42
  • $\begingroup$ Yes, there are better ways I believe to take advantage of the structure information. There is an algorithm better than the accepted answer as well. Just use base-2 instead. Use 10 bits for each number. Ignore the commas since they can be restored. $\endgroup$ – John L. Nov 19 '18 at 4:48
  • $\begingroup$ Is it possible that the string will ever begin with a comma, end with a comma, or that there will be two consecutive commas? ... i.e. Will it always be a comma-separated list of numbers? $\endgroup$ – David Dubois Dec 8 '18 at 17:38
3
$\begingroup$

Treat this as a base-11 number (the comma is treated like the digit "10"). Convert the base-11 number to binary, and use the resulting binary string as the compressed version of your data.

This will be close to optimal. It falls short of optimal only in that it does not take into account the guarantee that every number in the list will have at most 3 digits -- but even taking that into account would not improve the compression ratio much.

The absolute best method will depend on the distribution of data that you will be compressing; but I expect this will be close to optimal for most real-world distributions.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.