8
$\begingroup$

I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, D, E, F to represent 10,11,12,13,14,15 -- and that's what i want to do to my own numbering system but in a bigger scale . Please correct me if i'm missing something .

Is it possible ?

$\endgroup$
  • 2
    $\begingroup$ See also here. $\endgroup$ – Raphael Sep 10 '14 at 13:05
  • 5
    $\begingroup$ Frank's answer explains why this doesn't work. But here's something you could have asked yourself before you started: what special property of the number 80 do you think you are using? Unless there's something special about 80, if your idea worked for 80, wouldn't it work better for 81? Or 801? $\endgroup$ – David Richerby Sep 10 '14 at 13:05
  • 3
    $\begingroup$ @DavidRicherby: I can't think of much value to base 80, but there is actually some real value in using base-85: it can convert groups of four octets into five printable characters. While the storage efficiency isn't a huge improvement over base-64 (twenty characters will represent fifteen octets in base-64 and sixteen in base-85), the fact that the basic data "chunk" is 32 bits rather than 24 can sometimes be very helpful. $\endgroup$ – supercat Sep 10 '14 at 17:15
  • $\begingroup$ I mean what if i could find some patterns and represent them in symbols ? $\endgroup$ – Kinani Sep 10 '14 at 20:52
  • 2
    $\begingroup$ If you find patterns and represent them in symbols, you've created a working compression algorithm (as long as the representation is shorter than the original pattern). This is how all compression algorithms work. $\endgroup$ – Tanner Swett Sep 11 '14 at 1:59
30
$\begingroup$

While you will need fewer 80-based numbers than 2-based numbers (bits) to encode the same file, the only way to store these 80-based numbers on a computer is to encode them as bits. So you do not gain anything.

In fact you actually lose space, since 80 is not a power of 2: You will need 7 bits for each 80-based number, but in these 7 bits you could instead encoed 128 different states, if you used them directly.

$\endgroup$
10
$\begingroup$

There are several ways to interpret the question. What I think you might be asking is that you have a sequence of $n$ letters in an alphabet $\Sigma$ where $\left| \Sigma \right| = 80$. You want to store this in as few as possible bits. We will assume that the letters in the alphabet are uniformly distributed.

The information-theoretic amount of space required to store this is $n \log_2 \left| \Sigma \right|$ bits. Using arithmetic coding, you can do this in linear time, using $O(\log n)$ bits of intermediate space. (Remember, that's the logarithm of the number of symbols, in bits! If the size of the sequence fits in a machine word, the intermediate storage required is a constant number of machine words at the most.)

So that's pretty good. But what about if we want random access?

It turns out that it can be done. The first technique to do it was only discovered about four years ago. We can store the sequence in $n \log_2 \left| \Sigma \right|$ bits, such that reading or writing any entry takes $O(1)$ time. If you think about it, this is a remarkable result, because it means that a computer which works with any radix is, in a sense, equivalent to a binary one.

Here's the paper: Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup, An Alternative to Arithmetic Coding with Local Decodability, STOC 2010.

By the way, remember the name Mihai Pătraşcu. He was and is the closest thing we have to a modern-day Évariste Galois. He died very young, of a brain tumor at the age of 29. But in his short career as a computer scientist, his work revolutionised the field of analysis of algorithms in ways that will take decades to fully understand.

$\endgroup$
3
$\begingroup$

If you have a number (eg. 123456789⏨) as text you can write it in a different base (such as 21i3v9 in base 36), so you compress it written as text (from 9 characters to 6).

If you go further you end up storing it in binary (4 bytes¹).

Now, this works because you started with a reduced set [0-9] and moved to a bigger one [0-9a-z] and many bits of data were unused in the initial representation.

Similarly, if we know that a file only contains letters, we can easily compress it by changing the base. However, if you were to compress from arbitrary content, that won't (always) work. You may compress (get smaller outputs) for some files, but others will become larger just as any lossless compression method, this is unavoidable.

It can still useful though, for instance a method that compresses English texts well but makes Chinese texts larger may be good enough if you write a lot more English than Chinese.

¹ Actually you only need 2²⁷ bits, although nowadays computer storage uses multiples of 8 bits (but perhaps you wanted to store a serie of numbers of 2²⁷ bits? ☺).

$\endgroup$
2
$\begingroup$

Base 80?? Why 80? It doesn't make sense, however base 85 does. It's quite convenient as you can represent 4 bytes using 5 characters (because 85^5 = 4,437,053,125 which is slightly more than 2^32 = 4,294,967,296)

Here's my code for writing a single 32-bit word:

for (i=0; i<5; i++)
{
    c = (word % 85) + 37;
    word /= 85;
    fwrite(&c, sizeof(uint8_t), 1, file);
}

and here's for reading it back:

    word = 0;
    for (i=4; i>=0; i--)
        fread(&c[i], sizeof(uint8_t), 1, file);

    for (i=0; i<5; i++)
        word = word*85 + c[i]-37;

If you really want to use base 80 you can use the same approach and replace the instances of 85 with 80 and you'll need 6 characters for every 4 bytes instead of 5.

How is it going to compress anything though? You do realise that files are written in base 256, right? This being said if you zip a file written in base 85 it will be about the same size as the zipped original base 256 file, which makes base 85 (or base 64) a nice choice if you want to represent binary data using printable characters.

$\endgroup$
0
$\begingroup$

Different bases are used for different purposes, although as the other answers explain you won't gain anything in terms of compression.

See wikipedia for an explanation of base64 encoding. Base 64 is often used, not for compression, but to encode binary data that would normally result in non-printable characters and control codes into a printable ASCII character space. This will result in a larger file size, but is useful for transferring binary data that can be embedded in other ASCII files, e.g. inside XML, emails, CSS, web pages, etc.

$\endgroup$
  • $\begingroup$ What you say is true but it doesn't answer the question. $\endgroup$ – David Richerby Sep 11 '14 at 7:55
  • $\begingroup$ @DavidRicherby I disagree. It does answer the question from the point that it is possible to use number bases other than the ones that the OP is familiar with, and that they do have a purpose, but that purpose is not compression. $\endgroup$ – Luke Mills Sep 12 '14 at 0:02
  • $\begingroup$ The question is, is it possible to compress files by writing them in base-80? The answer to that is "no", as you mention in your first sentence and as all the other answers already cover. Your second paragraph is a comment about the question. Comments go in comments. $\endgroup$ – David Richerby Sep 12 '14 at 9:03

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.