隨機數據訪問的壓縮矢量/數組類

Question

我想製作「壓縮數組」/「壓縮矢量」類（下面詳細介紹），它允許隨機訪問數據或多或少保持恆定時間。 「大致恆定的時間」意味着雖然元素訪問時間不是恆定的，但當我接近數組的某個點時，它不應該繼續增加。即容器不應該做更多的計算（比如「再次解壓縮所有內容以獲取最後一個元素」，以及「幾乎沒有任何內容獲取第一個元素」）來獲取一個元素。可能可以通過將數組分割成壓縮數據塊來實現。即訪問一個元素應該採取「平均時間」+ - 一些偏差。我可以說，我希望最佳訪問時間和最差訪問時間相對接近平均訪問時間。

我的選擇是什麼（合適的算法/已有的容器 - 如果有的話）？

集裝箱細節：

1. 容器充當相同的元件（比如std ::矢量）
2. 一旦容器被初始化的線性陣列，數據是恆定的並且不會改變。容器需要提供只讀訪問權限。
3. 容器應該像array/std :: vector - 即通過運算符[]訪問的值，存在.size（）等。
4. 如果我可以將它作爲模板類，那就太好了。
5. 訪問數據應該或多或少是恆定時間的。我不需要爲每個元素使用相同的訪問時間，但我不應該解壓縮所有內容以獲取最後一個元素。

使用示例：
二進制數據搜索。

數據詳細信息：
1.數據結構主要由浮點數和一些整數組成。有更多的浮點數比整數。沒有字符串。
2.數組中不可能存在許多相同的元素，因此僅索引數據是不可能的。
3.一個元素的大小小於100字節。
4.每個容器的總數據大小在幾千字節和幾兆字節之間。
5.數據不稀疏 - 它是連續的元素塊，它們全部被分配，沒有「空白槽」。

壓縮的目標是減少塊與非壓縮表示形式數組相比的ram數量，同時保持一定的合理讀取訪問性能，並允許隨機訪問元素作爲數組。即數據應該以壓縮形式存儲在內部，我應該能夠像訪問std :: vector或類似容器一樣訪問它（只讀）。

想法/意見？

Answer 1

我認爲你需要一個陣列的元素並不存儲香草，但壓縮，以減少內存使用情況。

關於壓縮，你沒有關於數據結構的特殊見解，所以你可以使用某種標準的熵編碼。理想情況下，想要在你的整個陣列上運行GZIP並完成它，但這會失去O（1）訪問權限，這對你至關重要。

甲溶液就是關聯索引表一起使用Huffmann coding。

霍夫曼編碼通過用另一個符號變量位長替換每個輸入符號（例如，一個ASCII字節）來工作，具體取決於整個流中發生的頻率。例如，字符E經常出現，所以它得到一個短序列，而'W'很少得到一個長序列。

E -> 0b10 
W -> 0b11110 

現在，用這種方法壓縮你的整個數組。不幸的是，由於輸出符號具有可變長度，因此您不能再像以前那樣對數據編制索引：編號15不再位於stream[15*sizeof(item)]。

幸運的是，這個問題可以通過使用額外的索引表index來解決，它存儲了每個項目在壓縮流中的起始位置。換句話說，項目15的壓縮數據可以在stream[index[15]]找到;索引表累積可變輸出長度。

因此，要獲得第15項，只需開始解壓縮位於stream[index[15]]的字節即可。這是可行的，因爲Huffmann編碼不會對輸出做任何事情，它只是連接新的代碼字，並且您可以在流內開始解碼，而不必解碼所有以前的項目。

當然，索引表增加了一些開銷;您可能需要調整粒度，以便compressed data + index table仍然小於original data。

Answer 2

好的，從我的最佳理解，你想要的是某種訪問模板。基本上，創建具有模板適配器作爲其參數的元素類型之一，它通過內部訪問什麼，指針，指數到您的一滴，等使適配器類指針：

const T &operator->(void) const; 

