<p>I really don't think that there is a known algorithm to be optimal. In fact, there is a major conjecture about how effective a set of code words can be, see: <a href="http://arxiv.org/abs/0709.2598" rel="nofollow">http://arxiv.org/abs/0709.2598</a>
(the name I knew for affix code is fix-free code). If an algorithm was proved to be optimal, then most probably it would also solve (or disproof) this conjecture as well.</p>

CC BY-SA 3.0
2013-01-06T15:51:51.300Z
[These answers](http://cs.stackexchange.com/questions/3176/is-huffman-encoding-always-optimal) seem to suggest that Huffman algorithm produces optimal codes under reasonable conditions.
Anko
CC BY-SA 3.0
2013-01-06T22:32:11.817Z
I don't see how those answers are related to your problem. If you just one an algorithm, you can use huffman, and then extend some bad words.
domotorp
CC BY-SA 3.0
2013-01-07T00:24:51.370Z
I'm only making the point that *some* codes can be proved to be optimal. Extending a Huffman code's codewords would likely make it unoptimal, since every extension makes it approach a block coding. This might be a starting point though!
Anko
CC BY-SA 3.0
2013-01-07T07:15:56.443Z
But huffman are for prefix-free for which we know the Kraft-inequality (http://en.wikipedia.org/wiki/Kraft%27s_inequality). If we have proof of optimality, kraft-like inequality follows. But for fix-free codes the resp. inequality is conjecture, so there can be no proof.
domotorp
CC BY-SA 3.0
2013-01-07T21:53:03.703Z
On page 8, bottom, several fix-free codes for English are described, and it is mentioned that none of the algorithms used to construct them have been proven to be optimal. So presumably no efficient algorithm is known.
Yuval Filmus
CC BY-SA 3.0
2013-01-06T12:57:07.497Z
2013-01-06T12:57:07.497Z
domotorp
<p>FWIW, it seems likely to me there is a PTAS for the problem, following the basic idea in <a href="http://www.cs.ucr.edu/~neal/Papers/sicomp_41_3_684.pdf" rel="nofollow">this paper</a>.  (This doesn't exactly answer your question, but I'll still describe the PTAS here in the answer section as it is too long to fit in a comment.)</p>

<p>Fix any constant $\epsilon&gt;0$.  Let $p$ be an an instance of the problem, i.e., a probability distribution on $[n]$.</p>

<p>Say that a code (a set of codewords) is <em>$K$-fix-free</em> if no codeword in the code <em>that has length $K$ or less</em> is a prefix or suffix of another codeword.   </p>

<p>Fix $K=\lceil 1/\epsilon^2\rceil $.  Compute a min-cost $K$-fix-free code for $p$, in time polynomial in $n$, as follows.  For each of the (constantly many) subsets $S$ of strings of length at most $K$, consider the $K$-fix-free code $C(S)$ formed by assigning, to the $|S|$ largest probabilities in $p$, codewords from $S$ (matching smaller codewords to larger probabilities), then enumerating (in order of increasing length) the $n-|S|$ strings of length larger than $K$ that have no prefix or suffix in $S$, and assigning these $n-|S|$ strings as the codewords for the remaining $n-|S|$ probabilities (in order of decreasing probability).  Each subset $S$ gives a code $C(S)$; take $C_0$ to be one of minimum cost (by enumerating all choices for $S$).  $C_0$ is a minimum-cost $K$-fix-free code for $p$.</p>

<p>Note that the cost of $C_0$ is a lower bound on the cost of the optimal fix-free code for $p$, since the optimal fix-free code is also a $K$-fix-free code.</p>

<p>Next, convert $C_0$ into a fix-free code, without increasing its cost by more than a $(1+O(\epsilon))$ factor, as follows.</p>

<p>Within every codeword in $C_0$, insert an extra '1' into every (maximal) group of consecutive '1's of length $K' = \lceil 1/\epsilon \rceil$ or more.  (This increases the cost by at most a $(1+\epsilon)$ factor, and the resulting code will still be $K$-fix free, and no maximal group of consecutive '1's in any codeword has length $K$.)  Then, for every codeword in $C_0$ of length more than $K$, prepend $K'$ '1's followed by a '0', and append $K'$ '1's preceded by a '0'.  (This modification uniquely marks the start and end of each codeword, making the code completely fix-free. The modification increases the cost by at most a $1+O(\epsilon)$ factor overall.)  Take the resulting fix-free code $C_1$ as the solution.</p>

<p>Since $C_1$ costs at most $(1+O(\epsilon))$ times $C_0$, and the cost of $C_0$ is a lower bound on the cost of the optimal fix-free code, the fix-free code $C_1$ has cost at most $(1+O(\epsilon))$ times the cost of the optimal fix-free code.</p>

CC BY-SA 3.0
2013-01-12T07:10:56.623Z
2013-01-12T07:16:33.883Z
2013-01-12T07:16:33.883Z
Neal Young
<p>An <strong>affix code</strong> is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in <em>both directions</em> (forward and backward).</p>

<p>I want to create one that optimally compresses a given input symbol distribution, given a set of output symbols.</p>

<p>The Huffman algorithm (which creates prefix codes) comes closest, but due to its greedy strategy, it seems unsuitable for modification to this purpose.</p>

<p>How can optimal affix codes be found? </p>

<coding-theory><prefix-free-code>
How do I construct an optimal affix code?
Anko
# How do I construct an optimal affix code?

(Asked by: username_0 on 2013-01-04)

An **affix code** is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in *both directions* (forward and backward).

I want to create one that optimally compresses a given input symbol distribution, given a set of output symbols.

The Huffman algorithm (which creates prefix codes) comes closest, but due to its greedy strategy, it seems unsuitable for modification to this purpose.

How can optimal affix codes be found?

**Tags:** coding-theory, prefix-free-code

---

## 2 answers

### Answer by username_1 on 2013-01-06. Score: 4

I really don't think that there is a known algorithm to be optimal. In fact, there is a major conjecture about how effective a set of code words can be, see: <http://arxiv.org/abs/0709.2598>
(the name I knew for affix code is fix-free code). If an algorithm was proved to be optimal, then most probably it would also solve (or disproof) this conjecture as well.

> **Comments:**
> **username_0**: [These answers](http://cs.stackexchange.com/questions/3176/is-huffman-encoding-always-optimal) seem to suggest that Huffman algorithm produces optimal codes under reasonable conditions.  
> **username_1**: I don't see how those answers are related to your problem. If you just one an algorithm, you can use huffman, and then extend some bad words.  
> **username_0**: I'm only making the point that *some* codes can be proved to be optimal. Extending a Huffman code's codewords would likely make it unoptimal, since every extension makes it approach a block coding. This might be a starting point though!  
> **username_1**: But huffman are for prefix-free for which we know the Kraft-inequality (http://en.wikipedia.org/wiki/Kraft%27s_inequality). If we have proof of optimality, kraft-like inequality follows. But for fix-free codes the resp. inequality is conjecture, so there can be no proof.  
> **username_2**: On page 8, bottom, several fix-free codes for English are described, and it is mentioned that none of the algorithms used to construct them have been proven to be optimal. So presumably no efficient algorithm is known.  

---

### Answer by username_3 on 2013-01-12. Score: 2

FWIW, it seems likely to me there is a PTAS for the problem, following the basic idea in [this paper](http://www.cs.ucr.edu/~neal/Papers/sicomp_41_3_684.pdf). (This doesn't exactly answer your question, but I'll still describe the PTAS here in the answer section as it is too long to fit in a comment.)

Fix any constant $\epsilon>0$. Let $p$ be an an instance of the problem, i.e., a probability distribution on $[n]$.

Say that a code (a set of codewords) is *$K$-fix-free* if no codeword in the code *that has length $K$ or less* is a prefix or suffix of another codeword.

Fix $K=\lceil 1/\epsilon^2\rceil $. Compute a min-cost $K$-fix-free code for $p$, in time polynomial in $n$, as follows. For each of the (constantly many) subsets $S$ of strings of length at most $K$, consider the $K$-fix-free code $C(S)$ formed by assigning, to the $|S|$ largest probabilities in $p$, codewords from $S$ (matching smaller codewords to larger probabilities), then enumerating (in order of increasing length) the $n-|S|$ strings of length larger than $K$ that have no prefix or suffix in $S$, and assigning these $n-|S|$ strings as the codewords for the remaining $n-|S|$ probabilities (in order of decreasing probability). Each subset $S$ gives a code $C(S)$; take $C\_0$ to be one of minimum cost (by enumerating all choices for $S$). $C\_0$ is a minimum-cost $K$-fix-free code for $p$.

Note that the cost of $C\_0$ is a lower bound on the cost of the optimal fix-free code for $p$, since the optimal fix-free code is also a $K$-fix-free code.

Next, convert $C\_0$ into a fix-free code, without increasing its cost by more than a $(1+O(\epsilon))$ factor, as follows.

Within every codeword in $C\_0$, insert an extra '1' into every (maximal) group of consecutive '1's of length $K' = \lceil 1/\epsilon \rceil$ or more. (This increases the cost by at most a $(1+\epsilon)$ factor, and the resulting code will still be $K$-fix free, and no maximal group of consecutive '1's in any codeword has length $K$.) Then, for every codeword in $C\_0$ of length more than $K$, prepend $K'$ '1's followed by a '0', and append $K'$ '1's preceded by a '0'. (This modification uniquely marks the start and end of each codeword, making the code completely fix-free. The modification increases the cost by at most a $1+O(\epsilon)$ factor overall.) Take the resulting fix-free code $C\_1$ as the solution.

Since $C\_1$ costs at most $(1+O(\epsilon))$ times $C\_0$, and the cost of $C\_0$ is a lower bound on the cost of the optimal fix-free code, the fix-free code $C\_1$ has cost at most $(1+O(\epsilon))$ times the cost of the optimal fix-free code.


---

