Losslessness and prefix property of the explicit LZ78 code

Every dictionary entry is an ordinary word over $\mathcal{A}$. While unread text remains it ends in $\mathrm{\#}$, which no dictionary word contains; the root is a prefix and the finite dictionary therefore has a longest matching prefix with a following symbol. Each iteration removes at least one symbol, so from the finite input followed by $\mathrm{\#}$ the parser terminates after at most $n+1$ records, at a final marker record. If an ordinary phrase $wc$ were already in the dictionary, it would be a longer dictionary prefix than the selected $w$, contradicting the longest-prefix rule. Thus ordinary inserted phrases are distinct; the terminal phrase contains $\mathrm{\#}$ and is distinct from them.

For a parent index $i\ge 0$, put $m=i+1$, $b=\lfloor {\log }_{2}m\rfloor +1$ and $d=\lfloor {\log }_{2}b\rfloor +1$. The Elias-gamma code of $b$ consists of $d-1$ zeros followed by the $d$-bit binary expansion of $b$. Its first $1$ reveals $d$, after which exactly $d-1$ more bits complete $b$. Append the final $b-1$ bits of the binary expansion of $m$ to form its Elias-delta code; the decoder restores the leading $1$ of $m$ and then returns $i=m-1$. Thus the gamma header determines exactly how many suffix bits to read. No codeword can be a proper prefix of another, because identical headers determine the same suffix length. For $m=1,2,4$ the codes are respectively $1$, $0100$, and $01100$, so the case $b=1$ has an empty suffix but still a nonempty header. Appending a fixed-width $\lceil {\log }_2(q+1)\rceil$-bit symbol field gives an unambiguously delimited nonempty record.

The decoder lookup and dictionary update of [F1] recover each phrase. Since $\mathrm{\#}$ appears exactly once as the final symbol, decoding stops at the first such field, and a valid terminated codeword cannot be a proper prefix of another valid terminated codeword. Thus the concatenated records form a lossless prefix code on finite input words after termination.

The exact index length is $2d-1+(b-1)=b+2d-2=b+2\lfloor {\log }_{2}b\rfloor$. At phrase number $j\ge 1$, the parent satisfies $0\le i<j$, hence $m\le j$ and $b\le {\log }_2(j+1)+1$. Since $b\le 2{\log }_2(j+2)$, its length is at most ${\log }_2(j+1)+2{\log }_2{\log }_2(j+2)+3$. Thus, writing $s_q=\lceil {\log }_2(q+1)\rceil$, the $N$ output records, including the final marker record, have total bit length at most $N[{\log }_2(N+1)+2{\log }_2{\log }_2(N+2)+3+s_q]$. This is $O(N\log (N+1))$, with the same bound valid for every small index including $i=0$. The final record is encoded and counted even though its phrase is not inserted into the dictionary.