问题标签 [lz77]

我正在制作自己的 DEFLATE 压缩器，它几乎每次都击败了 ZLIB 库。

在 DEFLATE 格式 (LZ77) 中，数据流要么包含一个字节文字，要么包含一个反向引用，即我们应该从先前解码的字节中复制一个字节序列。压缩器通常执行 LZ77（查找反向引用 - 尽可能多），然后构建一个霍夫曼树并压缩该字节/引用流。

可能有一个极端情况：3个相同字节的引用，长度由15位编码，距离由15+13位编码，而编码字节在我们的霍夫曼树中只有1位。区别是 43 对 3 位。使用参考使输出比直接编码字节大 14 倍。

我的问题如下：我有一个 10,097,918 B 的文本文件。ZLIB 在它的 LZ77 中引用了 9,089,334 B，而我的压缩器覆盖了 9,305,056 B。所以我想我可以说我的 LZ77 更好。

但是 ZLIB 给出了一个 1,329,309 B 的文件，而我的程序给出了一个 1,381,153 B 的文件（两者都构建了一个最优的 Huffman 树）。因此，更好的 LZ77 会导致更差的霍夫曼编码。有没有关于霍夫曼友好型 LZ77 的研究？

我需要解压缩嵌入在 xlsx 文件中的数据模型文件。该文件应该使用 MS-XLDM 文件格式，应该由 3 个部分（电子表格数据模型头、文件和虚拟目录）组成，只有中间一个被压缩。第一个和最后一个部分是 xml 与 unicode/utf-16 编码大概（每隔一个字节是 0x00 并且内容前面是 0xFF 和 0xFE ）。中间文件前面是一小块 xml。有关文件结构的更多详细信息。

现在根据文档，应该使用此处指定的 Xpress 压缩来压缩文件，该压缩使用 LZ77 压缩和 DIRECT2 编码。

现在进入正题。据我了解，应该总是有一个 4 字节的位掩码，指示相应位置的字节是否应该是 1:1 数据或元数据。

例如，给定一个假设的 8 位位掩码，字符串“ABCABCDEF”被压缩为 (0,0)A(0,0)B(0,0)C(3,3)D(0,0)E( 0,0)F。它的位掩码是 b'00010001' (0x11)。

如果给定位置应该是元数据，则至少应读取 2 个字节。在 16 位中，前 13 位是偏移量，后 3 位是长度（除非最后一位是 1，否则必须读取另一个字节）。

所以现在到我挣扎的具体例子。前 2 块很容易。

第一个是：

前 4 个字节（点）是 0x00，因此后面的 32 个字节是未压缩的。下一个块是相似的：

现在第三块是我迷路的地方

我不确定该块到底在哪里结束，因为当我开始在第一个字节之后每 36 个字节计数一次时，我会到达应该未压缩的字节流的一部分并且它没有对齐。

所以回到第三块。这个的位掩码是0x77 0xB1 0x04 0x01。

或二进制01110111 10110001 00000100 00000001。我试图将它与字节对齐，但这没有任何意义。显然“引擎”这个词是未压缩的，它适合前面的块，因为快速的谷歌搜索向我显示了一个带有命名空间“ http://schemas.microsoft.com/analysisservices/2003/engine ”的结果。

这让我觉得如果位掩码是相反的顺序，可能是字节。这对我来说更有意义。

如果这是真的，那么元数据应该是0x0B 0x02。

或二进制00001011 00000010。因此，如果我将其拆分，前 13 位构成元数据的偏移量。长度为 010 +恒定偏移量3 = 2+3=5。

但是向后看 353 个字节，它位于未压缩的分区 xml 部分，应该返回括号中的字符（ame）。这对我来说没有意义，而且可能是错误的。

这是我尝试解压缩的文件。

我为超级晦涩的压缩格式编写了一个 Java 压缩器。（它主要用于 1990 年代的 Amiga 计算机）。

关于如何解压缩文件格式有大量的文档，但没有关于实际如何压缩它的文档。

所以，我试着自己做。它有效，但有一个问题。在“低强度设置”下，我需要 42 秒来压缩我想要压缩的所有文件。在较高强度设置下大约需要 10 倍的时间。

我相信它可以比这快得多。

它基本上是 Lz77 滑动窗口的变体。

真正的瓶颈是寻找要压缩的现有事件。现在，我正在使用一个Map<Byte, List<Integer>>（这List<Integer>是字节所在的所有索引。）

要找到潜在的匹配项，它的作用是：

它采用被压缩文件的当前索引。它List<Integer>从 Map 中获取当前索引处的字节。

它通过使用该列表找到文件中已经出现的最长的字节子列表，并检查它们匹配多长时间。

我认为更好的数据结构可以显着加快这一速度，但我被困在这一点上。

我必须处理的限制之一是，由于该程序的用途，我需要严格遵守这种古老的压缩格式。

如何优化压缩而不降低打包数据的效率？

主要瓶颈代码：

由以下人员调用：

完整代码在这里供任何需要它的人使用。

