javascript - 膨胀/解压缩部分 gzip 的算法

Question

我想在 Javascript 中实现部分 gzip 解压缩，即逐 block 膨胀 gzip。类似于 Linux 中的“zcat file.gz | head”。我正在寻找一个好的伪代码。

解压部分gzip的好处是:

1. 无需解压整个大型 gzip 文件即可获得第 1000 行。
2. 无需完成检索整个文件即可查看/分析前 10 行。

根据 this ，一旦我们超过了 gzip 文件头的几个字节，我们就在“压缩 block ”上，我们可以膨胀自己(例如，使用 this inflate algorithm )。

我试过膨胀压缩 block 的几个前字节(即第一个 block ，任何 block 大小)，它成功了!但是，当我拿第二个/第三个 block 时，它没有用。看起来 gzip-inflate 算法在 block 膨胀之前需要几个字节。

问题:确定要扩充/解压缩的 gzip block 的开始和停止字节位置的正确方法是什么？

更新:

[31,139,8,8,222,44,65,84,0,3,118,101,114,97,46,116,120,116,0,172,92,217,114,227,58,140,125,191,95,49,85,19,219,241,110,237,187,68,136,73,232,84,205,211,20,223,231,255,255,98,136,133,178,72,185,251,206,195,168,59,137,183,116,17,34,128,115,112,0,182,250,254,239,255,126,164,69,94,21,183,228,63,126,255,43,73,255,167,72,154,172,77,219,164,77,210,44,107,218,228,145,36,255,153,220,211,127,192,106,208,198,90,99,140,213,218,90,109,141,198,63,214,128,6,0,99,232,53,247,22,224,107,248,142,123,205,253,112,95,248,171,198,0,255,138,123,170,255,57,255,243,252,253,253,125,126,253,254,206,239,175,113,134,89,254,42,112,223,213,172,148,2,247,165,234,94,241,149,224,19,122,241,31,245,178,34,141,173,200,243,226,141,21,90,203,114,44,184,7,110,177,238,57,91,129,230,209,130,181,51,140,22,108,0,112,217,238,85,67,230,186,63,248,25,180,194,25,241,107,12,89,1,193,250,225,245,0,196,14,103,3,208,37,235,87,131,252,44,221,87,54,212,107,43,178,216,138,186,201,82,180,34,13,172,176,160,105,43,220,98,241,31,182,180,104,90,178,123,203,173,148,63,129,47,210,142,128,230,109,113,191,227,126,11,47,103,14,90,97,126,233,114,235,155,112,161,19,200,210,213,200,183,95,205,115,79,207,1,23,13,170,27,217,136,81,165,170,115,134,92,200,20,128,75,122,94,91,145,199,86,84,69,134,70,84,225,86,0,222,95,116,34,205,27,129,14,131,94,130,15,12,26,133,159,68,107,12,25,73,59,65,246,88,254,77,247,174,51,98,248,50,95,198,124,27,190,199,48,184,175,227,4,189,226,91,78,223,239,106,192,187,15,227,212,3,140,254,229,82,85,227,216,186,231,106,68,51,218,161,237,215,70,20,145,17,89,145,21,206,136,52,244,39,203,222,129,222,174,113,15,240,66,199,210,228,92,24,52,228,105,120,239,105,15,208,106,247,58,217,109,157,55,97,96,97,84,60,201,157,126,213,250,154,82,247,109,55,29,31,147,114,247,187,169,6,188,231,170,234,219,214,133,66,62,14,109,94,214,197,227,114,169,93,104,220,149,122,212,215];

上面是我的示例的二进制字符串数组。下面是标题:

[31,139,8,8,222,44,65,84,0,3,118,101,114,97,46,116,120,116,0]

任何以 172 开头的子字符串(紧跟在 header 之后)都可以很好地解压缩/膨胀。但是当子字符串不是来自 172 时，我在解压/膨胀时什么也得不到。也许要膨胀的字符串必须确实来自 172 位置？

Answer 1

您不能从压缩流的中间开始解压缩。至少在之前至少对整个流进行一次解压缩并为随机访问构建索引的情况下是这样。

首先，deflate 格式本质上是串行的。压缩部分是通过查找与先前字符串匹配的字符串来实现的。匹配项可能在您开始之前引用，因此您不知道未压缩的数据是什么。更重要的是，匹配的内容可能本身就是一个匹配项，并且匹配它之前的内容，一直回到文件的开头。

其次，deflate 格式本质上是串行的。它是一种由可变位数的代码构成的格式，没有标记来告诉您代码或 block 或任何内容的开始位置。仅通过查看字节序列中间的某处，无法知道放气 block 从哪里开始。了解 block 从何处开始的唯一方法是解码从压缩流开头开始的所有代码。

为了构建随机访问索引，您需要先解压缩整个内容，然后 a) 保存每个 block 开头的位位置，以及 b) 在每个 block 中保存之前的 32K 未压缩数据点以满足 block 中出现的匹配项(32K 是匹配项的最大距离)。这是一个 example of such code .

没有办法从你以前从未见过的压缩流的中间开始解压缩。