2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ If I understand correctly, I walk up the string building a sub string for each new character. I compute the byte-cost(encode it using both methods) at every character addition and compare the costs. Which ever cost is lower use that? I’m lost at the transition when switching methods. Can you provide a little pseudo-code or more logic to the comparison? $\endgroup$ – GisMofx Apr 18 '18 at 1:19
  • $\begingroup$ @GisMofx, I suggest you try to implement code to calculate $f(n,s)$ yourself (recursively), using only recursive calls to $f(n-1,\text{something})$. I suspect you'll find that the recursive code basically writes itself -- there's pretty much only one reasonable way to compute it, once you understand the definition of $f$. Then memoize it. At that point you will understand. I'm not sure how to explain it better, so hopefully it'll become clear why you try to do it. $\endgroup$ – D.W.♦ Apr 18 '18 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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