r/algorithms • • 10d ago

Help A fixed-block encoding experiment: converting 9 decimal digits into 5 Base64 characters

I have been experimenting with a simple encoding idea that I call as '9-to-5 Encoding'.

The concept is applicable only to a sequence of integer digits, for example, digits of π without the decimal point.

Method:

Start from the leftmost digit and take every block of 9 decimal digits, interpret them as an integer, and represent that integer using just 5 characters from a 64-character alphabet.

For example:

314159265 → IkR2X

The reason I chose 9 and 5 combination is because the max value of 9 decimal digits is closest to max value of 5 Base-64 digits when converted to decimal, as compared to other combinations between decimal and Base-64. So, we waste a minimum number of empty mappings between the two.

I tested the approach on 10 million digits of π.

The interesting result:

  • ZIP of original decimal text: 4,693,723 bytes

  • ZIP of 9-to-5 encoded text: 4,205,187 bytes

That's approximately 10.41% less compressed storage.

It is well-known that binary representation is shortest for numbers, and this is not a claim of a new compression algorithm.

However, if it is text representation of the numbers, this '9 to 5' scheme seems to offer an advantage after zipping the text representation for 10 million digits of π. I have also found a similar advantage for 1 million digits of π.

I am thinking to explore other number datasets and compare against binary representations, especially after zipping.

I'm curious:

Has anyone come across a similar fixed-block encoding scheme? And what other experiments would you recommend?

I'd particularly appreciate feedback from people working in data compression, information theory and numerical representation.

2 Upvotes

3 comments sorted by

3

u/lizardpq 10d ago

It makes sense that "pre-compress using your knowledge that the string contains only decimal digits, then do general-purpose compression" is better than just general-purpose compression.

Your observation that 109 is close to 645 =230 is related to the fact that 103 is close to 210 =1024. A binary encoding of decimal digits that uses this is https://en.wikipedia.org/wiki/Densely_packed_decimal

1

u/mpp06 9d ago

Thanks for appreciating, and for the insights. As 9 and 5 combination cannot be reduced further, this is the smallest grouping for decimal to base-64 for my scheme.

0

u/Ashamed_Difficulty89 6d ago

I'm not sure, but what you mention sounds awfully similar to what's known as Word RAM model, where a text that uses only subset of a larger alphabet is encoded using a smaller alphabet to save space.