MrApples

While working on the idea for another text compression algorithm, the idea for this one hit me.

You should know
A character on windows, or a letter ( such as 'a', 'A', '1', '$' ) takes up 1 byte. There are 256 different values in a byte, which is 8 bits ( binary ), so 2^8 = 256. 10001100 - 256 combinations

Most of these characters are almost never used, like % and ones I don't even know how to type. So, by using a smaller character set by default, and then extra bits for when a rare character is used, logically you should be able to save space.

00000 = a
00001 = b
00010 = c
...
11111 = *other* + 10101 = $

So a common character would take 5 bits, and a rare one would take 10, instead of every taking 8 ( an estimate ).

This is where it gets ugly
My idea is to have a separate character set for every NEXT character based on the CURRENT character.

If you look at the statistics for commonly used characters in HTML, you will notice there is always a steep slope on probability of the next character.

Probability of next character for 'a' in HTML

• "s" 14098
• "n" 12682
• "r" 11894
• "l" 10842
• " " 10324
• "t" 9159
• ">" 7724
• "d" 7303
• "m" 6676
• "c" 6145
• "g" 5836
• "v" 5548
• "b" 3946
• "y" 3132
• "i" 2974
• "p" 2698

Probability of next character for '<' in HTML

• "/" 26523
• "a" 8032
• "d" 6211
• "l" 3135
• "s" 2847
• "t" 2533
• "b" 1980
• "i" 1979
• "h" 1168
• "T" 853
• "p" 823

So, logically by the laws of probability, this can be used to save data. As most, in terms of percentage/bit look like this.

• 1-bit 19.7%
• 2-bit 36.4%
• 3-bit 61.9%
• 4-bit 89.1%
• 5-bit 97.7%
• 6-bit 99.8%
• 7-bit 100%

The algorithm is also very adaptive, and by just feeding it examples, it can work much better for those kinds.

It can also be much faster in comparison to current compression algorithms, such as gZip, as it doesn't rely on guesswork.

------------------------------------

Anyone follow? Anyone heard of something similar?

King Stubby

that is cool! I've never heard of anything like it!

MrApples, your genius is showing...

GhostlySpoon

I haven't heard anything like it, and I don't really understand it all, I understand up to the point of the next character probability thing. I understand what you mean about making some of 5-bit and others 10-bit.

What I find hard to understand though, is what the whole probability thing would do.

The World Ends With You!

MrApples

What the first part is about, using less bits for much more common characters, and using more bits for rare characters.