我想压缩.txt包含yyyy-mm-dd hh:mm:ss格式日期和有时倾向于在不同行中重复的英文单词的文件。
我阅读了一些关于压缩算法的文章，发现在我的情况下，基于字典的编码比基于熵的编码更好。因为我想自己实现算法，所以我需要一些不是很复杂的东西。所以我关注了LZW和LZ77，但无法在它们之间进行选择，因为我发现的文章的结论是矛盾的。根据一些文章，LZW 具有更好的压缩比，而根据其他人的说法，领导者是 LZ77。所以问题是在我的情况下哪一个最有可能会更好？是否有更易于实现的算法对我的目的有益？

我正在对 Gameboy Advance 的游戏进行逆向工程，我注意到原始开发人员编写的代码有两个系统调用来使用 Huffman 和 lz77（按此顺序）解压缩关卡。

但是为什么要使用霍夫曼+ lzZ7？这种方法有什么好处？

我正在分解由 NiceLabel 标签制作软件生成的 ZPL 标签定义。在大多数情况下，我不必担心解码 Z64，因为它只是编码的图形，我不需要更改底层数据。

但是，由于某种原因，可能由于字体或其他原因，我有一行文本被标签用作图形。

无论如何，Z64 或 ZB64 字符串是通过使用 LZ77 压缩原始数据并将其编码为 Base64 然后在末尾附加一个 CRC 来创建的。

测试字符串完整示例：

测试字符串目标示例：

我要解码/解压缩的代码：

当前例外：

堆栈跟踪：

更新：

我正在研究这个，我发现这个SO 帖子本质上是同一个问题。所以我做了更多的研究，我在 2007 年的博客上找到了这篇文章。其中讨论了一种解决方法，即跳过输入数组中的前 2 个字节，因为这些字节实际上并未包含在 RFC 规范中。

代码更改：

此代码更改实际上不再产生异常，但是它没有正确解压缩并返回以下结果：

我试图找到 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 字节！！）

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

我用来压缩的文本：

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

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

所以，我正在编写 LZ77 压缩算法。以下是程序要求：

• 程序应压缩任何未压缩的文件（.txt、.bmp 等）
• 基于上述，程序应该使用二进制

现在事情开始对我来说有点不清楚，所以我需要一些建议。以下是我对这个问题的看法：

输入文件应以std::ios::binary. 下一个是什么？为方便起见，我认为将二进制作为字节使用是最佳的，对于我正在使用的字节解释chars（因为 1 char 等于 1 字节，如果我没记错的话）。因此我将文件数据作为字节（chars）读取到细绳。string现在我可以使用算法对这个字节进行编码。编码的输出是三元组向量. 现在我需要将此输出数据解释为字节以保存到压缩文件中，对吗？因为offset和length是ints，所以我需要将它们分成字节（chars）以将它们写入输出二进制流（因为ofstream::write争论是 char* 和要插入的字符数（字节））。nextchar可以按原样写。对于解码，我将步骤颠倒过来：从文件中读取三元组字节，然后使用算法进行解码。

我错过了一些重要的东西吗？在这种情况下使用字节是否正确？有什么错误的逻辑吗？下面是一些代码：

我正在编写 LZ77 压缩算法，并且无法将无符号字符存储在字符串中。为了压缩任何文件，我使用它的二进制表示，然后将其读取为chars（因为 1 char 等于 1 字节，afaik）到std::string. 一切都很好用chars。但经过一段时间的谷歌搜索后，我了解到这char并不总是 1 字节，所以我决定将它换成unsigned char. 事情开始变得棘手：

• 压缩纯 .txt 时，一切都按预期工作，我在解压缩之前和之后得到相等的文件（我认为应该是这样，因为我们基本上在字节转换之前和之后处理文本）
• 但是，当尝试压缩 .bmp 时，与输入文件相比，解压缩文件会丢失 3 个字节（尝试将无符号字符保存到 std::string 时会丢失这 3 个字节）

所以，我的问题是——有没有办法将无符号字符正确保存到字符串中？

我尝试使用typedef basic_string<unsigned char> ustring所有相关函数并将其交换为使用 with 的基本替代方法unsigned char，但我仍然丢失了 3 个字节。

更新：我发现丢失 3 个字节（符号）不是因为 std::string，而是因为std::istream_iterator（我使用而不是std::istreambuf_iterator）来创建无符号字符的字符串（因为std::istreambuf_iterator的参数是 char，而不是无符号字符）

那么，有没有解决这个特定问题的方法？

例子：

示例代码：

我正在尝试解码使用 LZX 算法编码的字符串，其 LZX 窗口大小为 2 兆字节（二进制），然后转换为 base64。

我从 Microsoft 的更新 API ( GetUpdateData ) 收到此字符串作为响应。根据lzx/lz77 算法的Microsoft 文档，该XmlUpdateBlobCompressed字段为：

使用 Lempel-Ziv 压缩算法的 LZX 变体进行压缩。用于压缩该字段的 LZX 窗口大小为 2 兆字节。

我尝试将字符串解码/解压缩回其原始 XML，但没有成功。我尝试了lz_string库（NodeJS/Ruby）和其他一些库，但到目前为止没有成功。

这是我尝试解码/解压缩回原始 XML 的示例：

有没有人成功做到这一点？