壓縮超長字符串的列表

Question

我有很長的想要壓縮的短字符串的列表，但我希望能夠在任何時候解壓縮列表中的任意字符串而不需要解壓縮整個列表。

我知道提前清單，無論涉及多少預處理都無所謂。如果存在一些重要的O（1）內存開銷，那也很好。

我意識到我可以用一些無損壓縮算法獨立地壓縮每個字符串，但這不會很好，因爲字符串非常短，並且每個字符串都不包含太多冗餘。然而，在整個列表中有很多冗餘。

Answer 1

我建議一次壓縮64K左右的字符串（大約32個字符串），要求你只需要平均解壓16個字符串即可得到你想要的字符串。而不是1,000,000。使用deflate可以獲得幾乎相同的壓縮（gzip使用的壓縮方法）。

也可以使用deflate來構造一個32K「字典」，它包含200萬個字符串中最常見的子字符串。然後，每個字符串可以使用32K來繪製匹配。如果你的字符串具有這種共性，那麼你可以接近相同的壓縮。 （請參閱zlib'sdeflateSetDictionary()和inflateSetDictionary()函數。）