What type of encoding can I use to make a string shorter?

Question

I am interested in encoding a string I have and I am curious if there is a type of encoding that can be used that will only include alpha and numeric characters and would preferably shorten the number of characters needed to represent the string.

So far I have looked at using Base64 encoding to do this but it appears to make my string longer and sometimes includes == which I would like to avoid. Example:

test name|120101

becomes

dGVzdCBuYW1lfDEyMDEwMQ==

which goes from 16 to 24 characters and includes non-alphanumeric.

Does anyone know of a different type of encoding that I could use that will achieve my requirements? Bonus points if it's either built into the .NET framework or there exists a third party library that will do the encoding.

Answer 1

The final '=' or '==' in Base64 is there only to make the number of characters a multiple of 4. You can remove it, since you can always put it back later on. Note that Base64 is so called because it uses 64 distinct characters. Uppercase letters, lowercase letters, and digits, that's 62. So Base64 also uses '/' and '+', which may or may not fit your bill.

On a general basis, if you want to encode arbitrary sequences of bytes into alphanumeric characters, there is necessarily some length extension somewhere, because there are 256 possible values for a byte, and only 62 alphanumeric characters. It is sometimes called the pigeonhole principle. An encoding scheme must have an average length extension of a factor log 256 / log 62 = 1.344 (average over all sequences of bytes); otherwise, it means that some pigeons are being crushed to death somewhere and you will not get them back without damage (which means: two distinct strings encoded to the same, so decoding cannot work reliably).

Now, it is quite possible that your strings are not exactly "sequences of uniformly random bytes"; your strings have some meaning which means that most possible sequence of bytes will not occur, because they are meaningless. On that basis, you can probably devise an encoding scheme which will incur less length extension than generic Base64 (or Base62 if you need to stick to strict alphanumeric characters). This is lossless data compression. It works over a clearly defined probabilistic model of what can appear as input.

Summary: a generic scheme for encoding strings into alphanumerical sequences such that no or little length extension ever occurs, cannot exist; it is a mathematical impossibility. A specific scheme tailored for the kind of input string you expect can probably exist (but since you do not tell what kind of string you may encounter, noone can help you on this).

Answer 2

Re-encoding characters is generally done when the receiving system can't process them. For example, BASE64 is representing data using 6 bits (2⁶, hence 64) of characters to represent longer data sequences (the sometimes-appearing "==" at the end is padding for alignment). This is because your picture file in email may have 0xFE in it and your mail server will be unhappy transmitting that (or any other traditionally non-printing character).

There is no encoding that "reduces size." Encodings are just mappings of bits to the character they represent. That said, ASCII is a 7 bit character set (encoding) that is often stored in 8 bits of space. If you limit the ranges that you accept, you can also weed out the control characters.

Using this method means you have to write things out at the bit level, and it also plays a bit of hell with machine speed & instructions because all modern machines have alignments that are multiples of 8 bits. That, for example, is why Unicode is UTF-8, UTF-16, and UTF-32.

If you're doing this for security (that's why you posted it on Security.SE, right?), just filter things out and store them normally. If you're doing this to save space, consider whether all the extra code and slower access time (because most entries will cross address boundaries) is worth the space savings.

By the by, the following is a snippet from a CS course where we had to convert ASCII from 8 bit storage to 7 bit:

    memset(dest,0x00,8);
    memcpy(dest, source, length);

    for (int i = 0; i < 8; i++) {
            if (dest[i] & 0x80) {
                    fprintf(stderr, "%s: %s\n", dest, "Illegal byte sequence");
                    exit(EILSEQ);
            }
    }

    dest[0] = 0x7F & dest[0] | 0x80 & dest[1] << 7;
    dest[1] = 0x3F & dest[1] >> 1 | 0xC0 & dest[2] << 6;
    dest[2] = 0x1F & dest[2] >> 2 | 0xE0 & dest[3] << 5;
    dest[3] = 0x0F & dest[3] >> 3 | 0xF0 & dest[4] << 4;
    dest[4] = 0x07 & dest[4] >> 4 | 0xF8 & dest[5] << 3;
    dest[5] = 0x03 & dest[5] >> 5 | 0xFC & dest[6] << 2;
    dest[6] = 0x01 & dest[6] >> 6 | 0xFE & dest[7] << 1;
    dest[7] = 0x00; //Clearing out

Answer 3

You can compress the data with e.g. gzip, bzip2 or lzma and then run through base64 to limit the used character set. This is beneficial only on larger strings of hundreds of bytes or more.

Answer 4

why not use LZ compression? this can be a decent way of compressing a string, but would be more efficient in case of long strings. How long is the target string you want to encode?