資料壓縮/編碼
大多數人認為壓縮主要與編碼有關。好吧，曾經確實如此。在資訊理論出現之前，人們花費數年時間開發完美的程式碼以有效地儲存資料。為了理解編碼作為壓縮機制的侷限性，我們必須瞭解什麼是編碼。
計算機真正只理解一種型別的資料，即0和1的字串。你知道0是關，1是開，以及所有這些廢話。這些實際上與記憶體單元的狀態有關，其中0是單元的低電壓輸出，而1是略高的電壓。隨著電路尺寸的減小以及跨並行電路間隙所需的電壓減小，實際涉及的電壓差也在減小。
硬體配置用於定義程式碼的大小，方法是限制可以一次移動的雙狀態記憶體元素（稱為位元）的數量。例如，在微型計算機開發過程中發現的4位、8位、16位、32位、64位，以及現在的128位架構。
現在，計算機中的所有內容基本上都儲存為位元序列。計算機的儲存容量受浪費的位元數量的限制。理想情況下，我們不想浪費位元，因此我們傾向於使用能夠最大程度地減少任何特定計算機架構上浪費的位元數量的程式碼。最終的程式碼是涵蓋資料型別中所有可能變化的程式碼，並且浪費的位元最少。
有趣的是，這在人腦中並不是一個考慮因素，事實上，我們不得不定義一個術語來解釋大腦程式碼中攜帶的冗餘資訊，這個術語是簡併編碼，一個貶義詞，實際上只是意味著同一資訊有多個程式碼。
考慮一個表示某些含義的數字字串。它們是一串數字嗎？如果是，我們希望對它們進行編碼以最小化每個數字的儲存。一個整數值？如果是，我們希望對它們進行編碼以最小化任意大小整數的儲存。一個浮點值？如果是，我們希望對它們進行編碼以最小化任意大小尾數的儲存，幷包含有關數字提高到什麼冪以及我們將儲存小數點後多少位的資訊。或者一個地址字串？如果是，我們希望對它進行編碼以最小化特定語言中字元所需的位元數。
對於人類來說，所有這些不同型別的儲存在列印頁面上看起來都一樣。但是，在不同型別的儲存之間進行轉換需要時間，因此您可能不希望在使用它們時將其轉換為最緊湊的編碼。但是，稍後當您想將其儲存起來以備後用時，將其壓縮到儘可能小的尺寸似乎是一個好主意。這就是壓縮的本質。
因此，編碼密度的限制取決於您嘗試編碼的資料型別，以及從單獨位置獲得的資訊量。
例如，軍隊有在戰役期間限制無線電通訊的慣例，這通常被認為是一件好事。甚至將其推到限制自己點選麥克風以觸發攻擊下一階段的程度。對於完全瞭解情況的人來說，點選麥克風將足以傳送有關行動狀態的大量資訊。這一事件對躲在戰壕裡的敵人來說毫無意義，因此他們第一次發現攻擊的證據是槍聲響起的時候。
理想情況下，所有儲存都可以透過包含完整百科全書的單個位元檔案來實現。實際上，這不太可能發生。編碼仍然很重要，但它現在對壓縮的貢獻非常有限。新的壓縮演算法越來越難以獲得，因此新的方法專注於源資料，真正的進步最近已減少到程式碼將執行的硬體。
| “ | 需要說明的是，真正的壓縮演算法是一項複雜的技術，幾乎算得上是一種藝術形式。 | ” |
——Leo A. Notenboom，[1] | ||
在資料壓縮領域，用資料的基本單位——位元來衡量資料“大小”很方便。
許多資料壓縮演算法生成一個壓縮資料流，該資料流是位元流——與任何其他大小沒有特定對齊方式。
有時根據“符號”來考慮輸入資料很方便。一些演算法根據輸入中的符號壓縮英文文字，並處理它們，將它們轉換為壓縮輸出上的可逆表示。符號通常是位元集，但它們反過來可以表示任何型別的字元表示/編碼，甚至畫素或波形。
在壓縮CD音質音訊時，符號是2^16個可能的振幅級別——揚聲器錐體的2^16個可能的物理位置。
一些檔案壓縮實用程式根據257個不同的符號來考慮未壓縮的檔案。在檔案的任何位置，“下一個符號”都可以是257個符號中的任何一個：256個可能的位元組之一——或者我們可能已經到達檔案末尾，第257個符號表示“檔案末尾”。
在比較影像壓縮例程時，有時使用術語“bpp”（每畫素位元數）。未壓縮的彩色點陣圖影像為24 bpp。未壓縮的2色點陣圖影像（僅包含黑色畫素和白色畫素）為1 bpp。一些影像壓縮演算法可以將某些影像壓縮到遠小於0.1 bpp。相同的影像壓縮演算法可能在將其他一些影像壓縮到7.5 bpp方面做得非常好。
使用變長編碼，我們可以使某些符號非常短——比這些符號的任何定長編碼都短。這對於壓縮資料非常有用。
然而，變長編碼幾乎總是會導致其他符號略長於這些符號的最佳定長編碼。
一開始，使用更多位元來儲存一個符號聽起來很荒謬——為什麼我們不簡單地儲存這些符號的較短的定長版本呢？
好的，是的，*其他*符號可以更短。所以……為什麼我們不能在變長版本更短時使用它，而在定長版本更短時使用它呢？兩全其美？也許使用“1”字首來表示“接下來是定長表示”？
我們將在本書的熵編碼部分更詳細地討論變長編碼。
數字資訊可以編碼為一系列整數。使用現代數位電子裝置，我們通常首先 (1) 將資料（等）以某種相對簡單的（但冗長的）編碼方式編碼為一系列整數，然後 (2 & 3) 資料壓縮演算法獲取該整數序列，並找到其他方法來用更少的位元表示整個序列。
例如，當我們將音樂儲存在 MP3 檔案中時，機器通常首先 (1) 使用麥克風和 ADC 將模擬聲音數字化為 (相對簡單但冗長的) 16 位 PCM 編碼，取樣率為每通道 44.1 kHz（CD 數字音訊，未壓縮的 WAV 音訊等）。然後軟體首先處理原始資料以 (2) 將其轉換為需要更少整數的表示形式，然後 (3) 以某種方式表示每個整數的位元，以便整首歌曲可以用相對較少的位元儲存。
（在計算機的早期，人們花費大量時間來弄清楚如何將音樂（等）編碼成合理的按鍵數量，在將其輸入計算機之前，使用人腦“手動”壓縮和編碼資料）。
人們發明了大量將整數表示為位元的方法。
…（在此處簡要說明 32 位無符號整數）…
…（在此處簡要說明 2 的補碼有符號整數）…
浮點數通常儲存為一對有符號整數——尾數（有效數字）和指數。
定長碼是表示一系列整數的最簡單方法。
...
逗號碼是表示一系列任意長整數的一種方法。
每個整數都由一系列數字表示。
一個特殊的符號——稱為逗號——用於每個碼字之間，以標記一個整數的結束和下一個整數的開始。
SCDC 是表示一系列任意長整數的一種方法。
(s,c) 碼，也稱為 (s,c) 密集碼 (SCDC)，其長度是 8 位位元組的倍數。[1]
SCDC 只有一個引數 s，選擇為 0 < s < 256。每個碼字由一系列 8 位位元組組成，其中碼字中的最後一個位元組的值小於 s，而其他位元組（如果有）的值大於或等於 s。
結束標記密集碼 (ETDC)，也稱為變長量 (VLQ)，是 s=128 的 SCDC 特例。
由於每個 SCDC 碼字都與位元組邊界對齊，因此 SCDC 解壓縮比霍夫曼解壓縮更簡單、更快。[1]
SCDC 和斐波那契碼都支援在壓縮檔案中直接搜尋。[2][1]
Z 字形編碼是表示有符號整數的一種方法。它將“小”有符號整數（接近零）對映到“小”無符號整數（最高有效位全部為零）。[3][4] 它旨在在 32 位 Z 字形編碼的有符號整數和 32 位 2 的補碼有符號整數之間進行一對一的對映。Z 字形編碼（如增量編碼）本身不會節省任何空間，但它通常以某種方式轉換資料，使其他下游壓縮演算法能夠更好地工作。（增量編碼後跟 Z 字形編碼通常會產生更好的結果——使用相同的下游壓縮演算法——而不是單獨使用其中任何一個）。[5]
encoded integer 0000 0005 : -3 0000 0003 : -2 0000 0001 : -1 0000 0000 : 0 0000 0002 : +1 0000 0004 : +2 0000 0006 : +3
- ↑ a b c Shmuel T. Klein；和 Miri Kopel Ben-Nissan。[https://pdfs.semanticscholar.org/62de/373af61cc71854f86028554a988f8a4dbe36.pdf “關於斐波那契壓縮碼的有用性”]。2009 年。
- ↑ Shmuel T. Klein；和 Dana Shapira。“實用定長 Lempel Ziv 編碼”。
- ↑ Google 開發者。“Protocol Buffers：編碼”。
- ↑ “protobuf-c.c”
- ↑ “增量 Z 字形編碼二進位制打包”