Universal fixed-to-variable lossless source coding for memoryless sources is studied in the finite blocklength and higher order asymptotic regimes. Optimal three-term fixed-error asymptotic expressions are derived for general fixed-to-variable codes and for prefix codes. It is shown that the non-prefix  Type Size code , in which codeword lengths are chosen in ascending order of type class size, achieves the optimal third-order term, and outperforms classical two-stage codes. Converse results are proved making use of a result on the distribution of the empirical entropy and Laplace’s approximation. Finally, the fixed-to-variable coding problem without a prefix constraint is shown to be essentially the same as the universal guessing problem.
['Oliver Kosut', 'Lalitha Sankar']
Asymptotics and Non-Asymptotics for Universal Fixed-to-Variable Source Coding