作者如何選擇和設計編碼方案，以實現高效的解壓縮和高壓縮比？BtrBlocks是否適用于所有類型的數據？
選擇和設計編碼方案：
- 結合多種高效編碼方案：BtrBlocks 通過選擇一組針對不同數據分布的高效編碼方案，實現高壓縮比和快速高效的解壓縮。
- 基于采樣的方案選擇：BtrBlocks 對每個編碼方案在樣本上進行測試，并選擇表現最佳的方案。采樣算法在保持相鄰元組的局部性和準確表示整個數據范圍方面取得了平衡。
- 級聯應用方案：BtrBlocks 的遞歸應用方法將一個方案應用于另一個方案的輸出，直至達到最大遞歸深度。
BtrBlocks 適用于所有類型的數據：
- 支持各種數據類型：BtrBlocks 用于處理有符號整數、雙精度浮點數和可變長度字符串等類型的數據。
- 針對浮點數的偽十進制編碼：BtrBlocks 引入了針對二進制浮點數的偽十進制編碼，以提高浮點數數據的壓縮效果。
總之，作者通過結合多種高效編碼方案、使用基于采樣的方案選擇和遞歸應用方法，實現了高效的解壓縮和高壓縮比。BtrBlocks 適用于各種數據類型，包括有符號整數、雙精度浮點數和可變長度字符串。
級聯
級聯是指將多個設備或系統按照一定的順序連接起來，形成一個整體，使得每個設備或系統的輸出作為下一個設備或系統的輸入，實現功能的遞進和互補。
舉個例子，我們可以考慮一個音響系統的級聯。假設有一個音樂播放器和一個音箱，我們可以將它們級聯起來。首先，將音樂播放器的音頻輸出連接到音箱的音頻輸入接口上。這樣，在播放音樂時，音樂播放器會將音頻信號發送到音箱進行放大和輸出，從而可以聽到更大聲音的音樂。在這個例子中，音樂播放器是級聯系統中的第一個設備，音箱是第二個設備，它們通過級聯連接起來，實現了音頻信號的輸出和放大。
當我們連接多個電視機或顯示器來同時播放相同的內容時，就可以將它們級聯。其中一個電視機或顯示器作為主機，其他的電視機或顯示器作為從機，它們通過HDMI或VGA線連接在一起，主機的信號輸出被發送到從機，實現內容的同時播放。
在計算機網絡中，我們也可以將多個路由器級聯起來。每個路由器連接著不同的局域網，并且將數據包根據目標地址進行路由轉發，最終將數據包發送到正確的目標設備。
電子商務中的供應鏈管理也可以看作是級聯的一個例子。產品從供應商到制造商，再到批發商，最后到零售商，形成一個供應鏈網絡，每個環節都在前一環節的基礎上進行加工、組裝、配送等，最終將產品送到消費者手中。
這些例子中，級聯的設備或系統能夠實現信息、信號或物流的流動，從而達到更高的功能或效果。
編碼方案
RLE & One Value。Run-length Encoding (RLE)是一種普遍的技術，它對相等值的連續序列進行壓縮。例如，連續的序列{42, 42, 42}，存儲為(42, 3)。One Value是針對只有一個唯一值的列進行特殊優化。
Dictionary。字典編碼是另一種簡單但有效的方案，它使用（較短的）編碼替換輸入中的不同值。一個查找結構（即字典）將每個編碼映射到原始的不同值。用于實現字典的數據結構由編碼類型確定，字典通常是壓縮字符串的唯一方式。
Frequency。在真實世界的數據集中，通常會有一些多次出現的值，形成了偏斜分布。DB2 BLU提出了一種基于數據頻率的頻率編碼，使用多個代碼長度。例如，一個一位編碼可以表示兩個最頻繁的值，一個三位代碼可以表示接下來的八個最頻繁的值，依此類推。通常，一列只有一個主導的頻繁值，其次頻繁的值出現的頻率呈指數下降。本文針對這種情況進行了優化，只存儲：1）最頻繁的值，2）標記哪些值是最頻繁值的位圖，3）不是最頂部值的異常值。?? ?
FOR & Bit-packing。對于整數，參考框架（Frame of Reference，FOR）將每個值編碼為相對于選定基值的增量。例如，序列{105, 101, 113}，我們可以選擇基值為100，然后存儲{5, 1, 13}。這在與Bit-packing結合使用時很有用，后者截斷不必要的前導位，可以使用4位而不是8位對每個值進行Bit-packing。但是，基本的FOR方案在處理離群值時效果不佳。例如，向示例序列添加118，這種情況下每一個值都需要5位來表示。因此，Patched FOR (PFOR)將這些離群值存儲為異常，并保留其余值的較小位寬。SIMD-FastPFOR和SIMD-FastBP128構建在這個想法上，并專門為SIMD（單指令多數據）優化了算法和布局。在BtrBlocks中使用這些現有的高性能實現。
FSST。Fast Static Symbol Table (FSST)是一種用于字符串的輕量級壓縮方案，因為真實世界中大部分的數據都以字符串形式存儲。FSST通過將長度最多為8個字節的頻繁出現的子字符串替換為1個字節的編碼來實現壓縮。這些編碼在一個固定大小的255條目字典（符號表）中進行跟蹤。符號表是不可變的，并且用于整個字符串塊。解壓縮是簡單且快速的但是壓縮時需要找到一個合適的符號表，所以較為復雜。
NULL Storage Using Roaring Bitmaps。BtrBlocks使用Roaring Bitmap存儲每列的NULL值。Roaring 的背后思想是根據位的局部密度使用不同的數據結構，這使得它對于許多數據分布非常高效。BtrBlocks使用一個針對現代硬件進行了優化的開源C++庫來實現Roaring Bitmaps。除了追蹤NULL值之外，BtrBlocks還使用Roaring Bitmaps來追蹤內部編碼方案（例如頻率編碼）的異常情況。? ??
三. 方案選擇和壓縮
方案選擇算法。針對不同數據類型本文提供了不同的編碼方案，以適合各種不同的數據分布。但存在一些挑戰：一種更好的編碼方案選擇是使用抽樣。為了更好的壓縮，樣本必須捕獲與壓縮相關的數據集特征。例如，隨機抽樣可能不能很好地檢測RLE是否有效。另一方面，簡單地取第一個k個元組，就可能會得到一個有偏差的樣本。方案選擇算法的另一個挑戰是要考慮級聯，即它必須決定是否對已經編碼的數據進行二次編碼。（編碼后的數據作為新的輸入，然后嘗試是否可以繼續編碼）
解決方案。在BtrBlocks中將在每一個樣本中測試每種編碼方案并且選擇性能最好的方案。給定一個要壓縮的數據塊，每個遞歸級別都執行以下步驟：
（1）收集有關該塊的簡單統計信息。
（2）基于這些統計數據，過濾不可行的編碼方案。
（3）對于每個可行的方案，使用數據中的一個樣本來估計壓縮比。
（4）選擇觀測壓縮比最高的方案，并以此壓縮整個塊。
（5）如果壓縮的輸出為可壓縮格式，則重復步驟（1）。
3.1 樣本壓縮率評估
為了讓每個數據塊選擇最佳方案，樣本必須代表數據的特征。主要是需要保留空間局部性以及捕捉到唯一值的分布，而且開銷盡可能要低。如圖1所示，文章從數據的非重疊部分的隨機位置選擇多個小runs。對于64,000個值的塊大小，文章使用每個包含64個值的10個runs，從而得到1%數據的樣本大小。?? ?
圖1 從一個列塊中選擇一個隨機的樣本
估計壓縮比。BtrBlocks首先通過一次遍歷收集諸如𝑚𝑖𝑛、𝑚𝑎𝑥、唯一計數和平均運行長度等統計數據。基于這些統計數據，然后應用啟發式方法來排除不可行的方案。然后，BtrBlocks使用每個可行的編碼方案對樣本進行壓縮，以估計每個方案的壓縮比。
3.2 級聯
遞歸應用方案。在選擇了一個壓縮算法之后，壓縮后的數據（或其中的一部分）可能會使用不同的方案進行壓縮。如圖所示，遞歸點表示額外的可能壓縮步驟。用于額外步驟的方案再次使用我們的壓縮比估算算法進行選擇。遞歸的最大次數默認為3。一旦達到這個遞歸深度，BtrBlocks 將不再進行壓縮。?? ?
圖2 遞歸應用的編碼方案決策樹
編碼方案池。結果是一個通用的、可擴展的級聯壓縮框架，它從任意編碼方案的池中進行選擇。方案池顯著影響BtrBlocks的整體效果：有了更多的方案，壓縮速度變慢，因為需要評估更多的樣本，但壓縮比增加。添加更多的重型方案可能也會提高壓縮比，但減慢解壓縮速度。
意思就是說，D,S,I等三種類型是可以繼續壓縮的，在遞歸中會遇到不可壓縮的，為遞歸終點，以及遞歸深度超過3時，自動終止
四. 偽十進制編碼
過去對關系型數據庫中浮點壓縮的研究非常少。這有一個歷史原因：關系系統通常將實數表示為小數或數值，可以物理地存儲為整數。然而，隨著數據湖的轉移以及隨后與非關系系統的集成，這種情況正在改變，例如，Tableau的內部分析DBMS將所有實數編碼為浮點數，而機器學習系統幾乎完全依賴浮點數。
文章設計了一種專門為二進制浮點數設計的壓縮方案，即偽十進制編碼（Pseudodecimal?Encoding）。
4.1 壓縮浮點數?? ?
挑戰：1）物理上的IEEE 754表示，導致許多壓縮方法不適合；2）一些十進制數，不能用二進制精確表示，如0.99實際存儲的值是0.98999...。
浮點數表示為整數元組。偽十進制編碼使用十進制表示法對雙精度浮點數進行編碼。它使用兩個整數進行表示：帶符號的有效數字和指數。例如，3.25變為(+325, 2)，就像325 × 10^(-2)一樣；對于0.99只需要存（99, 2）而不用存（98999...，17）。
算法細節。偽十進制編碼算法通過測試所有10的冪并檢查它們是否正確地將雙精度浮點數乘以一個整數值來確定緊湊的十進制表示。首先在一個靜態表中存儲10的冪的倒數，以避免為每個數字重新計算它們。其次為解決-0、lnf和NaN問題，算法將其作為補丁存儲。同時將數字和指數的位數限制為32和5。這些屬性確保編碼比特位相同。
4.2 BtrBlocks中的偽十進制編碼
級聯到整數編碼方案。偽十進制編碼將一個浮點數列轉換為兩個整數列和一個小的異常列。BtrBlocks可能會再次使用級聯壓縮對這些列進行編碼：
圖3 偽十進制編碼示例
圖中所示的級聯壓縮選擇只是示例，而不是固定的；BtrBlocks使用其先前描述的采樣算法來選擇方案。
何時使用偽十進制編碼。有些數據不適合使用偽十進制編碼，比如包含許多異常值的列：偽十進制編碼略微提高了壓縮比，但由于存在許多異常值，解壓縮速度較慢。因此，BtrBlocks對那些具有超過50%不可編碼異常值的列禁用該方案。同樣，具有很少唯一值的列通常使用字典幾乎可以實現同樣好的壓縮效果，而字典具有更高的解壓縮速度。因此，在BtrBlocks的上下文中，選擇在具有少于10%唯一值的列中排除偽十進制編碼。?? ?
RLE代碼
import java.util.*;public class Main {private static List<Map.Entry<Integer, Integer>> RLE(int[] nums) {if (nums == null || nums.length == 0) {return new ArrayList<>();}List<Map.Entry<Integer, Integer>> result = new ArrayList<>();int count = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[i - 1]) {count++;} else {result.add(new AbstractMap.SimpleEntry<>(nums[i - 1], count));count = 1;}}result.add(new AbstractMap.SimpleEntry<>(nums[nums.length - 1], count));return result;}public static void main(String[] args) {int[] nums = {11, 11, 10, 999, 999, 999};List<Map.Entry<Integer, Integer>> encoding = RLE(nums);for (Map.Entry<Integer, Integer> entry : encoding) {System.out.println("(" + entry.getKey() + "," + entry.getValue() + ")");}}
}
)