RLE与BZ/BZW——两种算法哲学
内容提要
本文比较PS2的PRLE与BZ/BZW压缩：RLE以“值+重复次数”编码连续重复数据，LZSS用回溯引用复用历史片段。PRLE用字面量块处理非重复数据，BZ用控制掩码，纯明文渐近开销约12.5%。两者无优劣，取决于数据分布与格式设计，理解它们有助于复古游戏逆向与资源解包。
延伸解读
RLE与LZSS：互补而非替代
文章指出RLE和LZSS利用不同的数据特征：RLE针对连续重复值，LZSS利用历史重复片段。两者没有绝对优劣，实际压缩效果取决于数据分布。例如，大片相同颜色适合RLE，而文本或结构化数据可能更适合LZSS。理解这一点有助于在逆向工程中正确识别压缩格式。
非重复数据的处理差异
对于完全不重复的数据，PRLE通过字面量块减少逐值开销，但仍有固定控制开销；BZ/BZW使用控制掩码，每8个明文共享1个控制字节，渐近开销约12.5%。文章强调，12.5%仅是纯明文编码的渐近开销，实际膨胀率还受引用编码、结束标记等因素影响。
膨胀率对比的定性分析
文章对比了PRLE和BZ/BZW在不同数据特征下的表现：长段连续相同值PRLE通常有效，BZ/BZW也可能有效；远距离重复片段PRLE通常不能直接利用，而BZ/BZW可以利用回溯引用但受窗口限制。这提醒我们，不能简单断言哪种算法压缩率更高，需结合具体数据分布和格式设计。
复古游戏逆向中的实际意义
在Dreamcast和PS2时代，资源压缩需权衡压缩率、解压速度、内存占用和实现复杂度。理解RLE和LZSS变体有助于编写解包器，避免混淆压缩格式、资源封装和图像编码。逆向工程的价值在于从简单指令中还原开发者的约束与选择。
Q&A
RLE和LZSS在压缩思路上有什么根本区别？
RLE关注连续重复的数据，用“值+重复次数”编码；LZSS关注数据与历史内容之间的重复关系，通过回溯引用来表示，即使重复片段相隔很远也能利用。
PS2的PRLE如何处理不重复的数据？
PRLE使用字面量块（Literal Block）机制，用一条指令表示一整段不重复的数据。例如，一段长度为5的字面量块会有一个控制word标记非重复块和长度，后面跟着5个数据word。
BZ/BZW压缩算法中控制掩码的作用是什么？
BZ/BZW通过控制掩码区分明文与引用。以BZ为例，一个控制字节可以标记接下来的8次解码操作，其中每个位表示对应的操作是明文还是引用。
BZ算法对纯明文数据的渐近额外开销是多少？
对于连续的纯明文数据，每8个字节共用1个控制字节，渐近额外开销为1/8，即12.5%。
PRLE和BZ/BZW分别适合压缩什么样的数据？
PRLE适合大片相同颜色、填充值等连续重复值多的数据；BZ/BZW适合文本、结构化数据、重复图案等存在历史重复片段的数据。
为什么说RLE和LZSS没有优劣之分？
因为压缩效果取决于数据分布、引用编码、窗口大小和格式设计。RLE对连续重复值高效，LZSS能利用远距离重复片段，两者服务于不同的数据特征，没有绝对优劣。
