Сжатие коротких английских строк в Python?

Question

Я бы хотел разместить в памяти строки длиной 80M длиной <20 символов и использовать как можно меньше памяти. </p>

Мне нужна библиотека сжатия, которую я могу использовать из Python, которая позволит мне сжимать короткие (<20 символов) английские строки. У меня их около 80 миллионов, и я бы хотел, чтобы они занимали как можно меньше памяти. </p>

Я бы хотел максимальное сжатие без потерь. Процессорное время не является узким местом.

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

Я хочу сжать до <20% от исходного размера. Это правдоподобно, учитывая, что верхняя граница энтропии английского языка составляет 1,75 бита (Brown et al, 1992, <a href="http://acl.ldc.upenn.edu/J/J92/J92-1002.pdf" rel="nofollow">http://acl.ldc.upenn.edu/J/J92/J92-1002.pdf) = 22% сжатия (1,75 / 8).

Edit:

Я не могу использовать zlib, потому что заголовок слишком большой. (Если у меня есть строка, начинающаяся с 20 байтов, для хорошего сжатия заголовка НЕТ. Заголовок zlib = 200 байт согласно Роланду Иллингу. У меня нет двойной проверки, но я знаю, что она больше 20.)

Кодирование Хаффмана звучит хорошо, за исключением того, что оно основано на отдельных токенах и не может выполнять нграммы (несколько символов).

smaz имеет дерьмовый словарь и сжимает только до 50%.

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

Answer 1

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

Поэтому создайте одну строку со всем требуемым содержимым и сожмите всесразу с любым решением.Это также решает проблему «слишком большой заголовок».

Вы можете сделать это различными способами.Вероятно, самое простое - создать repr() списка строк;или вы можете использовать модули pickle, shelve или json для создания какого-либо другого вида сериализованной формы.

Answer 2

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

Во-вторых, 80M строк это много, и если вам придется распаковать их все, чтобы извлечь одну из них, вы будетенедоволен производительностью.Разделите ваш вход на меньшие, но все еще достаточно большие блоки.Типичное значение будет 64 КБ, что означает 3200 строк.

Затем вы можете сжимать каждый блок размером 64 КБ независимо.Когда вам нужно получить доступ к одной строке в блоке, вам нужно декодировать весь блок.

Итак, здесь есть компромисс для выбора между степенью сжатия (которая предпочитает большие блоки) и скоростью произвольного доступа(которые предпочитают меньшие блоки).Вы будете судить, чтобы выбрать лучший.

Быстрое примечание: произвольный доступ к структуре в памяти обычно предпочитает алгоритм быстрого сжатия, а не сильный.Если вы сжимаете только один раз, но произвольный доступ много раз, предпочтите некоторые сильно ассиметричные алгоритмы, такие как LZ4-HC: http://code.google.com/p/lz4hc/

Согласно тесту, скорость сжатия составляет всего 15 МБ / с, но скорость декодированиясоставляет около 1 ГБ / с.Это переводит в 16K блоков по 64KB в секунду ...

Answer 3

Как насчет использования zipfile из стандартной библиотеки?

Answer 4

В английских строках не более 128 различных символов.Следовательно, вы можете описать каждый символ 7-битным кодом.См. Сжатие UTF-8 (или другого 8-битного кодирования) до 7 или менее битов

Answer 5

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