r/compression • • 10d ago

Can we efficiently encode decimal digits using smaller number of bits?

(the idea is completely mine, but took some help from AI to write the post in a coherent language)

I was exploring this question and thought of a simple variable-length encoding scheme for decimal digits:

  • Digits 0–3 use 3 bits: 000, 001, 010, 011.

  • Digits 4–9 use 4 bits: 1001, 1010, 1011, 1100, 1101, 1110.

Decoding is straightforward:

  • If the first bit is 0, read next 2 bits and convert to decimal.

  • If the first bit is 1, read next 3 bits and convert to decimal and add 3.

  • Then go to the next block.

For the sequence 0123456789, this requires 36 bits instead of 40 bits in Packed BCD or 80 bits in ASCII.

The drawback is "Variable-Length Random Access Overhead": there is no way to access nth digit from the memory, without counting from the beginning again.

My questions:

  1. Is this or similar encoding already known and used?

  2. Are there better alternatives?

  3. Can random access be improved without sacrificing storage efficiency?

I'd appreciate your thoughts and technical feedback.

9 Upvotes

39 comments sorted by

7

u/CorvusRidiculissimus 10d ago • Bravo

I've seen similar encodings used elsewhere, though nor for that purpose. Variable length encoding is pretty common. It would work just fine, if your objective is to store long runs of decimal digits. I have another idea though, even better: Group them.

Ideally you'd want a number which is a power of both ten and two. Unfortunately there is no such number. But 1024 is pretty close. So, group your decimal digits in groups of three, and encode each group of three as a ten-bit number. Packing efficiency is pretty close to perfect for a random distribution, and it's seekable too. Plus you get twenty-four leftover codepoints that you can use for other purposes. Finally, if the string of bits terminates early, that means interpret the final four or eight bits as BCD because the length of string isn't divisible by three.

0123456789 now takes up 34 bits. Two less then yours!

Ignoring the problem of handling the end of run, that gets you 3.333 bits per digit, while packed BCD gets you exactly 4.000. The theoretical maximum, which you might reach by using an arithmetic coding on a long run, is log2 10 = 3.3219.

1

u/mpp06 10d ago edited 10d ago

Yes, that's a wonderful idea. Grouping improves efficiency to almost theoretical. I have explored grouping and various grouping combinations earlier. I arrived at what I called as '9 to 5 encoding', where I took a group of 9 decimal digits and converted it to 5-digit base-64 code. This is perhaps the best possible for 10-64 system, with least wastage of empty bits. I am not sure if that context fits here, though. Need to think through it.

1

u/mpp06 10d ago

I tried for 10-block formation with my scheme, but it seems to be not possible in this case, because we have the length of either 3 or 4 bits for each block, so block of 10 bits is not possible, unless we mix, and even then only a few permutations are covered.

5

u/ivanhoe90 10d ago edited 10d ago

What about this?
0 - read two more bits,
10 - read two more bits, add 4,
11 - read one more bit, add 8

000 - 0
001 - 1
010 - 2
011 - 3
1000 - 4
1001 - 5
1010 - 6
1011 - 7
110 - 8
111 - 9

You can also analyze your specific input and give 3-bit codes to digits that occur often, 4-bit codes to digits that occur rarely.

You should learn about prefix codes :D

2

u/mpp06 10d ago edited 10d ago

Quite amazing! I was trying this idea, but did not arrive at this scheme! Will try out. I have read about prefix codes, but I think I will skip that for now or maybe, review.

2

u/mpp06 10d ago

Your scheme is based on the prefix codes. Now I get it!

1

u/ivanhoe90 10d ago

I mentioned 10 different codes (3-bit and 4-bit in length). You can actually use any code you want! The key is that no code should be a prefix of anotehr code ( If you set 0101 for "5" and 01011 for "6", then, 01011... could be "5" and "6" - it is ambiguous).

1

u/xylarr 9d ago

As mentioned elsewhere, due to Benford's Law you'll want to encode 8 and 9 as a larger number of bits.

So make 10 add 4 - but only have 100 and 101, then have 11 be add six.

3

u/Worth-Wonder-7386 10d ago

The most efficent you can do is an average of log2 of the number of states that you are trying to encode. For 10 digits that is around 3.32, and you use 3.6.
People have pointed to various methods that can be used, but a Huffman encoding is a very general version of this.
There you construct a binary tree for your data, and what the computer just can do is look through the binary tree and see if a point is a leaf node or not when deciding to terminate.
This is even more efficent if the data is non uniform and you can encode that into the data so that more common subsequences are shorter.
For the example of encoding the digits we can divide the tree into four parts with 2 bits and they will either have 2 numbers requiring 1 bit or 3 numbers requiring 2 bits to distinguish. So we get an average of 3.5 bits per number.

There is lots of information written about such optimal encoding schemes in the field of information theory.

2

u/mpp06 9d ago

Insightful. Thanks for elaborating, and directing me to the field of information theory, which is something new to me worth exploration. I was just doing this purely out of curiosity and interest.

