为什么LZ77实现不同？

Question

我试图找到LZ77的正确实现，这是1977年论文中最初的著名算法。我所发现的是许多不同的实现，它们产生不同的输出，但仍然被标记为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. br/lz77 77/demo.html (JS，742 > 658字节-输出中包含可读的ASCII )
6. Github.com/olle/lz77kit/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只提供了算法本身的一般数学概念。它是灵活的，因为它的参数可以被改变，导致对编码器和解码器的不同的要求，并且可以极大地影响最终的数据流。现在由实现来决定这些细节，比如缓冲区的大小和码字的构造方式。这些参数的敏感性就是为什么相互竞争的实现可能称自己为LZ77，但不兼容。

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

这种自由带来了其他方式的创新，比如LZSS引入文字标志，或者LZRW使用哈希表。另一个流行的创新是后续的基于LZ的压缩(如在泄气中)或另一个熵编码器，以提高压缩比。