等。因爲創建一個指針適配器比創建一個引用適配器更容易（儘管如果你想知道如何編寫其中的一個，請參閱向量）。請注意，我根據您的指導原則使此訪問器保持不變。然後，在blob加載/壓縮時預先計算偏移量，並使用模板化的適配器類填充向量。這有意義嗎？如果您需要更多的細節，我會很樂意提供。對於壓縮算法，我建議你簡單地對blob中的字節進行頻率分析，然後通過硬編碼的霍夫曼編碼運行未壓縮的blob（正如之前提到的那樣），捕獲偏移量每個元素並將其存儲在您的代理適配器中，該代理適配器又是您陣列的元素。事實上，你可以將這個壓縮類的所有部分壓縮並生成可以從頭開始複製到你的向量中的元素。如果您需要示例代碼，請再次回覆。

Answer 3

您是否爲嵌入式系統編碼和/或您擁有數百或數千個這些容器？如果不是的話，雖然我認爲這是一個有趣的理論問題（+1），但我懷疑由於進行減壓會導致減速並非微不足道，因此最好使用std::vector。

接下來，你確定你存儲的數據是足夠多的，它的較小塊實際上是可壓縮的嗎？你有沒有嘗試保存不同大小的塊（2的權力也許），並嘗試通過gzip作爲練習運行它們？可能需要任何額外的數據來幫助解壓縮算法（取決於方法）會減少這種壓縮容器的空間利益。

如果你決定壓縮仍然是合理的，那麼至少有一些可能性，但沒有預先寫好。您可以壓縮每個單獨的元素，存儲指向壓縮數據塊的指針。然後索引訪問仍然是不變的，只需要解壓縮實際的數據。可能使用代理對象會使得實際的數據解壓縮變得更容易和更透明（甚至可能允許您使用std::vector作爲底層容器）。

或者，std::deque已經將數據存儲在塊中，因此您可以在此處使用類似的方法。例如std::vector<compressed_data_chunk>，其中每個塊可以說10個項目壓縮在一起作爲您的基礎容器。然後，您仍然可以直接索引所需的塊，解壓縮它，並從解壓縮的數據中返回項目。如果你願意，你的包含對象（包含vector）甚至可以緩存最近解壓縮的一個或兩個數據塊，以便在連續訪問時提高性能（儘管這對二進制搜索根本無幫助）。

Answer 4

我一直在想這一段時間了。從理論的角度來看，我確定了兩種可能性：

• 輕量級，因爲重複可以減少與此模式。
• 序列化（壓縮是某種形式的串行化的）

首先是純面向對象和合身我想一般，它不具有搞亂指針例如的缺點。

第二種似乎更適合這裏，雖然它一般有一個小小的缺點：指針失效+指針編碼/解碼，虛擬表等問題...值得注意的是，如果項目引用每個其他人使用指針而不是索引。

我已經看到了一些「霍夫曼編碼」解決方案，但這意味着每個結構都需要提供一個壓縮算法。概括並不容易。

所以我寧願去另一種方式，使用像'zlib'這樣的壓縮庫，選擇一個像lzo這樣的快速算法。

• B *樹（或變體）每個節點有大量項目（因爲它不會移動），比如說1001.每個節點都包含項目數組的壓縮表示。指數沒有壓縮。
• 可能：cache_view訪問容器，同時存儲最後5個（或所以）解壓縮的節點或東西。另一個變體是實現引用計數並保持數據未壓縮，只要有人處理了節點中的某個項目。

一些言論：

• ，如果你要大量的項目/每個節點的密鑰具有接近恆定訪問時間，例如與1001這意味着只有2個間接爲長因爲你存儲了不到100萬個項目，3個十億等級的間接尋址......
• 你可以用這樣的結構構建一個可讀/可寫的容器。我會這樣做，以便我在完成寫入節點後只進行重新壓縮。

Answer 5

"What is the best compression algorithm that allows random reads/writes in a file?" 的某些答案是否適用於您的內存數據？