压缩格式和分隔符序列
Compression Formats and Delimiter Sequences
我的问题是:有没有什么标准的压缩格式可以保证压缩后的数据流中不会出现某个定界符序列?
我们想设计一个二进制文件格式,包含大块的顺序数据(3D坐标+其他数据,对问题来说并不重要)。每个块都应使用标准压缩格式进行压缩,例如 GZIP、ZIP、...
因此,文件结构如下:
FileHeader
ChunkDelimiter Chunk1_Header compress(Chunk1_Data)
ChunkDelimiter Chunk2_Header compress(Chunk2_Data)
...
用例如下:文件应该在 Hadoop 中拆分读取,所以我们希望能够从文件中的任意字节位置开始,并通过查找定界符序列。 ->
分隔符序列不应出现在块内。
我知道我们可以 post-process 压缩数据,"escaping" 分隔符序列,以防它出现在压缩输出中。但我们最好避免这种情况,因为解码器中需要 "reverse escaping",增加了复杂性。
我们选择这种文件格式的更多事实:
- 第三方应该易于阅读
->
首选标准压缩算法。
- 大文件;流操作:开始写入文件时不知道数据量和块数
->
难以在 header. 中写入 start-of-chunk 字节位置
我不会用压缩方案名称来回答你的问题,但会提示你其他人是如何解决同样问题的。
让我们来看看 Avro。基本上,他们有类似的要求:文件必须是可分割的,每个数据块都可以压缩(你甚至可以选择你的压缩方案)。
从Avro Specification我们了解到可拆分性是在同步标记的帮助下实现的(对象存储在可以压缩的块中。同步标记用于块之间以允许为 MapReduce 处理高效分割文件。")。我们还发现同步标记是一个16-byterandomly-generatedvalue(16-byte,randomly-为此文件生成同步标记。").
它如何解决您的问题?好吧,由于 Martin Kleppmann 几年前对这个问题提供了很好的答案,我将复制粘贴他的信息
On 23 January 2013 21:09, Josh Spiegel wrote:
As I understand it, Avro container files contain synchronization markers
every so often to support splitting the file. See:
https://cwiki.apache.org/AVRO/faq.html#FAQ-Whatisthepurposeofthesyncmarkerintheobjectfileformat%3F
(1) Why isn't the synchronization marker the same for every container file?
(i.e. what is the point of generating it randomly every time)
(2) Is it possible, at least in theory, for naturally occurring data to
contain bytes that match the sync marker? If so, would this break
synchronization?
Thanks,
Josh
因为如果它是可预测的,它有时会不可避免地出现在实际数据中(例如想象一下 Avro 文档,说明
同步标记是什么,由网络爬虫下载并存储在
Avro 数据文件;然后同步标记将出现在实际
数据)。数据可能来自恶意来源;使标记随机
使其无法被利用。
可能,但极不可能。给定的随机 16 字节字符串出现在拍字节(均匀分布)数据中的概率
大约是 10^-23。您的数据中心更有可能被摧毁
陨石
(http://preshing.com/20110504/hash-collision-probabilities).
如果同步标记出现在您的数据中,它只会在您碰巧也在文件中查找该位置时中断读取文件。如果你只是
按顺序阅读它,没有任何反应。
马丁
Link to the Avro mailing list archive
如果它适用于 Avro,那么它也适用于您。
没有。我知道没有任何标准压缩格式不允许任何位序列出现在其中的某处。否则会(稍微)降低压缩率,违背压缩格式的原始目的。
解决方案是 a) post- 处理序列以使用指定的中断模式并在中断模式意外出现在压缩数据中时插入转义符——这保证有效,但你没有不喜欢这个解决方案,或者 b) 相信宇宙不会密谋反对你,并使用一个长中断模式,其长度确保它不太可能意外出现在所有序列中,从现在到热寂宇宙.
对于 b),您可以通过为每个文件选择随机模式并在文件开头提供随机模式来在一定程度上防止宇宙密谋反对您。对于真正的偏执狂,你可以走得更远,从以前的模式中为每个连续的中断生成一个新的随机模式。
请注意,宇宙 可以 合谋反对你的固定模式。如果您使用固定中断模式制作这些压缩文件之一,然后将 that 文件包含在另一个也使用该中断模式的压缩存档中,则该存档可能无法压缩此文件已经压缩的文件并将简单地存储它,暴露与存档使用的相同的固定中断模式。
b) 的另一种保护是通过查看中断前的片段未终止来检测不正确中断的解压失败,并通过将该片段和后续片段放回一起并尝试处理这种特殊情况再次减压。你也很可能在下面的片段中检测到这一点,解压失败。
我的问题是:有没有什么标准的压缩格式可以保证压缩后的数据流中不会出现某个定界符序列?
我们想设计一个二进制文件格式,包含大块的顺序数据(3D坐标+其他数据,对问题来说并不重要)。每个块都应使用标准压缩格式进行压缩,例如 GZIP、ZIP、...
因此,文件结构如下:
FileHeader
ChunkDelimiter Chunk1_Header compress(Chunk1_Data)
ChunkDelimiter Chunk2_Header compress(Chunk2_Data)
...
用例如下:文件应该在 Hadoop 中拆分读取,所以我们希望能够从文件中的任意字节位置开始,并通过查找定界符序列。 ->
分隔符序列不应出现在块内。
我知道我们可以 post-process 压缩数据,"escaping" 分隔符序列,以防它出现在压缩输出中。但我们最好避免这种情况,因为解码器中需要 "reverse escaping",增加了复杂性。
我们选择这种文件格式的更多事实:
- 第三方应该易于阅读
->
首选标准压缩算法。 - 大文件;流操作:开始写入文件时不知道数据量和块数
->
难以在 header. 中写入 start-of-chunk 字节位置
我不会用压缩方案名称来回答你的问题,但会提示你其他人是如何解决同样问题的。
让我们来看看 Avro。基本上,他们有类似的要求:文件必须是可分割的,每个数据块都可以压缩(你甚至可以选择你的压缩方案)。
从Avro Specification我们了解到可拆分性是在同步标记的帮助下实现的(对象存储在可以压缩的块中。同步标记用于块之间以允许为 MapReduce 处理高效分割文件。")。我们还发现同步标记是一个16-byterandomly-generatedvalue(16-byte,randomly-为此文件生成同步标记。").
它如何解决您的问题?好吧,由于 Martin Kleppmann 几年前对这个问题提供了很好的答案,我将复制粘贴他的信息
On 23 January 2013 21:09, Josh Spiegel wrote:
As I understand it, Avro container files contain synchronization markers every so often to support splitting the file. See: https://cwiki.apache.org/AVRO/faq.html#FAQ-Whatisthepurposeofthesyncmarkerintheobjectfileformat%3F
(1) Why isn't the synchronization marker the same for every container file? (i.e. what is the point of generating it randomly every time)
(2) Is it possible, at least in theory, for naturally occurring data to contain bytes that match the sync marker? If so, would this break synchronization?
Thanks, Josh
因为如果它是可预测的,它有时会不可避免地出现在实际数据中(例如想象一下 Avro 文档,说明 同步标记是什么,由网络爬虫下载并存储在 Avro 数据文件;然后同步标记将出现在实际 数据)。数据可能来自恶意来源;使标记随机 使其无法被利用。
可能,但极不可能。给定的随机 16 字节字符串出现在拍字节(均匀分布)数据中的概率 大约是 10^-23。您的数据中心更有可能被摧毁 陨石 (http://preshing.com/20110504/hash-collision-probabilities).
如果同步标记出现在您的数据中,它只会在您碰巧也在文件中查找该位置时中断读取文件。如果你只是 按顺序阅读它,没有任何反应。
马丁
Link to the Avro mailing list archive
如果它适用于 Avro,那么它也适用于您。
没有。我知道没有任何标准压缩格式不允许任何位序列出现在其中的某处。否则会(稍微)降低压缩率,违背压缩格式的原始目的。
解决方案是 a) post- 处理序列以使用指定的中断模式并在中断模式意外出现在压缩数据中时插入转义符——这保证有效,但你没有不喜欢这个解决方案,或者 b) 相信宇宙不会密谋反对你,并使用一个长中断模式,其长度确保它不太可能意外出现在所有序列中,从现在到热寂宇宙.
对于 b),您可以通过为每个文件选择随机模式并在文件开头提供随机模式来在一定程度上防止宇宙密谋反对您。对于真正的偏执狂,你可以走得更远,从以前的模式中为每个连续的中断生成一个新的随机模式。
请注意,宇宙 可以 合谋反对你的固定模式。如果您使用固定中断模式制作这些压缩文件之一,然后将 that 文件包含在另一个也使用该中断模式的压缩存档中,则该存档可能无法压缩此文件已经压缩的文件并将简单地存储它,暴露与存档使用的相同的固定中断模式。
b) 的另一种保护是通过查看中断前的片段未终止来检测不正确中断的解压失败,并通过将该片段和后续片段放回一起并尝试处理这种特殊情况再次减压。你也很可能在下面的片段中检测到这一点,解压失败。