Я не очень разбираюсь в Java, поэтому думаю, что мое решение должно быть общим:)
1. Сжать списки
Поскольку логические значения неэффективны, каждый List<Boolean> должен быть сжат до List<Byte>, это просто, просто захватите их по 8 за раз.
Последний «байт» может быть неполным, поэтому вам, конечно, нужно сохранить количество битов, закодированных.
2. Сериализация списка элементов
У вас есть 2 способа продолжить: либо вы кодируете количество элементов в списке, либо вы используете шаблон, чтобы отметить конец. Я бы порекомендовал кодировать количество элементов, шаблонный подход требует экранирования, и это жутко, плюс это сложнее с упакованными битами.
Для кодирования длины вы можете использовать переменную схему: то есть количество байтов, необходимое для кодирования длины, должно быть пропорционально длине, один из которых я уже использовал. Вы можете указать, сколько байтов используется для кодирования самой длины, используя префикс первого байта:
0... .... > this byte encodes the number of items (7 bits of effective)
10.. .... / .... .... > 2 bytes
110. .... / .... .... / .... .... > 3 bytes
Это довольно экономно, и декодирование происходит на целых байтах, так что не слишком сложно. Можно заметить, что это очень похоже на схему UTF8:)
3. Применить рекурсивно
List< List< Boolean > > становится [Length Item ... Item], где каждый Item является представлением List<Boolean>
4. Zip
Полагаю, для Java доступна библиотека zlib или что-то еще, например deflate или lcw. Передайте его в буфер и убедитесь, что вы хотите максимально сжать, сколько бы времени это ни потребовало.
Если в вашем представлении есть какой-либо повторяющийся шаблон (даже тот, который вы не видели), он должен быть в состоянии сжать его. Не доверяйте этому тупо, хотя и проверяйте, что «сжатая» форма легче, чем «несжатая», это не всегда так.
5. Примеры
Где замечено, что отслеживание края списков занимает много места:)
// Tricky here, we indicate how many bits are used, but they are packed into bytes ;)
List<Boolean> list = [false,false,true,true,false,false,true,true]
encode(list) == [0x08, 0x33] // [00001000, 00110011] (2 bytes)
// Easier: the length actually indicates the number of elements
List<List<Boolean>> super = [list,list]
encode(super) == [0x02, 0x08, 0x33, 0x08, 0x33] // [00000010, ...] (5 bytes)
6. Потребление пространства
Предположим, у нас есть List<Boolean> из n логических значений, пространство, используемое для его кодирования:
booleans = ceil( n / 8 )
Для кодирования количества бит (n) нам понадобится:
length = 1 for 0 <= n < 2^7 ~ 128
length = 2 for 2^7 <= n < 2^14 ~ 16384
length = 3 for 2^14 <= n < 2^21 ~ 2097152
...
length = ceil( log(n) / 7 ) # for n != 0 ;)
Таким образом, чтобы полностью закодировать список:
bytes =
if n == 0: 1
else : ceil( log(n) / 7 ) + ceil( n / 8 )
7. Маленькие списки
Существует один угловой случай: нижний предел спектра (т. Е. Почти пустой список).
Для n == 1, bytes оценивается как 2, что действительно может показаться расточительным. Однако я не буду пытаться угадать, что произойдет, когда произойдет сжатие.
Возможно, вы захотите упаковать еще больше. Это возможно, если мы откажемся от идеи сохранения целых байтов ...
- Сохраняйте кодировку длины как есть (на целых байтах), но не добавляйте
List<Boolean>. Список из одного элемента становится 0000 0001 x (9 бит)
- Попробуйте также "упаковать" кодировку длины
Второй пункт сложнее, мы фактически используем кодирование двойной длины:
- Указывает, сколько битов кодируют длину
- Фактически кодировать длину в этих битах
Например:
0 -> 0 0
1 -> 0 1
2 -> 10 10
3 -> 10 11
4 -> 110 100
5 -> 110 101
8 -> 1110 1000
16 -> 11110 10000 (=> 1 byte and 2 bits)
Работает очень хорошо для очень маленьких списков, но быстро вырождается:
# Original scheme
length = ceil( ( log(n) / 7)
# New scheme
length = 2 * ceil( log(n) )
Прорыв? 8
Да, вы правильно прочитали, это лучше только для списка с менее чем 8 элементами ... и только лучше "битами".
n -> bits spared
[0,1] -> 6
[2,3] -> 4
[4,7] -> 2
[8,15] -> 0 # Turn point
[16,31] -> -2
[32,63] -> -4
[64,127] -> -6
[128,255] -> 0 # Interesting eh ? That's the whole byte effect!
И, конечно же, как только компрессия начнет работать, скорее всего, это не будет иметь большого значения.
Я понимаю, что вы, возможно, оцените алгоритм recursive, но я бы все же посоветовал вычислить цифры фактического потребления пространства или, что еще лучше, проверить его с использованием архивирования, примененного к реальным тестовым наборам.
8. Рекурсивное / Переменное кодирование
Я с интересом прочитал ответ TheDon и ссылку, которую он отправил на Elias Omega Coding .
Это разумные ответы в теоретической области. К сожалению, они довольно непрактичны. Основная проблема заключается в том, что у них чрезвычайно интересное асимптотическое поведение, но когда нам действительно нужно кодировать гигабайтные данные? Редко, если вообще когда-либо.
Недавнее исследование использования памяти на работе показало, что большинство контейнеров использовалось для десятка элементов (или нескольких десятков). Только в очень редком случае мы достигаем тысячи. Конечно, для вашей конкретной проблемы лучшим способом было бы на самом деле изучить ваши собственные данные и увидеть распределение значений, но из опыта я бы сказал, что вы не можете просто сосредоточиться на верхнем конце спектра, потому что ваши данные лежат в нижнем конце .
Пример алгоритма TheDon. Скажем, у меня есть список [0,1,0,1,0,1,0,1]
len('01010101') = 8 -> 1000
len('1000') = 4 -> 100
len('100') = 3 -> 11
len('11') = 2 -> 10
encode('01010101') = '10' '0' '11' '0' '100' '0' '1000' '1' '01010101'
len(encode('01010101')) = 2 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 8 = 23
Давайте сделаем небольшую таблицу с различными «порогами», чтобы остановить рекурсию. Он представляет количество битов служебной информации для различных диапазонов n.
threshold 2 3 4 5 My proposal
-----------------------------------------------
[0,3] -> 3 4 5 6 8
[4,7] -> 10 4 5 6 8
[8,15] -> 15 9 5 6 8
[16,31] -> 16 10 5 6 8
[32,63] -> 17 11 12 6 8
[64,127] -> 18 12 13 14 8
[128,255]-> 19 13 14 15 16
Если честно, я сконцентрировался на нижнем конце, и мое предложение подходит для этой задачи. Я хотел подчеркнуть, что это не так ясно, хотя. Тем более, что около 1 функция log является почти линейной, и поэтому рекурсия теряет свое очарование. Порог очень помогает, и 3 кажется хорошим кандидатом ...
Что касается Elias omega coding, это еще хуже. Из статьи в википедии:
17 -> '10 100 10001 0'
Вот и все, 11 бит.
Мораль: вы не можете выбрать схему кодирования без учета имеющихся данных.
Итак, если ваш List<Boolean> не имеет длины в сотни, не беспокойтесь и не придерживайтесь моего маленького предложения.