LZ78短语字典与同步重建

LZ77的号码是“离当前写位置有多远”；LZ78的号码是“字典中的第几条短语”。后者可以保留很久以前发现的完整短语，但字典会持续长大，编号字段也会变长。

双方不必预先共享一个大词库。编码端每次宣布“第i条后面加这个新字节”，译码端就能做出同样的新条目。新短语只增加一个后缀字节，因此用父指针表示比每次复制完整短语更节省字典空间。

输入 ABABABA 的短语分解为 A | B | AB | ABA，最后无残余：

• $(0,A)$：输出A，新增 $D[1]=A$
• $(0,B)$：输出B，新增 $D[2]=B$
• $(1,B)$：输出AB，新增 $D[3]=AB$
• $(3,A)$：输出ABA，新增 $D[4]=ABA$
• $(0,END)$：输出空串，停止

连起来恰是七个字节。另一个输入 ABABA 在得到A、B、AB三条后只剩A，它已经在字典中，故最后发 $(1,END)$。如果仅规定“每次都要发送旧编号加新字节”，这个末尾会无字节可发；丢掉它则错误恢复成ABAB。

空文件就是 $(0,END)$。输入 AAAA 可发 $(0,A),(1,A),(1,END)$，对应 A | AA | A。一个没有字节的结束标记只能出现在最后；结束后还有token必须拒绝。收到 $(7,B)$ 而当前字典只有编号0至3时，是向前引用，不允许预先创建第7条或无限等待它出现。

字典大小到达上限后，协议可以停止加条目、重置，或切换到新块，但必须事先固定规则。若编码器擅自重置而译码器继续增长，之后相同编号会表示不同短语。这里的检查器到达字典预算就明确失败，没有隐含的重置token。

同步和无环的证明 ​

初态两边仅有相同的空条目。若此前字典一致，合法编号 $i$ 指向相同短语，追加同一个字节后得到相同输出和新条目，故字典继续一致。父编号严格小于新编号，所以沿父指针必定到0，不会构造循环。终止token只读已有条目，不改变这一归纳。

若当前已有 $m$ 条含空条目的字典记录，编号可用 $\lceil {\log }_{2}m\rceil$ 位表示；最初 $m=1$ 时编号0占零位，仍可由token标签和后面的字节区分动作。普通token还要8位字节和类型信息，END的编号也要编码。仅比较短语数量与原字节数，会漏掉增长的指针费用。本文定义token语义，不宣称给出了通用LZ78标准bitstream；完整的两个教学文件在流封装页理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。使用Huffman和算术编码。

保存每条完整短语可能重复保存大量前缀。父指针、末字节和短语长度把字典描述控制为 $O(k)$ 条记录，其中 $k$ 为新短语数；解码一个短语需要沿父链逆序收集再输出。全部父链遍历工作与展开字节数同阶，所以是 $O(k+n)$，另有最长短语长度的临时栈。实现必须在建栈之前用已保存的短语长度检查输出和工作预算。

LZ78是根据前缀形成字典的机制。其渐近通用性结论需要明确源类或有限状态编码比较类，不能由这个四token例子推出所有短文件都会缩小。它也不是LZW；LZW使用不同的码输出和字典更新规则，有自己的特殊解码情形。