大數據中的壓縮：類型與技術

\

簡介

本文將討論大數據背景下的壓縮,涵蓋壓縮的類型和方法。我還將強調為什麼以及何時應該使用每種類型和方法。

\

什麼是壓縮?

根據壓縮的一般英文定義,它指的是減少某物以佔據更小的空間。在計算機科學中,壓縮是將數據縮小至更小尺寸的過程。在這種情況下,數據可以用文本、音頻、視頻文件等來表示。可以將其視為您存儲在計算機硬碟上的任何內容,即以不同格式表示的數據。提供一個更技術性的定義,壓縮是對數據進行編碼以使用更少位元的過程。

\ 壓縮數據有多種原因。最常見和直觀的原因是節省存儲空間。其他原因是數據變小的結果。處理較小數據的好處包括:

1. 更快的數據傳輸時間:壓縮數據尺寸更小,從源到目的地的傳輸時間更短。
2. 減少帶寬消耗:這個原因與更快的數據傳輸優勢密切相關。壓縮數據使用更少的網絡帶寬,因此增加了吞吐量並減少了延遲。
3. 改善嚴重依賴數據的數字系統的性能:這在依賴處理數據的系統中很明顯。這些系統利用壓縮通過減少需要處理的數據量來改善系統性能。請注意,這可能是特定於系統的,並且將依賴於使用適當的壓縮技術。壓縮技術將在本文後面討論。
4. 成本效益:雲服務對數據存儲收費。通過使用更少的存儲,可以節省成本,特別是在大數據系統中。

\ 壓縮的其他原因取決於不同的壓縮技術和格式。一些加密算法可以用作壓縮方法。這樣做時,它為前面討論的壓縮數據原因增加了一層安全性。此外,使用常見的壓縮格式為外部系統的集成目的帶來了兼容性和可擴展性空間。

\ 值得注意的是,壓縮的原因聽起來也像好處。然而,壓縮並非沒有權衡。壓縮的一個常見權衡是需要解壓縮,這對於資源受限的系統可能令人擔憂。其他權衡取決於所使用的壓縮技術和數據類型。

\

壓縮類型

為了討論用於壓縮數據的不同技術,我將首先將壓縮分為兩大類。本文然後將討論與每個類別相關的技術。壓縮可以大致分為 有損 和 無損 壓縮。

\ 正如名稱已經揭示了它們的含義, 有損壓縮 技術是不保留數據完全保真度的技術。簡單地說,一些數據被丟棄,但不足以使數據所代表的內容無法識別。因此,與無損壓縮相比,有損壓縮可以提供非常高的壓縮級別,無損壓縮將很快介紹。

\ 有損壓縮的一個特徵是它是不可逆的,即當呈現壓縮文件時,無法以其原始保真度恢復原始數據。某些文件和文件格式適合有損壓縮。它通常用於圖像、音頻和視頻。例如,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)的有損壓縮

\