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

Question

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

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

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

Answer 1

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

Альтернативой, также использующей дефлят, было бы создание словаря 32K ", который состоит из наиболее часто встречающихся подстрок в ваших 2 000 000 строк. Затем каждая строка может быть сжата индивидуально, используя 32K, из которых можно провести совпадения. Если ваши строки имеют такую ​​общность, то вы можете приблизиться к одному и тому же сжатию. (См. zlib'sdeflateSetDictionary() и inflateSetDictionary().)