資料壓縮/評估壓縮效率
當應用程式程式設計師決定使用哪種壓縮演算法時，需要權衡許多因素：[1]
- 速度：它有多快？
- 壓縮率：如果它不能使我們的資料比未壓縮大小更小，那就沒有意義。
- 複雜度：可執行檔案有多大？（這既有硬成本——軟體使用多少 ROM 或磁碟空間？——也有軟成本——如果我需要更改它，需要多長時間才能瀏覽所有原始碼以找到要更改的正確內容，以及更改後，需要多長時間才能測試程式碼的每個部分以確保更改不會破壞其他內容？）
- 空間：執行需要多少 RAM？
- 延遲：我需要等待多久才能聽到歌曲的第一段？
- 互操作性：我生成的的檔案可以被任何標準歸檔實用程式讀取嗎？
當壓縮庫程式設計師調整了壓縮演算法並試圖確定它是否真的更好或者他是否應該恢復到以前的版本時，他會使用相同的標準。
在評估資料壓縮演算法時，速度始終以每秒處理的未壓縮資料量來衡量。
對於流式音訊和影片，
- 速度 = 一秒鐘內可以處理的未壓縮位數。
一些應用程式即使有足夠的 RAM 和磁碟空間，也不需要縮小檔案大小，也會使用資料壓縮技術。檔案壓縮和增量壓縮通常用於加快從慢速連線的一端到另一端的複製檔案速度。即使在單臺計算機上，某些型別的操作在壓縮版本的資料上執行時也要比直接在未壓縮資料上執行快得多。[2] 特別是，一些壓縮檔案格式的設計使得壓縮模式匹配——在壓縮文字檔案的壓縮版本中搜索短語——比在原始未壓縮文字檔案中搜索相同的短語快得多。[3][4][5][6][7][8][9][10][11]
（“zgrep”或“zcat”在這裡相關嗎？）
一些專門用於壓縮點陣圖的壓縮演算法——位元組對齊點陣圖程式碼 (BBC)、字對齊混合程式碼 (WAH)、位置列表字對齊混合程式碼 (PLWAH)、壓縮自適應索引 (COMPAX) 和壓縮 'n' 可組合整數集 (CONCISE)——允許將位運算直接應用於壓縮資料。[12] 這可能比解壓縮資料、應用位運算，然後重新壓縮結果快得多。
（FIXME：將以上內容的一部分移動到壓縮域處理。）
在許多應用中，解壓縮速度至關重要。如果在原型行動式音樂播放器硬體上執行的音訊解壓縮器特定實現無法持續向耳機提供 1.4 Mbit/s 的資料流，那麼它就無法使用。除非您切換到不同的實現或更快的硬體（或兩者兼而有之），否則沒有人會購買它，這些硬體能夠跟上標準立體聲音訊的速度。
在一些應用中，壓縮速度至關重要。如果在原型語音記錄器上執行的音訊壓縮器特定實現無法持續從麥克風向儲存器提供 7 bits/sample/channel x 1 channel x 8 kSamples/s = 56 kbit/s 的資料流，那麼它就無法使用。沒有人希望他們的錄音中出現靜默間隙，因為硬體無法跟上。除非您切換到不同的實現或更快的硬體（或兩者兼而有之），否則沒有人會購買它，這些硬體能夠跟上標準電話級語音速度。
速度在不同機器之間，不同實現之間差異很大。即使在同一臺機器上，使用同一基準檔案和同一實現原始碼，使用不同的編譯器也可能使解壓縮器執行速度更快。
壓縮器的速度幾乎總是比其對應解壓縮器的速度慢。
即使使用現代快速 CPU，壓縮檔案系統的效能通常受壓縮演算法速度的限制。許多現代嵌入式系統（以及許多早期開發資料壓縮演算法的計算機）在速度上受到嚴格限制。只有少數壓縮演算法足夠快，可以在速度極其受限的系統上使用：[1]
- RLE；
- LZSS 家族中的演算法；
- LZW 家族中的演算法；
- 固定位元組對編碼，例如 PalmDoc；
- 增量編碼 + 自適應霍夫曼。
… 還有其他嗎？…
許多現代嵌入式系統（以及許多早期開發資料壓縮演算法的計算機）在 RAM 方面受到限制。當可用 RAM 太小，無法容納解壓縮文字和單獨的字典（例如 GIF 解碼器為 LZW 字典所需的 12 KB 字典）時，很少有壓縮演算法能夠在這種限制下工作。 [13] 由於 RAM 太少，
- 如果我們需要將整個解壓縮文字儲存在 RAM 中（例如自解壓縮可執行檔案），那麼我們不得不排除 LZW，並使用解壓縮文字作為字典，例如 LZ77 和 Pucrunch。
- 如果我們不需要將整個解壓縮文字儲存在 RAM 中（例如，外部調變解調器在將明文轉發到 PC 之前，透過“慢速”電話鏈路解壓縮傳送的資料），那麼對於任何給定的 RAM 量，LZW 型別的壓縮格式通常比 LZ77 型別的壓縮格式提供更好的壓縮。對於典型的英文文字，在解壓縮器的字典中儲存的單詞和短語越多，壓縮效果就越好。LZ77 使用大量 RAM 來儲存經常重複出現的常用詞。LZW 使用可用 RAM 來儲存每個唯一詞一次，因此在 RAM 受到限制時，壓縮效果比 LZ77 好。
在設計壓縮檔案格式時，通常會在變長格式和位元組對齊格式之間進行速度/空間權衡。大多數系統可以更快地處理位元組對齊格式。變長格式通常提供更好的壓縮。位元組對齊格式可以使用除 8 位資料以外的資料大小。 [13] 例如，許多 LZ77 型別的解壓縮器使用位元組對齊格式，其中包含 16 位“專案”，解壓縮器將其分解為 3 位長度和 13 位偏移量。一些解壓縮器使用 1 位、8 位和 16 位專案的組合，其中（為了速度）1 位專案小心地打包到 8 位“控制位元組”中，因此其他所有內容都可以保持位元組對齊。（在本書的後面，我們將更詳細地討論位元組對齊格式：資料壓縮/字典壓縮#實現技巧和竅門）。
在本書中，我們將壓縮率定義為
能夠將 2 MB 壓縮檔案解壓縮為 10 MB 檔案的演算法的壓縮率為 10/2 = 5，有時寫為 5:1（讀作“五比一”）。
對於流式音訊和影片，壓縮率是根據未壓縮和壓縮位元率而不是資料大小來定義的
例如，CD 上的歌曲以 16 bits/sample/channel x 2 channels x 44.1 kSamples/s = 1.4 Mbit/s 的資料速率進行未壓縮。同一首歌曲以 (有損“高質量”) 128 kbit/s Vorbis 流（或 128 kbit/s MP3 流或 128 kbit/s AAC 檔案）編碼，產生的壓縮率約為 11:1（“十一比一”）。
同一首歌曲使用典型的無損音訊壓縮器（如 FLAC 或 WavPack）進行編碼，通常壓縮比約為 2:1 到 3:1（“三比一”），儘管有些歌曲沒有壓縮（1:1），而某些型別的古典音樂使用此類無損音訊壓縮器可以獲得高於 3:1 的壓縮比。
根據此“壓縮比”的定義，對於給定的未壓縮檔案，更高的壓縮比會導致更小的壓縮檔案。
（不幸的是，其他一些文字將“壓縮比”定義為倒數，或插入 8 或 100 等任意其他因子，或完全使用其他公式）。
文字檔案無失真壓縮的一些典型壓縮比
- 2:1 或更差：極其簡單且快速的演算法，如 LZRW1-a，可以在 2GHz CPU 上以壓縮資料飽和 100 MB/s 硬碟。
- 文字檔案的壓縮比為 2.5:1 到 3.5:1：稍微複雜（因此稍微慢一些）的演算法，如 DEFLATE[14]
- 5:1 不幸的是，所有已知的用於在英語文字上獲得高於 5:1 壓縮因子的演算法執行速度都極其緩慢，在 2GHz P4 上解壓縮 100 MB 未壓縮資料需要 5 個小時或更長時間。
- 6.27:1 當前（2009 年）的 Hutter 獎世界紀錄壓縮比
所有無損資料壓縮演算法對不同檔案的壓縮比都不同。對於幾乎任何資料壓縮演算法，都很容易人工構造一個“基準測試”檔案，該檔案可以以驚人的高壓縮比進行壓縮並無損解壓縮。不幸的是，這種人工的高壓縮比並不能說明這些演算法在真實資料上的工作效果如何。有多種標準基準檔案可用。使用大量此類基準檔案可以幫助程式設計師避免意外地過度調整演算法，使其在某個特定檔案上表現出色，但在其他檔案上卻表現很差。
一些標準基準檔案將在本書後面列出——Data Compression/References#Benchmark files.
通用壓縮
[edit | edit source]一些程式設計師專注於“通用壓縮”演算法，這些演算法不與任何特定格式（如文字或影像）繫結。[15][16] 這些程式設計師在包含各種格式的基準檔案集合上調整他們的演算法。
格式特定壓縮
[edit | edit source]其他程式設計師專注於一種特定型別的檔案——影片壓縮、靜止影像壓縮、單人語音壓縮、高保真音樂壓縮、英語文字壓縮或其他一些特定型別的檔案。通常，這些格式特定程式設計師會嘗試在原始資料中找到某種冗餘，這些冗餘可以用於無失真壓縮——例如，音樂通常有一個主音，該主音以特定頻率重複多次，持續幾分之一秒——但每次重複都不完全相同於其他任何重複——然後是另一個主音，以其他頻率重複多次，持續幾分之一秒。通常，這些格式特定程式設計師會嘗試找到人類感知的侷限性，這些侷限性可以用於有失真壓縮。通常，這些程式設計師會想出一些方法來“轉換”或“預處理”或“去相關”資料，然後將中間結果交給某個“通用壓縮”演算法。我們將在Data Compression/Multiple transformations中對此進行更詳細的討論。
對於它被調整的特定格式，這種格式特定壓縮演算法通常比單獨的通用壓縮演算法提供更好的結果。不幸的是，這種演算法通常比通用壓縮演算法對其他型別的檔案提供更差的結果。
延遲
[edit | edit source]延遲是指音訊訊號進入系統到從系統中出來的短時間延遲（通常以毫秒為單位測量）。
壓縮會增加兩種型別的延遲：壓縮延遲和解壓縮延遲，這兩者都會增加端到端延遲。
在某些音訊應用中，尤其是雙向電話式通訊，端到端延遲至關重要。電話服務的推薦最大時間延遲為 150 毫秒[citation needed](Wikipedia:1 E-1 s)。這排除了許多流行的壓縮演算法。例如，標準霍夫曼壓縮的塊大小為 150 毫秒或更長，將無法正常工作。標準霍夫曼壓縮需要分析整個塊才能傳送出塊中第一個符號的壓縮字首碼。在這種情況下，霍夫曼壓縮器會用掉所有等待塊填滿的時間，沒有時間用於飛行時間傳輸或解碼。（150 毫秒或更長的塊大小可能適用於自適應解碼器）。
在其他音訊應用中，端到端延遲無關緊要。在壓縮歌曲以便稍後分發或壓縮電影的音軌時，壓縮器通常在開始壓縮之前可以獲得所有資料。此類應用可能會在低延遲演算法足夠的情況下使用低延遲演算法；但它們也允許使用其他演算法，這些演算法可能提供更好的網路壓縮或更低的峰值位元率。
在一些應用中，只有解壓縮延遲很重要。例如，如果在原型行動式音樂播放器硬體上執行的音訊解壓縮器的特定實現的延遲為 10 分鐘，那麼它幾乎不可用。沒有人想在選擇歌曲後等待 10 分鐘才能開始聽到它。除非您切換到不同的實現或更快的硬體（或兩者兼而有之），否則沒有人會購買它。
許多壓縮演算法具有以位為單位測量的最小資訊理論延遲。（是否有一個比“資訊理論延遲”更好的名稱來描述本段和下一段討論的內容？） 在給定恆定的未壓縮位元率的情況下，這對應於從（未壓縮）位進入壓縮器到相應的（未壓縮）位從解壓縮器出來的最壞情況延遲，在位元率如此緩慢以至於我們可以忽略壓縮器和解壓縮器中執行的計算所需的時間以及飛行時間的情況下。
固定字首編碼器或自適應霍夫曼編碼器通常具有極其短的資訊理論延遲。它們中的許多具有小於 16 位的延遲。
MP3 壓縮器犧牲延遲和質量以獲得更高的壓縮比。它們的延遲至少為 576 個時域 16 位樣本，以 44.1 kHz 取樣，延遲至少為 9,216 位或 13 毫秒，通常更長以利用“位元組庫”。
能量
[edit | edit source]關於壓縮演算法使用的能量量，研究很少。
在一些感測器網路中，壓縮的目的是節省能量。透過在 CPU 中花費少量能量壓縮資料，因此我們可以減少要傳輸的位元組數，從而節省無線電的能量——無線電可以更少地開啟或更短地開啟，或者兩者兼而有之。[17]
此類感測器網路中最好的壓縮演算法是那些最小化總能量，從而最大化執行時間（兩次更換電池之間的時間間隔）的演算法。這種演算法處於兩個方面之間的利基市場：一方面，是那些產生更小的壓縮檔案，但使用過多的 CPU 能量來產生它們的演算法；另一方面，是那些使用更少的 CPU 能量，但產生（相對）更長的檔案，需要更多的能量來傳輸的演算法。
比較
[edit | edit source]我們使用博弈論術語“支配”來表示一種演算法比其他演算法更快、生成更小的壓縮檔案並且延遲更低。當然，某些特定實現並非經過很好的最佳化，因此可以對其進行調整以使其執行*更快*，並且仍然以相同的壓縮檔案格式實現相同的演算法。但任何抽象演算法都必然需要一些最小操作次數，因此不可能將需要比某個當前更快演算法多幾個數量級的操作次數的演算法最佳化到足以支配該更快演算法的地步。
許多歷史重要的壓縮演算法現已過時，被其他更實用的演算法所取代。但目前（以及在可預見的未來），即使對於固定的一組基準檔案，也不存在一種“最佳”的壓縮演算法——在帕累託前沿上存在許多“最佳”演算法的譜系；這些演算法譜系共同支配著並使所有其他已知演算法過時。能夠提供一些但並非大量壓縮的極速演算法位於帕累託前沿的一端。在帕累託前沿的另一端，是已知的壓縮基準檔案的最佳方式——但是，由於速度太慢，它們並沒有太大的用處。
- ↑ a b "駭客資料壓縮" 由安迪·麥克法登 1993 年撰寫
- ↑ "壓縮域處理技術調查" 由布萊恩·C·史密斯撰寫
- ↑ [1] "SASE：壓縮文字搜尋引擎的實現" (1997) 由 Srinidhi Varadarajan 和 Srinidhi Varadarajan 和 Srinidhi Varadarajan 和 Tzi-cker Chiueh 和 Tzi-cker Chiueh 撰寫
- ↑ Shmuel T. Klein 和 Miri Kopel Ben-Nissan. "關於斐波那契壓縮碼的有用性". 2004. 2009.
- ↑ "一種允許在壓縮檔案中快速搜尋的文字壓縮方案" 1993 年由 Udi Manber 撰寫
- ↑ "壓縮文字中的基於短語的模式匹配" 由 J. Shane Culpepper 和 Alistair Moffat 撰寫
- ↑ 維基百科：壓縮字尾陣列
- ↑ Shmuel T. Klein 和 Dana Shapira. "壓縮詞典中的搜尋".
- ↑ Carlos Avendaño Pérez 和 Claudia Feregrino Uribe. "壓縮文字的近似搜尋".
- ↑ Udi Manber. "一種允許在壓縮檔案中快速搜尋的文字壓縮方案".
- ↑ Yusuke Shibata，Takuya Kida，Shuichi Fukamachi，Masayuki Takeda，Ayumi Shinohara，Takeshi Shinohara，Setsuo Arikawa. "位元組對編碼：一種加速模式匹配的文字壓縮方案" 1999 年。 "在 BPE 壓縮文字中進行模式匹配比在原始文字中更快。"
- ↑ 維基百科：點陣圖索引：壓縮。 FIXME：用更好的引用替換此引用。
- ↑ a b "Pucrunch：一種最佳化混合 LZ77 RLE 資料壓縮程式，也稱為提高低資源解壓縮的壓縮率" 由 Pasi Ojala 撰寫
- ↑ "解壓縮 GZIP 壓縮協議" 由 Joe Rash 撰寫
- ↑ Matt Mahoney. "通用壓縮基準"。進一步討論："通用壓縮基準".
- ↑ IETF. "6LoWPAN 標頭和類似標頭的有效載荷的通用壓縮"
- ↑ Christopher M. Sadler 和 Margaret Martonosi "延遲容忍網路中能量受限裝置的資料壓縮演算法"