BasicData Compression
Keywords
data compressionblock compressiondictionary codingentropy codingHuffman codingANSfixed-inputfixed-outputcompression ratioCPU overheadAsk ChatGPT
Prerequisites
None — this is a starting concept.
Related Papers
Progress
Sign in to track your progress.
在 storage system 中，資料壓縮可以有效減少磁碟使用量與 I/O 傳輸量，但也會帶來 CPU 開銷與 read amplification。我們會學習 block compression 的基本單位概念、dictionary coding 如何利用重複值來節省空間，以及 entropy coding（Huffman、ANS）如何根據符號出現頻率進行最佳編碼。另一個重要的設計取捨是 fixed-input 與 fixed-output paradigm 的差異——前者壓縮率較好但隨機讀取困難，後者犧牲壓縮率換取 O(1) 定位能力。理解這些壓縮基礎，對後續學習 columnar storage 格式與 deduplication 技術至關重要。
Key Concepts
我理解 block compression 的概念，即以固定大小的 block 作為壓縮與解壓縮的基本單位
我理解 dictionary coding 如何利用重複出現的值來節省儲存空間
我理解 entropy coding（Huffman coding、ANS）如何根據符號出現的頻率進行最佳化編碼
我理解 fixed-input 與 fixed-output paradigm 的設計取捨——前者壓縮率較高但不利於隨機存取，後者犧牲壓縮率換取 O(1) 定位能力
我了解壓縮帶來的 CPU overhead 與節省 I/O 之間的權衡，以及在 storage system 中如何做出適當的取捨
Recommended Resources
