Readers of this blog will know that I spent some time in Hong Kong, specifically in 荃湾 (Tsuen Wan). Part, not all, of my job there was to help compress Chinese fonts, because they needed to be written to mask ROM, where every bit counts. These days, storage, even permanent storage that works when the power is off, is plentiful and dirt cheap but not then -- and not so long ago either!
Here's an idea I had. Suppose you have a Chinese character (or a western character for that matter), but emphasis on a large character set like GB2312 (GB stands for Guojia Biaozhun = 国家标准 = National Standard), China's original computer character set. It has around 7000 glyphs (characters) including 6763 Chinese characters plus assorted other characters, such as the Latin and Cyrillic alphabets, Japanese hiragana and katakana, and more.
Suppose you're a dot matrix printer and you are tasked with printing a glyph based on two pieces of data: a large table of probabilities of what a row of 8 dots will be based on dots that have already been printed. In particular, the zeroth (invisible) row, the row above the first row is all 0s (blank) and the actual first row is likely blank too. So let's set up the situation like this
xxxx yyyyyyyy
zzzz qqqqqqqq
Here, xxxx yyyyyyyy and zzzzzzzzz are parts of the character (glyph) that have already been printed. qqqqqqqq is the part to print next. If this part of the character is a horizontal stroke, then are two likely possibilities:
(a) yyyyyyyy and qqqqqqqq are the same
(b) qqqqqqqq is blank
In any case we imagine this.
We take all 7000 characters and we do a computation (on a big computer) of all possible values of
xxxx zzzz yyyyyyyy qqqqqqqq
For each case of xxxx zzzz yyyyyyyy we find the most likely value of qqqqqqqq and put this in a database. The database has 16 x 16 x 256 = 65536 entries.
In a printer from that era, a medium-resolution character set might use 32 dots in each direction, for 1024 bits in all, or 64 bytes of data. For each character, we print it in pieces. For each piece, we look up the values of xxxx zzzz yyyyyyyy If they match match the database entry, we write the single bit 0. Otherwise, we write the bit 1 and the actual values of qqqqqqqqq
So it's a game. We have already used up an extra 65536 bytes of data. For each 8 bits of character data, it takes either 9 bits (if the database doesn't match) or 1 bit (if we get a match from the database).
We can play the game a different way.
We can have 3 matches in our database for each row xxxx zzzz yyyyyyyy
00 01 10
So up to 3 values of qqqqqqqq are a match, but otherwise we have to write 11 + actual value.
So we have 3 chances to match the value, but we waste 2 bits every time we're wrong.
Techniques like this can be used quite successfully to compress simplified fonts, but less successfully for traditional fonts -- because there is less white space in these fonts. The Taiwanese character set has 11000 characters instead of 7000 for the Chinese set.
When I first told my boss about "predictive" encoding, he was suspicious about what happens if "predictions" are wrong. He's quite correct -- the process depends on characters being predictable -- on average -- from other information in the character. This is sometimes not possible -- even humans reading the character need to depend on feature recognition -- the complete stroke structure cannot be seen when the character is small.