Сжать длинный список коротких строк

Question

У меня есть длинный список коротких строк, которые я хочу сжать, но я хочу иметь возможность распаковывать произвольную строку в списке в любое время, не распаковывая весь список.

Я знаю список заранее, и неважно, сколько времени занимает предварительная обработка. Также хорошо, если есть некоторые значительные O(1) накладные расходы памяти.

Я понимаю, что мог бы просто сжать каждую строку независимо с помощью какого-либо алгоритма сжатия без потерь, но это не сработает очень хорошо, потому что строки очень короткие и каждая не содержит большой избыточности. Однако во всем списке много избыточности.

Answer 1

Я бы рекомендовал сжимать строки длиной около 64 КБ (около 32 строк), требуя, чтобы вы в среднем распаковывали только 16 строк, чтобы получить ту, которую вы хотите. В отличие от 1 000 000. Вы получите почти такое же сжатие с помощью deflate (метод сжатия, используемый gzip).

Альтернативой, также использующей deflate, будет создание 32-словарного "словаря", который состоит из наиболее часто встречающихся подстрок в ваших 2 000 000 строк. Затем каждую строку можно сжать индивидуально, используя те 32 КБ, из которых можно извлечь совпадения. Если ваши строки имеют такой тип общности, то вы можете приблизиться к тому же сжатию. (См. Злиба deflateSetDictionary() а также inflateSetDictionary() функции.)