问题标签 [lz77]

我试图在 LZ77 算法（源代码：http ://www.zlib.net/）中找到两个参数（滑动窗口大小和最大匹配长度），以分析不同级别的压缩。一开始我发现zpipe.c中的CHUNK值是最大匹配长度参数，滑动窗口是deflate.c中函数deflateInit2中的参数windowBits问题是不同压缩级别的压缩文件根据无论参数如何，这些参数都是相同的。

如果有人使用了这个源代码并且已经在代码中识别了这些参数，那对我很有帮助。

谢谢！

我了解 LZ77 和 LZ78 算法。我在这里和这里阅读了 LZ4并找到了它的代码。

这些链接描述了 LZ4 块格式。但是，如果有人可以解释（或引导我到一些资源解释），那就太好了：

• LZ4与LZ77有何不同？
• LZ4HC 与 LZ4 有何不同？
• 是什么想法让 LZ4HC 算法这么快？

我有兴趣实现 LZ 算法来压缩 ECG 信号，并希望优化与微控制器相关的代码。

这样它的熵效率就会降低，压缩和解压缩心电信号所需的时间也更少。我完全不知道我是如何实现这一目标的。我对任何编程语言都持开放态度。

我在网上搜索了源代码，发现代码很长，很难在​​短时间内理解。

有什么建议...？

背景：我在 C++ 上实现了一个通用 LZSS 后端（可在此处获得。我在这个版本中使用的匹配算法非常简单，因为它最初是为了压缩相对较小的文件（最多 64kB），用于相对古老的硬件（特别是，Mega Drive/Sega Genesis，其中 64kB 是整个主 RAM）。

然而，在我的实现中，一些文件的压缩时间太长了，大约几分钟。原因有两个：天真的匹配算法花费了大部分时间，但这特别是因为我从文件中构造了一个压缩图以实现最佳压缩。查看分析器，大部分时间都花在寻找匹配上，甚至使结果图的二次大小相形见绌。

一段时间以来，我一直在研究几种可能的替代品；引起我注意的是使用多层后缀树的字典符号灵活解析。多层部分很重要，因为我感兴趣的 LZSS 变体之一对（位置、长度）使用可变大小的编码。

我当前的实现允许滑动窗口中的匹配项与前瞻缓冲区重叠，因此该输入：

可以直接编码为

代替

这里，(0,'a') 表示将字符“a”编码为文字，而 (1,n,m) 表示“从位置 n 复制 m 个字符”。

问题：说了这么多，这是我的问题：我在后缀树上找到的每个资源似乎都暗示它们无法处理重叠的情况，而只允许您找到不重叠的匹配项。当涉及到后缀树时，研究论文、书籍甚至一些实现都给出了没有重叠的压缩示例，就好像它们是完美的压缩一样（我会链接到其中的一些，但我的声誉不允许这样做）。他们中的一些人甚至提到在描述基本压缩方案时重叠可能很有用，但在讨论后缀树时却奇怪地沉默了。

由于无论如何都需要扩充后缀树以存储偏移信息，因此这似乎是一个可以在查找匹配项时检查的属性——您将过滤掉从前瞻缓冲区开始的任何匹配项。并且树的构造/更新方式意味着，如果一条边将您带到与从前瞻开始的匹配对应的节点，则您将返回前一个节点，因为任何进一步的后代也将在前瞻中缓冲。

我的方法是错误的还是不正确的？是否有 LZ77/LZSS 的实现或讨论，其后缀树提到匹配与前瞻缓冲区重叠？

我有大量的原始字节。字节数组不遵循任何模式，字节值可以是任意值（随机）。数组的大小为 45000x5x400 字节。我有 1 秒的时间进行编码。lz77可行吗？我应该如何选择查找字典？还有什么是保存相对索引和匹配长度的比特数的好选择？

我正在使用 ZLIB 压缩几个长字符串，它在使用 Huffman 树对这些表示进行编码之前使用重复子字符串的 LZ77 表示。我对研究整数元组表示本身的序列很感兴趣，并且一直在查看代码以找出这些表示在哪里生成以及如何将它们一个接一个地打印出来。不幸的是，我的 C 语言不是很强，而且压缩器似乎将距离处理为指针，而不是整数。有人可以告诉我是否有一种简单的方法可以在算法运行时打印出元组序列，并将我指向代码中的适当位置。

为什么 LZ77 DEFLATE 在第二遍使用 Huffman 编码而不是 LZW？他们的组合有什么是最佳的吗？如果是这样，LZ77 输出的本质是什么，使它比 LZW 或其他一些方法更适合 Huffman 压缩？

我想了解这个基于 LZSS 的算法，以便编写一个压缩器（也许是一个更好的解压缩器），我正在研究 LZ77 和 LZSS，但我仍然没有得到几行代码。

我尽可能多地注释了以下代码，第一个注释块不是我制作的，而是解释了标题。

回顾一下，为什么原作者以这种方式使用 nbits 值？

为什么使用这些常数和 nbits 的移位？

谢谢

您能否在下图中的示例中解释如何从 lz77 转换为霍夫曼？

我阅读了有关 gzip 压缩和 png 图像压缩的信息，它们都使用 DEFLATE 算法，但我不确定该算法的实现是否相同。此外，如果它是相同的算法，那么除了 png 压缩在 DEFLATE 之前使用 delta 过滤这一事实之外，这些压缩之间有什么区别？