大数据压缩:类型与技术

\

简介

本文将讨论大数据背景下的压缩,涵盖压缩的类型和方法。我也会强调每种类型和方法应在何时以及为何使用。

\

什么是压缩?

根据压缩的一般英语定义,它是指减少某物占用的空间。在计算机科学中,压缩是将数据缩减到更小尺寸的过程。在这种情况下,数据可以用文本、音频、视频文件等表示。可以将其视为您存储在计算机硬盘上的任何内容,以不同格式表示的数据。提供一个更技术性的定义,压缩是对数据进行编码以使用更少位元的过程。

\ 压缩数据有多种原因。最常见和直观的原因是节省存储空间。其他原因是数据变小的结果。处理较小数据的好处包括:

1. 更快的数据传输时间:压缩数据体积更小,从源到目的地的传输时间更短。
2. 减少带宽消耗:这个原因与更快数据传输的优势密切相关。压缩数据使用较少的网络带宽,因此增加吞吐量并减少延迟。
3. 改善严重依赖数据的数字系统的性能:这在依赖处理数据的系统中很明显。这些系统利用压缩通过减少需要处理的数据量来改善系统性能。请注意,这可能是特定于系统的,并且将依赖于使用适当的压缩技术。压缩技术将在本文后面讨论。
4. 成本效益:云服务对数据存储收费。通过使用较少的存储空间,可以节省成本,特别是在大数据系统中。

\ 压缩的其他原因取决于不同的压缩技术和格式。某些加密算法可以用作压缩方法。这样做时,它为前面讨论的压缩数据的原因增加了一层安全性。此外,使用常见的压缩格式带来了兼容性和可扩展性空间,以便与外部系统集成。

\ 值得注意的是,压缩的原因听起来也像好处。然而,压缩并非没有权衡。压缩的一个常见权衡是需要解压缩,这对于资源受限的系统可能是一个问题。其他权衡取决于所使用的压缩技术和数据类型。

\

压缩类型

为了讨论用于压缩数据的不同技术,我将首先将压缩分为2个主要类别。然后本文将讨论与每个类别相关的技术。压缩可以大致分为 有损 和 无损 压缩。

\ 正如名称已经揭示了它们的含义, 有损压缩 技术是不保留数据完整保真度的技术。简单地说,一些数据被丢弃,但不足以使数据所代表的内容无法识别。因此,与无损压缩相比,有损压缩可以提供非常高的压缩级别,无损压缩将很快介绍。

\ 有损压缩的一个特征是它是不可逆的,即当呈现压缩文件时,无法以原始保真度恢复原始数据。某些文件和文件格式适合有损压缩。它通常用于图像、音频和视频。例如,JPEG格式的图像非常适合压缩,通过压缩JPEG图像,创建者或编辑者可以选择要引入多少损失。

\ 另一方面, 无损压缩 是可逆的,意味着压缩时,所有数据都被保留并在解压缩期间完全恢复。这意味着无损压缩适合类似文本的文件,在数据仓库和湖仓世界中,它将是唯一相关的类型。一些音频(FLAC和ALAC)和图像文件(GIF、PNG等)格式与这种压缩类型配合良好。

选择方法

没有普遍最佳的压缩方法。选择哪种方法适合需要根据具体情况考虑不同因素。举例说明,金融行业中处理表格数据存储的数据工程师会倾向于使用无损压缩,因为缺失数据会影响创建准确报告。或者,有损压缩可能是优化包含大量图像的网页的方法,通过压缩图像并减少加载项来使网站更轻。因此,进行评估以确定与业务需求一致的最合适压缩方法至关重要。

压缩技术

本节将只涵盖有损和无损压缩的常见压缩技术。请注意,这绝不是详尽无遗的。此外,所讨论的技术可能有细微变化以增强其性能,这得到了不同研究的支持。

无损压缩技术

三种常见的无损技术是行程长度编码(RLE)、霍夫曼编码和Lempel-Ziv-Welch技术。

\ 行程长度编码:RLE基于编码数据,使其用单个数据片段和该数据片段的计数替换重复数据序列。它对长串重复数据有效。此外,具有从低基数级别到高基数级别排序的维度(字段)的数据集受益于RLE。

