1
$\begingroup$

Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100.

Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as shortest length as possible?

So the person can dictate sequence of letters and numbers by phone and it can be recreated into bytes on the other side.

Im really bad at math, and found how to shorten that string up to about 100 symbols. Any way to di it shorter?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Thousand bytes gives $2^{8*1000}$ variations. A character of Latin alphabet is roughly enough to encode 6 bits of information. One such encoding is often used in situations when binary data is to be transferred over text-only protocol: Base64. $\endgroup$
    – wvxvw
    Commented Sep 23, 2015 at 22:37
  • $\begingroup$ @wvxvw Make an answer? $\endgroup$
    – Yuval Filmus
    Commented Sep 23, 2015 at 22:42
  • $\begingroup$ Base 64 its the thing that i have thought, but the string length is still quite long. ill mark an answer though, it there wouldnt be less trivial approaches. $\endgroup$
    – Drinkins
    Commented Sep 23, 2015 at 22:56

1 Answer 1

Reset to default
2
$\begingroup$

A common encoding used for such tasks is Base64. It is easy to implement and it has been implemented multiple times in many main-stream languages. However, it is not exactly suited for being read by humans.

The basic underlying idea is that a character of Latin alphabet is encoded in ASCII using 6 bits. The encoding alphabet is completed by few punctuation symbols to make it the exact multiple of 8.

Here is a nice even if somewhat light-hearted proposal http://www.crockford.com/wrmg/base32.html for alternative Base32 encoding (it also tries to prevent occasional appearance of expletives in the produced encoding, at least if it is interpreted as English language).

Unfortunately, you won't be able to make it much shorter using only Latin alphabet, unless you have more information about the nature of the data being encoded. Text compression algorithms would try to discover such information about the text being encoded and use variable length encoding, assigning shorter sequences in the output to the more common sequences in the source text. For a simple example of such encoding you can look into Huffman coding

Another, obvious way to shorten the output length is to use a larger alphabet.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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