2

u/ivanhoe90 10d ago edited 10d ago

I have never seen a use case for this problem (encoding an alphabet of 10 characters as binary).

Digits usually represent integers, and then, it is more efficient to encode them as binary integers.

Maybe, if you had an image of 10 colors, and for each pixel, you want to store indices into a palette, then, instead of using 4 bits per index, your method allows using 3.6 bits per index.

However, benefits of your method disappear once you apply some lossless compression to your encoded data (vs. data encoded with a more stupid encoding).

4

u/mpp06 10d ago

One possible use case is to store digits of numbers like pi, first in this format and then zip it. I have actually tried this with another similar scheme (my 9 to 5 encoding described in reply to first comment), and found that the final zip was 10% smaller, compared to zipping the text file containing actual digits. But whether that benefit applies in this case needs to be examined.

0

u/TheThiefMaster 9d ago

You should try a better compressor like 7zip or bzip2.

.zip is ancient and known to be a bit weak.

1

u/which1umean 10d ago

I actually did something like the above at work not too long ago.

The reason is that I wanted to be able to catch transpositions quickly on tons of pairs of numbers, so I encoded the numbers like this and then did the bit math on them to look for transposed digits.

I was able to get it WAY faster than using the built-in algorithm on strings this way. 👍

1

u/WikiBox 10d ago

Look up BCD encoding. You can, for example, encode a decimal digit using four bits and fit two digits into a byte. Good simple compromise if you don't want binary integers.

https://en.wikipedia.org/wiki/Binary-coded_decimal

1

u/mpp06 10d ago

yes, I know the basic idea of BCD, and actually started with that. The goal here was to try and improve upon it.

1

u/ivanhoe90 10d ago

His method allows you to fit more than two digits into a byte, like 2.2 digits on average.

1

u/raphman 10d ago edited 10d ago

Thanks for sharing your thoughts! As /u/CorvusRidiculissimus pointed out, the approach is not completely new, and there might be better solutions for most real-world use cases. Nevertheless, I had not yet thought about your concept and found it worthwhile to think about it for a few minutes. Just in case you do not know this already: this is quite similar to how UTF-8 stores Unicode characters in 1-4 bytes.

2

u/mpp06 10d ago

Didn't know the UTF thing. will check out!

2

u/vip17 9d ago

in fact it's also similar to Huffman tree if the ratio of 0-3 is equal and higher than 4-9

1

u/SeriousPlankton2000 10d ago

You dicoverd Huffman coding

1

u/mpp06 10d ago

wow. makes me feel good! will check it out!

1

u/regular_lamp 10d ago

I guess that is not that dissimilar to what you'd get when applying Huffmann coding to only digits.

1

u/mpp06 9d ago

Yes, someone has mentioned it. I am not aware of Huffman coding logic, and I will check it out.

1

u/CoachSevere5365 9d ago

While you're at it, check out run length encoding. It's not directly relevant to your current use case, but you might find it interesting.

1

u/mpp06 9d ago

Thanks. wow, RLE. it's there in Golly, the 2D cellular automaton software. I love Golly and explored it. read a bit about RLE in Golly help, but not enough to say anything more here!

1

u/CoachSevere5365 9d ago

I don't know If it's used for anything these days. I know it was used for fax but the only time I've come across it was fixing endianness issues when porting a patent scanning system to Linux circa 1999.

1

u/OzzyM_Dev 9d ago

Yes. I think you'll find something very very interesting though.

DPD. Densely Packed Decimals.

It chooses the approach of packing the decimals into groups of 3. If we used BCD, storing 123 would get:

0001 0010 0011

12 bits

However DPD can use 3 bits to identify any number 0-7 split into groups of 3

but when it comes to 8 and 9, it splits decimals into two groups

small and large

0-7 and 8 and 9

8 and 9 are the only large digits, meaning you only need one bit to distinguish between them once we know that the digit is large.

so for 123, DPD says

001010(0, a control bit to indicate all three digits are 0-7)011

Now for 129, DPD says

001010(1, a control bit, indicating at least one digit is large.)00(indicates where the last digit is large and where the first digits are small)1(1 meaning 9 here)

When multiple digits are 8 or 9 it changes how it arranges everything here to make room for the information required, with 8 possible variations, but this is just to sort of show the idea here.

It also solves the random access problem.

For 123456789012

DPD splits it into four groups

123, 456, 789, 012

represented using 10 bits each, that's 40 vs 48 for BCD

Say you want specifically the 8th digit

You don't need to look through block 0 and 1, since they each only contain 1-3 and 4-6 in the sequence

so you can skip directly to block 2 without reading all the other blocks.

Now I should also mention something.

Of course, when we talk about decimal storage for general use cases we generally aren't asking the questions that BCD or DPD are answering here.

But binary is generally just more efficient than any of these because say 123

Binary can just go 1111011 and that's 7 bits and we look like fools

Binary is also slightly more space efficient over long sequences and it's also more efficient usually because modern cpus are built for binary arithmetic

