在壓縮排序的固定寬度文件內搜索

Question

假設我有一個固定寬度的文件，該文件在其中一個字段上排序。考慮到我知道記錄的長度，我可以使用lseek實現二分查找，以查找具有匹配給定值的字段而不必讀取整個文件的記錄。

現在的困難是，該文件是gzip壓縮。是否有可能做到這一點，而不是完全膨脹文件？如果沒有使用gzip。有沒有支持這種行爲的壓縮？

Answer 1

這是完全不可能與拉鍊和衍生物壓縮的文件。這些基於滾動字典窗口，通常對輸出代碼的最高有效位進行基於緩衝區的壓縮。底線是壓縮文件中的特定字節序列在沒有上下文的情況下是沒有意義的。

如果你希望能夠隨機讀取特定記錄了一個壓縮文件，你可以分別壓縮每個記錄，然後有一個索引文件。根據你的數據，這可能會使壓縮步驟變得毫無價值。

Answer 2

幾乎所有的壓縮算法我知道在塊模式下工作，這意味着隨機查找是不可能的。即使不使用初始字典的LZMA也需要連續的解壓縮。

流壓縮通常意味着自適應有損壓縮一些密鑰復位狀態（或者實際上切成塊）。細節更復雜。

現在這裏有一對夫婦的想法來解決這個問題：

• 創建索引：就像當你打開ZIP，你可以看到所有文件，也
• 削減你壓縮文件成塊，然後在每個塊內使用二進制搜索（實際上與第一個塊相似）
• 解壓縮到內存中但實際上放棄任何數據，直到找到您要查找的數據的開頭f要麼。

最後一種方法適用於小型壓縮文件，塊方法適用於大型壓縮文件。你可以混合這兩個。

PS：利用固定於輸入，並不意味着壓縮文件將被固定。所以這是一個非常無用的信息。

Answer 3

建立在什麼Wernight said，您可以將您的文件gzip壓縮之前分割成許多固定大小的子文件。你的二分查找可以通過搜索包含該範圍的子文件開始，那麼它只需要解壓縮小的子文件而不是整個東西。您可以通過在包含每個子文件的第一行的歸檔中創建一個上層文件來進行優化。

Answer 4

bzip2的文件格式由多個獨立地壓縮塊。 如果您願意保留與您的bzip2文件並列的索引，您可以知道在哪裏找到。

注：這是一個問題重複：

• Compression formats with good support for random access within archives?
• Random access gzip stream
• Multi-part gzip file random access (in Java)

這些回答同樣的問題，而且身份BGZF作爲一個gzip兼容輸出格式，插入同步點以重置壓縮狀態。

Answer 5

繼續在什麼Liudvikas Bukys說：如果你的壓縮塊有一個獨特的頭，你不需要索引。這與如何在某些壓縮視頻格式中查找相似。你尋找一個點並尋找下一個標題。這並不需要強大的驗證（使用校驗）雖然，因爲誤識別是可能的。

Answer 6

你想要的是可搜索的壓縮;所述字典服務器具有dictzip這與gzip格式兼容，因爲它存儲它在標題和偵探套件一個gzip延伸seektable具有sgzip這不是因爲它在每個塊的開頭存儲塊長度