跳转到内容

数据压缩/数据差异化

Add links
来自Wikibooks，开放世界的开放书籍
零频率问题 数据压缩
数据差异化 		字典压缩

数据差异化

[编辑 | 编辑源代码]

数据压缩可以被视为数据差异化的一个特例。[1] 就像数据压缩涉及通常在两台不同机器上运行的两个过程——“数据压缩器”和“数据扩展器”——数据差异化涉及通常在两台不同机器上运行的两个过程——分别为“差异化程序”和“补丁程序”。

一些用于数据差异化的算法和程序与“小窗口压缩”（又称传统数据压缩）中使用的算法非常相似——例如“大窗口压缩”（又称“数据折叠”[2]）——而另一些则非常不同——例如“数据重复数据删除”[3][4]和rsync算法。

一些用于大型文件传统数据压缩的算法类似于数据差异化算法——例如在霍夫曼：存储频率表中描述的存储许多霍夫曼频率表的某些技术。

为数据差异化开发的一些算法和程序包括

  • diff（“w:增量压缩”）
  • rsync
  • rdiff
  • lzip
  • rzip
  • IZO（信息压缩优化器）[2]
  • xdelta[5]
  • bsdiff 4和bspatch[6]
  • bsdiff 6和Percival的通用增量压缩器[6][7]

对于其他形式的压缩，更多信息通常会带来更好的压缩效果。但是，Factor、Sheinwald和Yassour在2001年的实验似乎表明，当使用类似LZ77的压缩进行数据差异化时，尝试使用大量类似于目标文件的共享文件通常会比使用该集合中的单个参考文件产生更差的压缩效果。[8]

预加载字典

[编辑 | 编辑源代码]

在压缩非常大的文件时，字典的预加载内容通常不会有太大区别，因此许多系统从空字典开始。

但是，在两种情况下，预加载字典可以生成明显更小的文件

  • 压缩大量短字符串时，或
  • 进行数据差异化时——压缩某个与接收方已有的某个文件几乎相同的大文件。

一些数据压缩算法的实现已经支持预加载字典。

  • 流行的zlib压缩库支持deflateSetDictionary()和inflateSetDictionary()函数来预加载字典。[9]


一种可能的数据差异化方法涉及调整某些压缩算法以“预加载”其内部数据结构（其“窗口”或“字典”）来自我们已经拥有的文件的数据，以允许压缩算法使用这些数据来（希望）在下一个文件上获得更好的压缩效果。[10][11]

例如，IPSW算法（Shapira和Storer的原地滑动窗口）将类似LZ77的解压缩器的源滑动窗口初始化为某个共享文件S，[8]允许目标文件T的公共子字符串从S中复制出来，以及（像其他类似LZ77的压缩器一样）允许重复的子字符串从目标文件T先前解压缩的部分复制，或者如果所有其他方法都失败，则从压缩文件中的文字值复制。

有时，此类“预加载”实现使用未修改的“小窗口压缩”算法，如美国专利RE41152 2010中所述。许多早期的压缩算法使用“静态字典”（Huffword、PalmDoc等）预加载字典。LZW算法比非常类似的LZ78算法提供更好的压缩效果。关于LZW的一种思考方式是，想象一下256个文字字节值不是一个单独的“特殊情况”，而是实际上预加载到字典中；而LZ78算法实际上是从空字典开始，因此压缩效果较差。

对于许多压缩算法，此类预加载受“窗口”或“历史限制”的限制——当窗口或限制为，例如，32 kByte时，无论尝试预加载什么或多少数据，只有最后32 kByte才会产生任何影响。

这导致一些从事数据差异化工作的人使用比其他压缩研究人员大得多的窗口或历史限制。

窗口大小

[编辑 | 编辑源代码]

LZ77风格的解压缩器有一个固定大小的“窗口”，用于存储最近解压缩的文本，“复制引用”只能引用该窗口内的文本。

从理论上讲，许多压缩算法没有固有的“历史限制”——例如LZ78风格的算法和自适应霍夫曼算法。但是，在实践中，大多数压缩算法的实现都会定期重置其字典并从头开始。因此，它们具有字典重置之间最大文本长度的块大小。

对于许多早期的压缩算法，提高性能的一种简单方法是增加窗口大小。（即，对于LZ77算法，从字面上增加“窗口”缓冲区，或者对于LZ78风格的算法，简单地减少字典重置频率）。这些早期的压缩算法通常是在内存远小于现代机器的机器上开发的，因此“窗口大小”、“重置频率”和“内部字典大小”都受到此限制。（这些早期机器的运行速度也远低于现代机器，并且许多算法——例如LZRW系列算法——受到这些速度限制的严重约束；目前尚不清楚这对字典大小有何影响）。

为简单起见，我们将考虑将窗口大小加倍对各种算法的影响。原始的“小窗口”算法具有一定的固定窗口大小W，而加宽的“大窗口”算法具有一定的固定窗口大小2*W，可以将其视为“近窗口”，其中包含与小窗口算法相同的所有内容，以及“远窗口”，其中包含小窗口算法无法访问的内容，但也许大窗口算法可以利用这些内容来获得更好的压缩效果。

