r/algorithms • u/mpp06 • 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.
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.
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