Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

Question

When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40. Reference:

Here's a reference: https://en.wikipedia.org/wiki/Data_Matrix#Text_modes

Some sections of the string will compress more efficiently than others depending on the encoding method.

To be clear, I'm not trying to make my own compression scheme.

I want to compute the best combination of existing compression schemes. For example, I can individually use Ascii or C40 to encode an entire string. Each scheme has its unique benefits.

BUT I can also compress specific parts of the string with different schemes. So, switching back and forth between Ascii and C40 can result in a more efficient compression than C40 or Ascii alone.

QUESTION: How do I optimize the selection of compression schemes for section of the input string. I would be comfortable narrowing it down to only combining c40 and ascii.

Are there any algorithms for scanning strings and and optimizing the result?

Answer 1

If you want to find the optimal combination, one approach would be to use dynamic programming. Let $f(n,s)$ denote the length of compressing the first $n$ characters via some combination of compression methods, ending with the compression subsystem in state $s$. Here $s$ represents both which compression method is currently being used (Ascii or C40) as well as its internal state (i.e., whether you are currently in set 0, set 1, set 2, or set 3).

Then you can compute $f$ recursively. Applying memoization, we get a dynamic programming algorithm to compute $f$. The resulting algorithm will take $O(n)$ time to compute the best compression.

How do you compute $f$ recursively? Basically, when computing $f(n,s)$, you consider both possible cases for how to encode the $n$th character:

• Case 1: Stick with the same compression method and state you had before, when encoding the $n$th character. The cost of doing so is $f(n-1,s) +$ the number of bits to encode the $n$th character when in state $s$.

• Case 2: Switch compression methods and/or state just before encoding the $n$th character. The cost of doing this is $f(n-1,s') + $ the number of bits to switch from state $s'$ to state $s$ and then encode the $n$th character while in state $s$.

You should choose whichever of those provides a shorter encoding. In other words, $f(n,s)$ is the smaller of these two quantities. This gives a recursive algorithm for computing $f$, which can be memoized, yielding a solution that is essentially dynamic programming.

Since there are only 8 possible states (2 compression methods $\times$ 4 choices of the character set), the running time to compute $f(n,s)$ is $O(n)$. This gives you a linear-time algorithm to find the best combination of compression algorithms for encoding any given string.