Finite-block LZ78 incremental prefix code

Input: A finite alphabet $\mathcal{A}$ of size $q\ge 2$, an integer $n\ge 0$, a word $x_0^{n-1}\in {\mathcal{A}}^n$ (with $x_0^{-1}$ denoting the empty word when $n=0$), and a terminator $\mathrm{\#}$ not in $\mathcal{A}$. Fix an injective $s_q:=\lceil {\log }_2(q+1)\rceil$-bit symbol field for $\mathcal{A}\cup \{\mathrm{\#}\}$. The alphabet convention is that of Finite-alphabet stationary source. Output, when the procedure terminates: a finite terminated binary record stream; prefix codes use Binary prefix codes on finite supports.

1. Start with dictionary $D[0]=ϵ$ and unread text $x_0^{n-1}\mathrm{\#}$. While text remains, let $w$ be the longest dictionary word prefixing the unread text, let $i$ be its dictionary index, and let $c$ be the next symbol. Output the record $(i,c)$ and remove the prefix $wc$ from the unread text. If $c\mathrm{\ne }\mathrm{\#}$, append $wc$ as the next dictionary entry; if $c=\mathrm{\#}$, stop without inserting the terminal phrase.

2. Serialize each parent index $i\ge 0$ by the Elias-delta code of $m=i+1$. Put $b=\lfloor {\log }_{2}m\rfloor +1$ and $d=\lfloor {\log }_{2}b\rfloor +1$. Emit $d-1$ zeros, then the $d$-bit binary expansion of $b$, then the final $b-1$ bits of the $b$-bit binary expansion of $m$. Append the fixed-width symbol field for $c$. Concatenate these records in parser order, including the final marker record.

3. To decode an encoded block, start with dictionary $D[0]=ϵ$. Count the leading zeros before the first $1$ of an index header as $z$ and set $d=z+1$. Read the following $d-1$ bits; together with that first $1$, these are the $d$-bit binary expansion of $b$. Read the next $b-1$ bits and prepend $1$ to recover $m$; put $i=m-1$. Read the next $s_q$ bits as $c$, and emit $D[i]c$. Append that phrase to the dictionary when $c\mathrm{\ne }\mathrm{\#}$, then read the next record. At the first $c=\mathrm{\#}$, stop without insertion and remove the terminal marker from the decoded text. The decoder is specified on valid encoded streams and is not supplied the source length or record count.

Ordinary inserted phrases are dictionary entries; the final phrase containing $\mathrm{\#}$ is an output record but is not a dictionary entry. Termination, distinctness of ordinary complete phrases, losslessness, the prefix property and the exact index-length bound are proved in Losslessness and prefix property of the explicit LZ78 code ↗.