Minimizing compression overhead in a simple compression algorithm

Question

Note: this question has been re-written to simplify and generalize the problem. The original is available below.

Suppose I created a simple compression scheme for lists of 2-digit numbers. It has 2 modes:

• Mode 0: The numbers are written as-is, uncompressed.
• Mode 1: Only the ones digit is written for each number, but the run of numbers must have the same tens digit. This provides 2:1 compression given an infinite list of numbers with the same tens digit.

The compressed output string must have only digits 0-9, except for the following 3-character magic values which must be used to switch the mode of compression:

• *** - switch to mode 0
• *x* - switch to mode 1, where x is the common tens digit for the numbers that follow. If the tens digit changes, the mode 1 switch needs to be written again, with a different common tens digit.

The compressor can switch freely between the two compression modes. So, some two ways that the list of numbers 11 12 13 14 21 22 23 24 can be encoded are:

***1112131421222324 (only mode 0, each number written out as-is)
*1*1234*2*1234      (only mode 1, only ones digits are written after the mode switches, 
                     but mode 1 needed to be started twice, for each diff. tens digit)

In the above example, using mode 1 saved 5 characters, but that is not always the case. Encoding the list 15 26 37 48:

***15263748
*1*5*2*6*3*7*4*8

is shorter in mode 0. And obviously, in more complex texts, the modes need to be mixed correctly to provide the shortest result. For example, encoding the list 11 12 21 22 23 24 25 26 18 39:

***11122122232425261839 (only mode 0)
*1*12*2*123456*1*8*3*9  (only mode 1)
*1*12*2*123456***1839   (mode 1 then mode 0)

the third encoding provides the shortest result, by properly mixing the encoding modes.

Given this specification, an encoder that exhaustively tries mixing the 2 modes while encoding a list of numbers will give the shortest possible compressed result. Obviously, such an encoder takes a ridiculously long time - O(n^n). Trying to think of a more efficient encoder, I got stumped.

So my question - is it possible, given the above specification, to write an encoder that would perform better than O(n^n) - that could make decisions in mixing the 2 compression modes without exhaustively trying every single combination? Or is the exhaustive algorithm the only way to get the shortest possible compressed string?

Thanks in advance to anyone who shares any insight on this. Note that my goal is to figure out the general compression problem illustrated in my question, rather than to simply find/create an efficient number list compressor.

=============================================================================

Below is my question as it was phrased originally, in terms of text encoding

=============================================================================

I thought up a simple UTF-16 text compression scheme that has 2 modes:

• Mode 0: UTF-16 byte pairs are written as-is, uncompressed.
• Mode 1: Only the least-significant-byte is written for each character, but the run of characters must have the same most-significant-byte (be from the same unicode block). This provides 2:1 compression given an infinite string of characters from the same unicode block.

Assume that it takes 3 bytes to change the mode. Switching the active most-significant-byte (unicode block) on mode 1 likewise takes 3 bytes.

Below are some examples of how UTF-16 text can be encoded given this specification. In the examples,

"a" = any character from unicode block 1
"b" = any character from unicode block 2
"===" = 3-byte value indicating mode 0 is now active
"---" = 3-byte value indicating mode 1 is now active

So the text "aaaabbbb" (4 different characters from unicode block1, and 4 diff. chars. from unicode block 2) can be encoded as

===aaaaaaaabbbbbbbb  (each letter takes up 2 bytes)  -or-
---aaaa---bbbb       (each letter takes up 1 byte, but mode 1 needed to be started twice, because b is from a different block than a)

In the above example, using mode 1 saved 5 bytes, but that is not always the case. Encoding the text "abab",

===aabbaabb
---a---b---a---b

is shorter in mode 0. And obviously, in more complex texts, the modes need to be mixed correctly to provide the shortest result. For example, encoding the text "abbbbbbab",

===aabbbbbbbbbbbbaabb
---a---bbbbbb---a---b
---a---bbbbbb===aabb

the third encoding provides the shortest result, by properly mixing the encoding modes.

I wrote an encoder, given this specification, that exhaustively tries mixing the 2 modes while encoding a string and outputs the shortest result. Obviously, this takes a ridiculously long time - O(n^n). Trying to write a more efficient encoder, I got stumped.

So my question - is it possible, given the above specification, to write an encoder that would perform better than O(n^n) - that could make decisions in mixing the 2 compression modes without exhaustively trying every single combination? Or is the exhaustive algorithm the only way to get the shortest possible compressed string?

Thanks in advance to anyone who shares any insight on this. Note that my goal is to figure out the general compression problem illustrated in my question, rather than to simply find/create an efficient text encoder.

Answer 1

Consider:

• Mode 1 is only more efficient when you have a run of the same tens digit.
• Mode 1 saves 1 character for each same tens digit, except the first
• It costs 2 characters to switch to mode 1.
• Therefore Mode 1 only becomes advantageous after 4 similar 10s characters (costs 2, saves 3)

For example, consider if you are running in mode 0. A switch to mode 1 breaks even after 3 tens characters:

818283
*8*123

and becomes advantageous after 4 tens characters

81828384
*8*1234

However,

• It costs 3 characters to switch back to mode 0

Therefore, it is only worthwhile switching to mode 1, if:

You have 7 or more similar tens characters (cost 2 + 3, save 6), eg

102010208182838485868710201020
10201020*8*1234567***10201020

Or you have adjacent runs of tens characters that save you more than it costs to switch back to mode 0 (3). Again, runs of 3 gain you nothing, runs of 4 gain you 1 etc. In the example below there are 4 runs of 4 adjacent 10s, so we save 4 characters. One more than the three we need to switch back.

102010206162636471727374818283849192939410201020
10201020*6*1234*7*1234*8*1234*9*1234***10201020

Now the above rules assume some infinite stream. In reality you can gain at the start of the stream by choosing whichever encoding you want for the first sequence, and at the end of the stream you won't have to change back to mode 0 if you have duplicate 10s right to the end. This is why your examples seem so arbitrary. They're so short that the start and end optimisations override the main rules.