There is a few advantages against binary like floating point which binary floating point fails at 0.1 or like, say if you want to extract a given digit in a sequence, binary needs you to convert to decimal or do modulo arithmetic or something,

BCD lets you just grab it, DPD lets you find the digit in a group of 3, which is a lot simpler than what you do with binary.

Overall it's just what situation are you in where you don't use binary? There's definitely a few that exist, hence why BCD and DPD and well, you, tried to store decimals better, it's just interesting.

1

u/mpp06 9d ago

First of all, thank you so much for the elaborate comment! I have explored DPD slightly, and I found it indeed very close to my idea of 9 to 5 encoding (see my reply to first comment of this thread). There are indeed use cases where binary may not be the best choice, but no arguments about binary being most compact storage.

My exploration started when I noticed that BCD uses a total of 25 zeros and 15 ones to represent the decimal numbers from 0 to 9. I wondered, can I bring a balance to it, towards equal number of total zeros and ones used?

Then I created a scheme that used 19 zeros and 17 ones, and incidentally, it took a total of 36 bits instead of 40 for BCD, to represent the sequence 0123456789. It was a happy coincidence. So I am now just exploring how far I can take this.

Indeed it's a very interesting exploration, where I am also learning so many new concepts I never heard of!

1

u/vip17 9d ago

yes DPD would be more efficient in general, because 3 digits always map to 10 bits. OP's algorithm is only better when most of the digits are in the 0-3 range

1

u/Lion2471 9d ago

I'll point out that your scheme will also benefit a tiny bit from Benford's law.

1

u/xylarr 9d ago

Ah yes, I was trying to remember this. All I had was a vague memory that the numeral 1 occurs more than 9.

1

u/Underhill42 9d ago

And what if you want to store 23? as-is the strategy doesn't scale very well. You can also run into some difficulties distinguishing between number transitions in a long bitstream. Especially if a byte is corrupted, or you tuned in late so you don't know where it started. Any encoding system that depends on perfection is doomed to eventually fail spectacularly.

You could improve that by storing each chunk as the same 4-bit length, e.g.the initial numbers are 0---, so that there's a clear indicator that this is the last bit-cluster in this number. Then you always know which bit is the "stop? bit", and can positively ID it no matter what came before.

But it still means you're wasting 1/4 of the bit stream just indicating if you should continue or not, which makes it really inefficient for larger numbers. E.g. a number that requires 16 bits to represent normally requires ceiling(16/3) = 6 chunks = 24 bits.

Google Protocol Buffers have a variable-length integer type that does something similar at the byte level, with as I recall the high bit in each byte indicating whether this is the last byte in the number. Still wasting 1/8 of the bit capacity... but most small numbers will fit in 7 bits

E.g. Byte 1 = 0------- = number is the corresponding value from 0-127 (or -64 to +63 if signed)
Byte 1 = 1------- = same initial value, but left-shift it by seven bits (=multiply by 128) to make room for the 7 low bits that will be added by the next byte.

Byte 2+ = repeat. Just keep going, left-shifting and adding 7 bits per byte until you hit a byte starting with zero, which indicates these are the last 7 bits in the number.

1

u/Broad-Promise6954 9d ago

There are many variable encoding schemes. One of my favorites is in TeX, which encodes numbers that are expected to be small (but must be positive) by using leading zeros to count remaining digits: values from 1 to 9 are encoded as 1 to 9; 10 through 99 are 010 through 099; 100 is 00100; and so on.

In the end and in the absence of patterned input your best bet is a general compression algorithm like Huffman encoding, but if you know the shape of your data you can do better. It's mainly a question of trade-offs.

1

u/SM1334 9d ago edited 9d ago

I came up with this last year, kind of a similar concept, much more complicated.

https://www.reddit.com/r/compression/s/HxrFZN24e4

A very basic explanation of this is;

Imagine I assign a pattern to 0000, that value is now taken. So if I assign another value to 0001, we already know 0000 is used so I can just give you the first 3 0s and you can assume the 4th bit is a 1. We can then structure the entire pattern index using this same implied indexing scheme. But this isnt just limited to the index itself, but also the patterns too. If we have a bunch of sequential patterns we can arrange them the same way and shave off bits on that side as well.

1

u/robinechuca 9d ago

C'est une très bonne idée! Mais dommage pour toi c'est déjà ce qui est utilisé depuis belle lurette dans le codage de Hufmann, et plus généralement dans tous les codages anthropiques. L'idée est proche de la tienne, le symboles qui aparraissent souvent, on leur associe un mot qui se code sur peu de bits, ceux qui apparaissent plus souvent, on leur assigne un mot plus long.

Voila, donc avec le recul c'est en effet une bonne idée car elle existe depuis plus de 100 ans et pourtant elle est toujours utilisée.

1

u/NoNameSwitzerland 8d ago

You also could do some arithmetic coding. If the different numbers have different probability, then you only need the optimal fractional bit size. But random access is not possible anymore and a error ruins everything.