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.