Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
These answers seem to suggest that Huffman algorithm produces optimal codes under reasonable conditions. –  Anko Jan 6 '13 at 15:51
    
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 Jan 6 '13 at 22:32
    
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 Jan 7 '13 at 0:24
1  
But huffman are for prefix-free for which we know the Kraft-inequality (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 Jan 7 '13 at 7:15
    
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 Jan 7 '13 at 21:53
add comment

FWIW, it seems likely to me there is a PTAS for the problem, following the basic idea in this paper. (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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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