0

It is not unlikely that what I want to do is not possible, but it doesn't hurt to ask.

Imagine a set of lists, each containing positive integers (in my case, a list always consists of four integers, but that shouldn't make any difference).

a = [35, 2, 123684, 647]
b = [453, 346457546457, 6, 0]
c = ...

Then there is an alphabet, e.g.

alphabet = [A, .., Z, a, .., z, 0, .., 9]

What I want to do is to create a function that transforms the lists into strings using the alphabet.

f: (list[Int], alphabet) -> string 

The requirements for f are as follows:

  • f should be injective in the sense that two different lists always result in two different strings and one specific list always results in the same string each time f is called.

    Notes:

    • Two lists are equal if both contain the same elements in the same order.
    • It is ok if transformations of different lists using different alphabets result in the same string. The unique-requirement only applies to the transformation of different lists using the same alphabet.
    • An inverse function is not required.
  • Now the hard part: the resulting strings must be as short as possible.

All of the numbers are 32 bit integers. But the fact that they vary greatly in size (the possible range is from 0 to Int.max) should be taken into account. Just chaining the 32 bit representations together (or doing something else that uses chunks of a fixed size) is not a viable solution.

One approach could be to choose one character of the alphabet and use it as a separator. This is basically what hashids does. E.g. if 'A' is the separator, all resulting strings would look like this: "...A...A...A...".

What I don't like about this solution:

  • The effective size of the alphabet is reduced by one, since one of the characters can only be used as a separator, not for encoding numbers. This results in longer strings, especially when using small alphabets
  • The separatoritself also extends the string. Encoding a list of four integers means three additional characters in the result.

I'm wondering if there is a less obvious solution to the problem, maybe a more mathematical approach? Essentially, the problem is to "merge" multiple numbers into a single (unique) number.

  • Base64 encoding? That's what the author of hashids actually recommends, if you don't need all the fancy stuff in hashids. That's about as good a lossless compression as you're going to get with human-readable characters. – Robert Harvey Jun 7 '16 at 1:36
  • 2
    As a rough idea: use a Huffman encoding first to convert the list into a binary number which is as short as possible. Then use Base64 encoding to convert the binary to your final string. – Doc Brown Jun 7 '16 at 4:59
  • @RobertHarvey The question is still how the input for the Base64 encoder would look like. Just passing the 4 numbers as a byte array (with 4 * 32 bits) surely results in a larger string than the one hashids would produce. – ceaaj Jun 7 '16 at 10:17
  • @DocBrown Could you elaborate on how the Huffman encoding can be used to combine the numbers? In order to get unique results, I guess that I have to use the same huffman tree for all lists, not one specific tree for each list. But since the digits of the numbers are evenly distributed (instead of having digits with higher and lower frequencies which is utilized by hoffman), is there really a benefit? – ceaaj Jun 7 '16 at 10:33
  • I don't see how. hashids uses base63 encoding. With delimiters, as you already pointed out. Its string is almost certainly going to be larger, not smaller. – Robert Harvey Jun 7 '16 at 14:35
0

I think Doc Brown hit upon the real problem: it is a compression problem. As such, first streaming the numbers to a binary representation (compressed bits, a byte array) and then encoding using the letters is probably the best solution. When you stream to a binary representation, include the length of any variable sized collection as the header before the body. The length can be 7bit encoded, or use a a fixed sized integer, as appropriate. If all of your lists are the same size, you don't need a length for them.

How I would stream this myself:

  • the number of lists (length as described above)
  • each list (fixed size of 4 integers)
  • each item in the list 7 bit encoded -- this is a variable sized encoding
  • no separator is needed

After streaming to a memory stream, I would then take the resulting bytes, and use LZ4 or your favorite compression algorithm. Then encode that using your character set.

Note: at the time I wrote the answer above, I thought the arrays were going to be combined before compression. It turns out each must be compressed separately. This is a more difficult topic and requires more information about the source and usage of the arrays. You can find some information here: http://encode.ru/threads/343-Compressing-small-bits-of-data

  • If you don't know how to do 7 bit encoding I will post a sample. – Frank Hileman Jun 9 '16 at 17:01
  • Thanks for your answer Frank. If 7 bit encoding is the same as MSB VarInt encoding, then I'm already doing that (using the first bit of a byte to indicate whether or not the following byte belongs to the same number). The thing is that I only want to encode single arrays (with a fixed size of 4, e.g. [1, 2, 10, 0]), not a set of these arrays. The average size of such an array after the 7 bit encoding is around 7-8 bytes. – ceaaj Jun 10 '16 at 9:17
  • As a subsequent step, I tried to encode the result with LZ4 and ZLIB, but the compressed output seems to be larger than the input. So either I did something wrong, or ~8 bytes is just too little to be compressed efficiently. – ceaaj Jun 10 '16 at 9:20
  • @ceaaj Yes I believe you have the same algorithm. It is impossible to apply compression to such a small string, except some custom compression. I am not a compression expert, but you are headed in the right direction. I don't understand why your question is mentioning separators, however. There is no need for them if the arrays are fixed size. – Frank Hileman Jun 10 '16 at 16:22
  • @ceaaj If you must compress each array separately, your best bet is to take advantage of some knowledge you have about the data therein, if any. Suppose the numbers tend to be near each other in value, within a list. You can xor the second number with the first, and xor the third with the second, etc, to obtain numbers that have smaller overall values (and shorter 7 bit encodings). You then do the reverse on decompression. Another option is to recognize some pattern of repeating numbers. If you have any more information, provide it in your question and put a heads up here. – Frank Hileman Jun 10 '16 at 16:31

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.