Самый компактный способ кодирования последовательности двоичных кодов произвольной длины?

Question

Допустим, у вас есть List<List<Boolean>>, и вы хотите закодировать его в двоичную форму максимально компактным способом.

Мне плевать на производительность чтения или записи. Я просто хочу использовать минимальное количество места. Кроме того, пример на Java, но мы не ограничены системой Java. Длина каждого «Списка» составляет неограниченно . Поэтому любое решение, которое кодирует длину каждого списка, должно само по себе кодировать тип данных переменной длины.

С этой проблемой связано кодирование целых чисел переменной длины. Вы можете думать о каждом List<Boolean> как о переменной длине unsigned integer.

Пожалуйста, внимательно прочитайте вопрос. Мы не ограничены системой Java.

EDIT

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

Вы можете думать об этом вопросе по-другому. Допустим, у вас есть список произвольного списка случайных целых чисел без знака (неограниченный). Как вы кодируете этот список в двоичном файле?

Исследования

Я немного прочитал и нашел то, что действительно ищу, это Универсальный код

Результат

Я собираюсь использовать вариант Elias Omega Coding , описанный в статье Новый рекурсивный универсальный код натуральных чисел

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

Answer 1

Список-оф-листа-из-Ints-двоичный:

Start traversing the input list
For each sublist:
    Output 0xFF 0xFE
    For each item in the sublist:
        Output the item as a stream of bits, LSB first.
          If the pattern 0xFF appears anywhere in the stream,
          replace it with 0xFF 0xFD in the output.
        Output 0xFF 0xFC

Декодирование:

If the stream has ended then end any previous list and end reading.
Read bits from input stream. If pattern 0xFF is encountered, read the next 8 bits.
   If they are 0xFE, end any previous list and begin a new one.
   If they are 0xFD, assume that the value 0xFF has been read (discard the 0xFD)
   If they are 0xFC, end any current integer at the bit before the pattern, and begin reading a new one at the bit after the 0xFC.
   Otherwise indicate error. 

Answer 2

Если я правильно понял вопрос, биты являются случайными, и у нас есть список произвольной длины независимо друг от друга. Поскольку байты не имеют ничего общего, я буду обсуждать это как поток битов. Поскольку файлы на самом деле содержат байты, вам нужно будет упаковать восемь битов на каждый байт и оставить 0,7 бита последнего байта неиспользованными.

Самый эффективный способ хранения логических значений - это как есть. Просто выведите их в битовый поток в виде простого массива.

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

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

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

Десериализация: декодировать длины и распределять структуры, затем считывать биты один за другим, назначая их структуре по порядку.

Answer 3

@ ответ zneak (победите меня), но используйте целые числа, закодированные Хаффманом, особенно если некоторые длины более вероятны.

Просто для автономности: закодируйте число списков в виде целого числа, закодированного Хаффманом, затем для каждого списка закодируйте его длину в битах в виде целого числа, закодированного Хаффманом. Биты для каждого списка следуют без промежуточных потерянных битов.

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

Answer 4

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

Однако этого недостаточно. Строка из произвольных 1 и 0 будет выглядеть довольно случайной, и любой алгоритм сжатия выходит из строя по мере увеличения случайности ваших данных - поэтому я бы порекомендовал такой процесс, как сортировка по Бэрроуз-Уилеру, чтобы значительно увеличить количество повторяющихся «слов» или блоки "в ваших данных. Как только это будет завершено, простой код Хаффмана или алгоритм Лемпеля-Зива смогут довольно хорошо сжать ваш файл.

Чтобы позволить вышеуказанному методу работать с целыми числами без знака, вы должны сжать целые числа с помощью дельта-кодов, а затем выполнить сортировку и сжатие блоков (стандартная практика в списках проводок поиска информации).

Answer 5

Ну, во-первых, вы захотите собрать эти логические значения вместе, чтобы получить восемь из них в байт. Стандарт C ++ bitset был разработан для этой цели. Возможно, вам следует использовать его вместо вектора, если вы можете.

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

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

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

Answer 6

Вы можете преобразовать каждый список в BitSet и затем сериализовать BitSet-ы.