How do I construct an optimal affix code? 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?
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.