\ 例如,取一个简单的字符串如 AAAAABBCDDD。RLE将数据压缩为 A(5)B(2)C(1)D(3)。更实际地说,看下图中的表格。

\ 图1 - RLE之前。重要的是要观察到基数级别从左到右在字段上增加

图2 - RLE之后

因为RLE依赖于重复字段的运行,在第二个示例中,基数和数据的排序顺序,项目列上的 Mouse 记录不能仅压缩为 Mouse (3),因为前面的列将所有值分为 IT, Mouse 和 HR, Mouse。某些文件格式与RLE兼容,例如位图文件格式,如TIFF、BMP等。Parquet文件也支持RLE,使其在使用S3或GCS等对象存储的现代数据湖仓中非常有用。

\ 霍夫曼编码:它基于统计建模,根据原始数据中值出现的频率为其分配可变长度代码。这种建模的表示可以称为霍夫曼树,类似于二叉树。然后使用此树为原始数据中的每个值创建霍夫曼代码。该算法优先使用尽可能少的位元对最频繁的值进行编码。

\ 让我们使用RLE示例中使用的相同数据 AAAAABBCDDD。相应的霍夫曼树如下所示。

\ 霍夫曼树

从树中,我们可以看到字母 A 由 0 表示,同样 D 由 10 表示。与字母 B: 111 和 C:110 相比,我们观察到A和D由更少的位元表示。这是因为它们具有更高的频率;因此,霍夫曼算法通过设计用更少的位元表示它们。压缩后的数据变为 00000111111110101010。

\ 霍夫曼编码使用 前缀规则, 该规则规定 表示字符的代码不应出现在任何其他代码的前缀中。例如,有效的霍夫曼代码不能使用 C: 00 和 D: 000 表示字母c和d,因为 C 的表示是 D 的前缀。

\ 要实际看到这一点,计算机科学领域指南有一个 霍夫曼树生成器 您可以使用。

\ Lempel–Ziv–Welch编码:它由Abraham Lempel、Jacob Ziv和Terry Welch于1984年创建,显然是以创建者的名字命名的😅。与RLE和霍夫曼编码类似,LZW适用于包含大量重复数据的数据。LZW算法基于字典,创建一个包含原始数据中常见模式的键值对的字典。这样的字典也可以称为代码表。使用示例来解释这种技术的工作原理,让我们将原始数据表示为 ABBABABABA。当使用A-Z作为可能值的配置通过算法时,生成的代码表如下所示:

\ LZW代码表

从上面的代码表中,所有字母A-Z都有一个键值对,以及AB、BB、BA和ABA等模式的键值对。通过对这些模式进行更短的表示,LZW算法可以通过将其编码为更少的位元来压缩原始数据。因此,使用从该输入生成的代码表,压缩版本是 0 1 1 26 29 28。注意压缩数据中的空格是关键。可以将它们视为字符的结尾,因此解码器不会将 1,0 解释为 10,因为它们意味着不同的事物。

\ LZW通常是通用的,今天被广泛使用。它集成在许多基于Unix/Linux的操作系统的 compress shell命令后面。此外,与LZW兼容的常见文件格式是GIF、TIFF和PDF。LZW压缩的其他应用可以在自然语言处理领域看到,如本文关于 NLP中的标记化 的讨论。

\ RLE、霍夫曼编码和LZW编码只是常见的例子。无损压缩技术超越了上述三(3)种。其他技术包括 DEFLATE, 它使用霍夫曼和LZW的组合 - 特别是LZ77 - 编码。

有损压缩技术

在本节中,我们将研究两种类型的有损压缩。回想一下,有损压缩会对原始数据引入损失,这意味着不是所有数据都被保留。

\ 离散余弦变换(DCT):这种压缩方法主要用于音频、图像和视频文件,也通常称为块压缩。它使用数学函数 - 如名称所示的余弦函数 - 将原始数据块转换为频率。数据块通常是8x8、4x4等的矩阵,按该数量级顺序。

