language-agnostic - 为什么 LZ77 实现不同？

Question

我正在尝试找到 LZ77 的正确实现，LZ77 是 the 1977 paper 中的原始著名算法。 .我发现许多不同的实现产生不同的输出，但仍然标记为 LZ77。例如，一些使用哈希表，一些在更“官方”的算法中使用的东西，如 LZRW 或 LZJB。所以我很困惑。

我测试过的一些实现:

1. https://gist.github.com/fogus/5401265 (C，742 > 538 字节，哈希表？输出困惑)
2. https://sourceforge.net/projects/crush (C++，742 > 508 字节，哈希表？输出困惑)
3. https://github.com/cstdvd/lz77 (C，742 > 642 字节——在输出中包含可读的 ASCII)
4. http://lab.polygonpla.net/js/tinylz77.html (JS，742 > 863 字节!! -- 在输出中包含可读的 ASCII)
5. http://geocities.com/diogok_br/lz77/demo.html (JS，742 > 658 字节——输出中包含可读的 ASCII)
6. github.com/olle/lz77-kit/src/main/js/lz77.js (JS，742 > 639 字节——输出中包含可读的 ASCII)
7. https://github.com/Favrito/LZ77 (C，742 > 755 字节!!)

据我所知，没有人使用任何后处理编码，例如 Huffman 等

我用来压缩的文本:

Oho! Oho! Rise up, O Teti!
Take your head, collect your bones,
Gather your limbs, shake the earth from your flesh!
Take your bread that rots not, your beer that sours not,
Stand at the gates that bar the common people!
The gatekeeper comes out to you, he grasps your hand,
Takes you into heaven, to your father Geb.
He rejoices at your coming, gives you his hands,
Kisses you, caresses you,
Sets you before the spirits, the imperishable stars...
The hidden ones worship you,
The great ones surround you,
The watchers wait on you,
Barley is threshed for you,
Emmer is reaped for you,
Your monthly feasts are made with it,
Your half-month feasts are made with it,
As ordered done for you by Geb, your father,
Rise up, O Teti, you shall not die!

它们都有不同的输出流。是否没有可供检查的 LZ77 的纯引用实现或标准？

为什么不是所有“LZ77”压缩器都提供相同的压缩比、相同的输出比特流？

Answer 1

没有一种特定的方法来实现 LZ77

LZ77只提供了算法本身的一般数学概念。它的灵 active 在于它的参数可以改变，从而对编码器和解码器产生不同的要求，并且可以极大地影响结果数据流。由实现来决定这些细节，例如缓冲区的大小和代码字的构造方式。这些参数的敏感性是竞争实现可能自称为 LZ77 但不兼容的原因。

例如，DEFLATE specification指定 32768 的窗口大小，并将位置和长度存储为 15+8 位码字。一个更简单但效率较低的实现可以选择 12 位距离和 4 位长度，给出 4096 字节的窗口大小。另一种可能选择 8192 字节的窗口大小，使用 13 位来表示距离，如果要使用每个 token 16 位，则只留下 3 位的长度。

这种自由导致了其他方面的创新，例如引入文字标志的 LZSS，或使用哈希表的 LZRW。另一个流行的创新是使用 Huffman coding 跟进基于 LZ 的压缩。 (如在 DEFLATE 中)或其他熵编码器以提高压缩率。