2011-02-11 83 views
2

我正在尋找具有以下能力的壓縮庫/格式:用於動態壓縮和二分搜索的最佳壓縮庫/格式?

  1. 我寫它可以壓縮數據。
  2. 讓我有效地二進制搜索文件。
  3. 讓我有效地遍歷文件的反向。

語境:我正在寫一個C++應用程序,偵聽傳入的數據,規範化,然後需要堅持標準化輸出到磁盤。手動運行gzip文件時,數據已經很好壓縮了。但是,傳入數據的數量可能很大,我想快速進行壓縮。文件中的每個條目都有一個與它關聯的時間戳,我可能只對時間X和時間Y之間的數據塊感興趣,所以爲了快速找到該塊,我希望能夠進行二分搜索。如果可能的話,甚至可以反向迭代。做特別好的壓縮庫/格式是否適合我的項目?我發現滿足#1的庫,但是#2或#3是否會工作的文檔通常是無證的。

+0

我想你的意思是,沒有管理塊自己:)?我知道protobuf提供了延遲解碼,可以進行高效的搜索,但是您需要自己實際編碼二進制數據,所以在壓縮時效率可能不會如此高:/ – 2011-02-11 16:03:55

回答

1

您可以一次壓縮幾個塊,這樣您就可以分別對它們進行解壓縮,然後在壓縮數據中的每個塊塊的開始處保留一個(未壓縮但很小的)索引。這將允許對塊的幾乎隨機訪問,並且仍然通過時間戳保持它們的順序。對此的限制情況是單獨壓縮每個塊,儘管這可能會損害您的壓縮比。