\ 一旦使用数学函数将原始数据转换为频域,压缩就会在处理数据中出现的高频时发挥作用。使用DCT进行压缩的整体过程是:

• 将原始数据分解为块。例如,在图像压缩中,这可能是8x8像素。
• 应用数学函数将数据块转换为频率。这将导致一些高频和低频。
• 然后根据愿意引入的可接受损失程度减少或删除高频。这就是它真正成为有损压缩的地方。
• 要转换回可表示的数据,所有剩余频率都通过逆离散余弦变换 - IDCT - 从频率恢复数据。

\ DCT今天在不同领域广泛使用,不仅在压缩中,而且在信号处理中。与DCT兼容的常见文件格式是JPEG(图像)、MP3(音频)和MPEG(视频)。此外,DCT可以实现高压缩比,使其适用于具有大量图像的数字系统,如互联网上的网页。

\ 分形压缩:分形是在不同尺度上重复的自重复无限模式。从尺度上的任何点查看时,模式看起来相似。因为模式在任何尺度上都相似,分形压缩减少"大"分形的尺度以减小数据的大小。

\ 分形示例

分形压缩由Michael Barnsley在1980年代引入。使用图像的一般想法是,如果图像包含几个看起来相似的部分,为什么要存储两次?为此,分形压缩执行以下操作:

• 将图像分割成不重叠的块,称为 范围块。这可能是8x8、16x16像素等的范围块。
• 它扫描图像以查找自重复模式(分形模式)。使用范围块,算法找到与这些范围块相似的图像的较大部分。这些较大的部分称为 域块。
• 然后将变换函数应用于域块以近似范围块。这些变换函数是数学函数,如缩放、平移、旋转等。它们也可以称为变换。相对于分形压缩,这些变换称为 分形代码。
• 然后将数据编码为这些变换函数。存储变换而不是存储像素-像素数据。这些变换是描述如何从域块重建图像的规则。

\ 使用分形代码,使用迭代过程重建图像。这个过程可能在计算上很昂贵,但与其他压缩技术相比,分形压缩可以实现高压缩比。由于它依赖于自重复模式,它将在符合具有此类自重复模式的数据上表现更好。例子包括风景照片(自然图像)和DNA图像。

\ 还有其他有损压缩技术,如离散小波变换、量化。这些技术通常用于图像、音频和视频文件,适用于每种文件类型的某些类型或文件格式 - JPEG、MP3。

\ 有损压缩通常比无损压缩具有更高的压缩比,有时期望用户事先知道要引入的损失量。必须强调的是,压缩方法和技术的选择取决于几个因素。这些因素的核心是数据格式和期望的结果。

TL;DR

总体而言,这篇文章讨论了数据世界中的压缩。它强烈依赖于计算机科学和信息论中现有的知识体系。压缩意味着减少实体占用的体积,在数据领域,体积指的是存储空间。正确完成时,数字系统中的压缩具有许多优势。显而易见的是它减少了空间并为存储更多数据提供了空间。其他优势包括更快的传输、更少的带宽使用以及所述系统效率的总体改善。记住,这是在正确完成时。

\ 要利用压缩的优势,关键是要知道使用哪种类型。压缩要么是有损的,要么是无损的。有损压缩会对原始数据引入通常不可逆的损失,而无损压缩会压缩数据并保留原始数据中包含的所有信息。此外,还有关于混合压缩类型的讨论,但我认为有损和无损的组合就是有损。请在评论中让我知道您的想法。

\ 最后,为有损和无损压缩引入了不同的技术。技术列表和这些技术的解释既不详尽也不全面。我认为它们只是一个很好的开始,让您了解每种技术的工作原理。总结一下,我添加了额外的资源来帮助您进一步调查并更深入地了解大数据中的压缩。

额外资源

视频:数据湖基础 - 实践中使用Parquet的RLE编码

论文:数据压缩技术综述

论文:无损压缩技术

David Salomon的数据压缩简明介绍

论文:各种数据压缩技术的研究

博客文章:开放文件格式中的压缩

文章:开放文件格式

文章:数据库中的压缩

基因组数据(RNA)的有损压缩

\