2

我试图找到 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 bytes!! -- 输出中包含可读的 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 字节！！）

据我所知，没有人使用任何后处理编码，如霍夫曼等。

我用来压缩的文本：

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”压缩器都提供相同的压缩比、相同的输出比特流？

4

1 回答 1

6

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

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

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

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

于 2019-11-25T05:11:43.407 回答