Сжатие в Скале

Question

Я работаю над Scala с ОЧЕНЬ большими списками Int (может быть large ), и мне нужно сжать их и сохранить в памяти.

Единственное требование - чтобы я мог вытащить (и распаковать) первое число в списке для работы, не касаясь остальной части списка.

У меня много хороших идей, но большинство из них переводят числа в биты. Пример:

Вы можете написать любое число x в качестве кортежа | log (x) |, x- | log (x) | первый элемент мы исправляем как строку из 1 и 0 в конце (унарный код), а второй - в двоичном. например:

1 -> 0,1 -> 0 1

...

5 -> 2,1 -> 110 01

...

8 -> 3,0 -> 1110 000

9 -> 3,1 -> 1110 001

...

В то время как Int занимает фиксированные 32 бита памяти и длинные 64, при таком сжатии x требуется 2log (x) битов для хранения и может расти бесконечно. Это Сжатие действительно уменьшает память в большинстве случаев.

Как бы вы обработали данные такого типа? Есть ли что-то вроде bitarray или что-то еще?

Есть ли другой способ сжать такие данные в Scala?

Спасибо

Answer 1

В зависимости от разреженности и диапазона вашего набора данных, вы можете хранить свои данные в виде списка дельт вместо цифр. Например, он используется для сжатия звука и может быть как с потерями, так и без потерь, в зависимости от ваших потребностей.

Например, если у вас есть Int числа, но вы знаете, что они вряд ли когда-нибудь будут больше, чем (подписано) Byte, вы можете сделать что-то вроде этого списка байтов:

-1           // Use -1 to imply the next number cannot be computed as a byte delta
0, 0, 4, 0   // 1024 encoded as bytes
1            // 1025 as a delta
-5           // 1020 as a delta
-1           // Next number can't be computed as a byte delta
0, 0, -1, -1 // 65535 encoded as bytes -- -1 doesn't have special meaning here
10           // 65545 as a delta

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

Перечитывая ваш вопрос, кажется, вы не отбрасываете методы сжатия, которые превращают данные в биты. Если нет, то я предлагаю Хаффмана - прогнозирующего, если нужно - или что-то из семьи Лемпель-Зив.

И, к сожалению, у Scala нет библиотеки для обработки двоичных данных. Хотя в paulp, вероятно, есть что-то подобное в самом компиляторе.