> It would be interesting to see a uniquely decodable code that is neither a prefix code nor one in reverse.
More interesting than I thought. First the adversarial answer; sure (edit: ah, I see someone else posted exactly the same!):
a 101
b 1
But it's a bad code, because we'd always be better with a=1 and b=0.
The Kraft inequality gives the sets of code lengths that can be made uniquely decodable, and we can achieve any of those with Huffman coding. So there's never a reason to use a non-prefix code (assuming we are doing symbol coding, and not swapping to something else like ANS or arithmetic coding).
But hmmmm, I don't know if there exists a uniquely-decodable code with the same set of lengths as an optimal Huffman code that is neither a prefix code nor one in reverse (a suffix code).
More interesting than I thought. First the adversarial answer; sure (edit: ah, I see someone else posted exactly the same!):
But it's a bad code, because we'd always be better with a=1 and b=0.The Kraft inequality gives the sets of code lengths that can be made uniquely decodable, and we can achieve any of those with Huffman coding. So there's never a reason to use a non-prefix code (assuming we are doing symbol coding, and not swapping to something else like ANS or arithmetic coding).
But hmmmm, I don't know if there exists a uniquely-decodable code with the same set of lengths as an optimal Huffman code that is neither a prefix code nor one in reverse (a suffix code).
If I was going to spend time on it, I'd look at https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm -- either to brute force a counter-example, or to see if a proof is inspired by how it works.