4
$\begingroup$

Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than 3 $b$'s). There is an easy way to get this working. Suppose you have a string of $n$ characters. Just add between every two numbers a new number so the string is correct. Decoding is not hard: just remove all numbers on even positions. So $abbbbaba \rightarrow axbxbxbxbxaxbxax$ and decoding is the same as just removing the $x$'s. But the problem is that the string size doubles. Is there a more efficient way to accomplish encoding and decoding? So encoding means encode all strings to valid strings and decoding means decode that string back to the original string.

$\endgroup$
  • 2
    $\begingroup$ Using extra symbols is kind of cheating (you can encode up to $|\Sigma|^n$ strings of length $n$ using alphabet $\Sigma$). So you can actually compress a binary string using larger alphabet! Could you please make the question more accurate? $\endgroup$ – Dmytro Korduban Feb 22 '12 at 15:53
  • 2
    $\begingroup$ @Dmytro: The x's in the original question stand for either a or b ... it is not hard to show that you can always replace the x's with some combination of a's and b's to achieve a legal string. $\endgroup$ – Peter Shor Feb 22 '12 at 19:10
  • 1
    $\begingroup$ Then it would be even possible to compress any random string to a string of length one (using a alphabet of unbounded size). $\endgroup$ – Rudy Feb 22 '12 at 22:31
6
$\begingroup$

This is called run-length-limited coding, there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature.

One simple thing you could do that does better than doubling the string size is:

(1) add a 0 to the end of the original sequence,
(2) break the original sequence greedily into blocks of either 0, 10, or 11,
(3) encode using the encoding

   0 → ab
10 → abb
11 → abbb

Step (2) is always possible, since after step (1) the sequence ends with a 0. Except for step (1), which adds at most two bits to your encoded sequence, this cannot do worse than double the string size, and generally does better.

For example, you encode
0110100101 → 0.11.0.10.0.10.10 → ababbbababbababbabb,
taking 10 characters into 19.

If I did my calculations right, starting with $n$ random bits, this encoding gives an expected length of 11/6 $n$ bits, which is only slightly more than the optimal value of around 1.813 $n$ bits.

$\endgroup$
  • $\begingroup$ We have already proven that $1.81... \cdot n$ bit is the optimal value using recursive formula's and counting the legal sequences. How have you found that that is the optimal value? Are there even more effective ways than this $1.83... \cdot n$ algorithm? $\endgroup$ – Rudy Feb 22 '12 at 22:35
  • $\begingroup$ @Rudy: I used recursive formulas and counting the legal sequences to get $1.813\, n$ as well. There are certainly even more effective ways than the $1.833 \, n$ algorithm, but I don't know whether any of them are as simple. $\endgroup$ – Peter Shor Feb 22 '12 at 22:42
  • $\begingroup$ @Rudy: somewhere in the literature there should be theorem giving polynomial-time algorithms for doing run-length encoding with arbitrary constraints. So, yes, you can get more effective algorithms. But I don't have time to do the literature search for you, and offhand I don't know whether any of them are as simple as the encoding I give in my answer. $\endgroup$ – Peter Shor Feb 27 '12 at 16:58
2
$\begingroup$

For the problem as you've posed it, it seems that you could simply replace every occurrence of an illegal sequence by a new symbol so that: aababbbaba -> xbayaba.

I guess that's probably too simple, but we'll need more information to provide a better solution (like the cost of adding symbols).

$\endgroup$
  • $\begingroup$ No, no new symbols are allowed, only $\{a,b\}$. So there are two symbols. We need to encode (il)illegal sequences to legal ones, and we must be able to go back to the original (il)legal sequences. $\endgroup$ – Rudy Feb 22 '12 at 15:56
  • $\begingroup$ I see what you mean now: the x's represent a or b depending on the context. I'll have another think. $\endgroup$ – Peter Feb 22 '12 at 16:07

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.