4

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.

6
  • unicode.org/notes/tn31 Jun 26, 2015 at 3:01
  • I realize that there are various Unicode compression algorithms. Thanks, but my goal is to figure out the general compression problem illustrated in my question, rather than just find/create an efficient text encoder. I will edit my question to reflect that.
    – Duke Nukem
    Jun 26, 2015 at 3:40
  • I am still trying to figure out where the block number is encoded in mode 1. And can you switch from Mode 1 - block x to Mode 1 - block y directly? And what if your UTF stream contains characters like "-" or "=" ?
    – Doc Brown
    Jun 26, 2015 at 6:08
  • Oops, that's a leftover from editing. I originally had a block number in the mode1 switch, but decided to just use "---" for the sake of clarity. You need the full 3 bytes to switch between different blocks in mode 1 (that's pretty much the crux of the problem - at what point does the overhead from mode 1 switching start using more space than just writing out the uncompressed byte pairs in mode 0?) The symbols ("a", "---", etc...) used in the examples are just for clarity.
    – Duke Nukem
    Jun 26, 2015 at 7:51
  • Just to be clear, in my actual implementation, text is encoded in mapped blocks and the 3 mode-switch bytes encode mode, offset, run length, etc.. which is irrelevant to the current problem that has me stumped. Thanks for trying to figure this out :)
    – Duke Nukem
    Jun 26, 2015 at 7:52

1 Answer 1

4

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.

1
  • Thanks, this should get me on the right track. I'll try creating the compression algorithm based on your advice in a bit and post the results.
    – Duke Nukem
    Jun 27, 2015 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.