如何在二進制文件中存儲有序整數集？

存儲大量32位整數值（按升序排列），僅用於連續讀取。原始文件很大，不能放入RAM中，逐塊讀取。到目前爲止，我只是將它們保存爲二進制文件，每個值4個字節。如何在二進制文件中存儲有序整數集？

隨着系統的不斷髮展，需要優化存儲/備份空間，我發現考慮到它的排序，對這些數據進行高效壓縮具有很大的潛力。

我想出的是存儲初始值，然後是增量，隨着集合中值的數量增加，增量往往更小。將它們的大小舍入到全字節，我建議每個增量只留下有意義的字節，所以不是4，而是每增加1-2-3字節。爲了表示使用的字節數，我會使用標題每個增量2位。

流看起來像：

01010101 01010101 01010101 01010101 - initial value 

             Four increments block start 
10110101       - b bytes used: four 2-bit pairs 
             (10 11 01 01 = 2, 3, 1, 1) 
01010101 01010101     - inc 
01010101 01010101 01010101   - inc 
01010101       - inc 
01010101       - inc 

             Four increments block start 
11011101       - b (11 01 11 01 = 3, 1, 3, 1) 
01010101 01010101 01010101   - inc 
01010101       - inc 
01010101 01010101 01010101   - inc 
01010101       - inc 

...

我是不是想在這裏發明車輪？在這裏流式壓縮可以更有效率，在相當小的塊上保持運行嗎？

來源

2014-12-07 Serge

所以你想用PHP壓縮數據？什麼樣的數據？如果您試圖將文件轉換爲二進制文件並保存。這將不會有效 – codinginsane 2014-12-07 10:08:24

您的文件有多大？可能使用支持壓縮的基於數據庫的解決方案是一種方法嗎？這樣你就可以獲得所有功能，而不用重新創建任何車輪 – Konstantin 2014-12-07 10:15:16

@CodingInsane，如問題中所述：數據是32位整數的有序集合。從某些服務中收到，以二進制格式保存到本地文件中。「這根本不會有效」 - 爲什麼？ – Serge 2014-12-07 10:17:03

這叫做variable-length integers or variable-length quantities。對於您的應用程序而言，取決於差異分佈的可能更高效的方法，以及避免處理比特流的更快速的方法是在每個字節的高位中使用其餘的七位每個字節用於整數位。舉例來說，你可以有一個高位1表示整數的結尾，整數位最先存儲最高有效位。然後0..127被存儲爲字節0x80..0xff。如果第一個字節是0x01..0x7f，那麼你有高7位的數字，然後你轉到接下來的7位的下一個字節，直到你得到一個高位。

這也有一個特性，即0x00的初始字節是不允許的，所以你可以用它來表示流的結束。

例如，如果128..255範圍內的差異很常見，那麼您的計劃可能會更有效。在這種情況下，你的方案使用十位來表示那些，上面描述的那個使用了16位。另一方面，如果差別範圍0..127是最常見的，則上述可能是最好的，因爲它將它們編碼爲8位，在那裏你使用十個。

完成編碼後，可以通過應用標準壓縮例程（如zlib）來獲得進一步壓縮。

來源

2014-12-07 16:11:29

謝謝@馬克阿德勒！我知道有一天MIDI會回到我身邊） – Serge 2014-12-07 17:58:05

如何在二進制文件中存儲有序整數集？

回答

相關問題