One of the key benefits of Tunstall and other variable-to-fixed length codes
is the availability of random access to individual codewords in the compressed
stream. However, when one begins decoding of a randomly retrieved codeword,
he/she has no exact knowledge of position at which the corresponding decoded
phrase should be placed in the decoded space. In some cases, such position can
be estimated, but if an application requires exact placements of decoded
phrases, then the problem becomes much harder. Thus, in practice, one might be
forced to spend additional bits to communicate start position, or perform
sequential decoding of codewords preceding a given one in order to obtain its
offset. Both such approaches exhibit serious drawbacks (added redundancy or
higher complexity), and highlight the need for algorithms for fast navigation
through compressed streams.

In this talk, we study the problem of parsing of variable-to-fixed-length
codes, where the difference between parsing and conventional decoding is such
that for parsing it is sufficient to accurately identify the length of a
phrase represented by a codeword, while for decoding it is also necessary to
reproduce this exact phrase.

We show, that there exists a family of optimal (in minimum redundancy
sense) variable-to-fixed length codes for memoryless sources, such that the
average number of operations needed for their parsing is at most $O(\log D)$,
where $D$ is the expected decoded phrase length. The complexity of full
decoding of such codes, however, is $O(D)$.  Hence, we show that parsing of
variable-to-fixed length codes can be executed much faster than their full
decoding. Both parsing and decoding in our proposed algorithms require linear
$O(D)$ amount of space.