Variable-to-Fixed Length Code and Plurally Parsable Dictionaries

Aa variable-to-fixed length encoding procedure is a mapping from a dictionary of variable length strings of source outputs to the set of codewords of a given length. For memoryless sources, the Tunstall procedure can be applied to construct optimal uniquely parsable dictionaries and the resulting codes are known to work especially well for sources with small entropies. We introduce the idea of plurally parsable dictionaries and show how to design plurally parsable dictionaries that can outperform the Tunstall dictionary of the same size on very predictable binary, memoryless sources.