唉，增加窗口大小会带来收益递减。实际上，几乎总存在某种数据相关的“最佳”窗口大小。将窗口大小增加到最佳值以上会导致更差的压缩效果（压缩文件更大）。

窗口大小大于最佳大小会产生负面影响的原因有4个

1. 一些LZ77风格的算法使用固定长度的线性偏移。将窗口大小加倍必然会使每个复制项的长度增加1位。对于典型的16位复制项，除非压缩器可以在远窗口中找到比近窗口中任何字符串都长的匹配字符串，否则这会使压缩文件长度增加17/16倍（压缩效果更差）。

2. 其他LZ77风格的算法使用可变长度的偏移。通常，更远的偏移量更长。将窗口大小加倍通常会使“极其接近”的复制项的长度保持不变，将近窗口外边界附近的一些复制项的大小增加1位，并需要更大的复制项才能引用远窗口中的内容。因此，与类别（1）相比，增加窗口大小对类别（2）几乎没有惩罚。但是，收益并不那么好。在许多情况下，即使远窗口中存在一个非常好的长匹配，其长度超过近窗口中的任何匹配，它也不会使压缩文件变小——引用该远处匹配字符串所需的较长复制项可能与可以从近窗口中的两个位置重新组合相同字符串的两个较短复制项的长度相同甚至更长。

3. 正如Jeff J. Kato等人所指出的那样，[12] 当尝试压缩具有略微不同特征的数据，或尝试压缩特征从一部分到另一部分发生变化（“发展”）的文件时，窗口/字典中存在一种文件的数据甚至可能适得其反。通常最好重置字典并从头开始。

但是，有时这些“大窗口”压缩器具有很大的优势——特别是当我们目前尝试压缩的文件不仅仅是相同类型的文件，而是与某个早期文件完全相同。当文件*大部分*相同并且只有少量编辑时，一些大窗口技术也能很好地工作。

一些压缩软件的默认窗口大小或块大小为

  • gzip：32 kByte滑动窗口
  • bzip2：900 kB的块

  • DEFLATE（如用于“.zip”、“.jar”、“.png”等）：32 kByte 滑动窗口
  • GIF 标准提到了两种 LZW 编码器
    • 一些 GIF 编码器实现会在字典每次填满时重置字典——

即，压缩器在每 (最大字典大小 - 硬编码条目数) = 2048 - (256 + 2) 个压缩符号后发送“清除代码”来重置字典。

    • 所有 GIF 解码器都必须支持“延迟清除”。如果压缩器使用这种“延迟清除”，则许多图像可以存储在更小的 .gif 压缩文件中。[13][14][15]

）。GIF LZW 编码器在字典填满后变得不适应，同时它正在“等待”下一个清除代码。

http://en.wikipedia.org/wiki/xdelta


  1. ↑

    维基百科 有相关信息在 数据差异化

    w:数据差异化
  2. ↑ a b http://static.usenix.org/event/lisa08/tech/full_papers/smith/smith_html/
  3. ↑ Dutch T. Meyer 和 William J. Bolosky。 "实用重复数据删除研究"。
  4. ↑ 维基百科：重复数据删除
  5. ↑ http://code.google.com/p/xdelta/
  6. ↑ a b “通过使用后缀排序（特别是 Larsson 和 Sadakane 的 qsufsort）并利用可执行文件如何更改，bsdiff 通常生成的二进制补丁比 Xdelta 生成的补丁小 50-80%，比 .RTPatch 生成的补丁小 15%……一个更复杂的算法，通常提供大约 20% 更小的补丁，在我的博士论文中进行了描述。”——Colin Percival。 "二进制差异/补丁实用程序"
  7. ↑ Colin Percival。 "匹配与不匹配及相关应用"。论文。2006 年。
  8. ↑ a b Dana Shapira 和 James A. Storer。 "就地差分文件压缩"。2005 年。
  9. ↑ http://www.gzip.org/zlib/manual.html#deflateSetDictionary http://www.gzip.org/zlib/manual.html#inflateSetDictionary
  10. ↑ "压缩算法能否在文件集上“学习”并更好地压缩它们？"
  11. ↑ comp.compression：“在解压缩时保证可用的一组数据文件”
  12. ↑ Jeff J. Kato、David W. Ruska、David J. Van Maren。美国专利 4847619 "基于性能的数据压缩字典重置"。1987 年。
  13. ↑ Attila Tarpai。 "GIF 中的延迟清除代码"。2010 年。
  14. ↑ "GIF89a 规范封面：LZW 压缩中的延迟清除代码"
  15. ↑ GIF 文件格式：可移植性警告 2：延迟清除代码问题


零频率问题 数据压缩
数据差异化 		字典压缩
检索自“https://wikibooks.cn/w/index.php?title=Data_Compression/data_differencing&oldid=3813688”
华夏公益教科书