Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from security.stackexchange.com Nov 11 '11 at 9:59

This question came from our site for Information security professionals.

3  
What does this have to do with IT Security? –  D.W. Nov 11 '11 at 4:41
1  
can't use a loss less compression like Huffman coding!! They are ideally suited for texts... but then at receiving end you should really know about this mutation you have done for getting back the text. –  Vineet Menon Nov 11 '11 at 8:54
5  
You're describing compression, not encoding –  Andy Smith Nov 11 '11 at 9:41
    
@Andrew - Ok, any suggestions? –  Abe Miessler Nov 17 '11 at 4:09
add comment

4 Answers

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).

share|improve this answer
1  
+1, excellent explanation. I did not know about the =/== being related to the length having to be a multiple of 4. I may be able to work around this for my needs –  Abe Miessler Nov 10 '11 at 21:56
2  
+1 for the pigeonhole principle –  Dog eat cat world Nov 11 '11 at 8:10
    
Mind you, this assumes a lack of pigeonholes. Unicode has plenty of letters. We really need a better understanding of the real problem. –  MSalters Nov 11 '11 at 14:25
add comment

Re-encoding characters is generally done when the receiving system can't process them. For example, BASE64 is representing data using 6 bits (26, 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
share|improve this answer
add comment

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.

share|improve this answer
add comment

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?

share|improve this answer
    
How does LZ compression compares to gzip or bzip2 mentioned in attir suggestion? –  Emmad Kareem Nov 11 '11 at 19:06
    
gzip is built on LZ and Huffman Coding. more on LZ en.wikipedia.org/wiki/LZ77 –  A.Rashad Nov 11 '11 at 19:39
2  
Thanks, +1 for the compression idea. –  Emmad Kareem Nov 11 '11 at 19:56
    
thanks to you .. –  A.Rashad Nov 11 '11 at 20:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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