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

Ответ 1

Я думаю о кодировании такой последовательности:

head  | value
------+------------------
00001 | 0110100111000011

Head имеет переменную длину. Его конец отмечен первым вхождением числа 1. Подсчитайте количество нулей в голове. Длина поля value будет 2 ^ zeroes. Поскольку длина значения известна, это кодирование можно повторить. Поскольку размер Head равен log value, по мере увеличения размера кодированного значения накладные расходы сходятся до 0%.

Добавление

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

head  | length | value
------+--------+-----------
00001 | 1001   | 011011001

Ответ 2

Я не знаю много о 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

Я предполагаю, что существует библиотека zlib, доступная для Java, или что-нибудь еще, например deflate или lcw. Передайте ему свой буфер и убедитесь, что вы хотите как можно больше сжатия, независимо от времени.

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

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, пространство, затраченное на его кодирование:

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 the whole byte effect!

И, конечно же, как только сжатие начнется, возможно, это не имеет большого значения.

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

8. Рекурсивное/переменное кодирование

Я с интересом прочитал ответ TheDon и ссылку, которую он отправил Elias Omega Coding.

Это звуковые ответы в теоретической области. К сожалению, они довольно непрактичны. Основная проблема заключается в том, что они имеют чрезвычайно интересное асимптотическое поведение, но когда нам действительно нужно кодировать данные Gigabyte? Редко, если когда-либо.

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

Пример алгоритма 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> не имеет длины в сотнях, не беспокойтесь и придерживайтесь моего небольшого предложения.

Ответ 3

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

11000101 10010110 00100000

Фактически это означало бы:

   10001 01001011 00100000

Так как целое число продолжается 2 раза.

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

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

РЕДАКТИРОВАТЬ Я не думаю, что существует идеальный способ добиться всего, что вы хотите, сразу. Вы не можете создать информацию из ничего, и если вам нужны целые числа переменной длины, вам, очевидно, придется кодировать и целую длину. Существует неизбежное компромисс между пространством и информацией, но есть также минимальная информация, которую вы не можете вырезать, чтобы использовать меньше места. Никакая система, где факторы растут с разной скоростью, никогда не будет масштабироваться. Это похоже на попытку установить прямую линию по логарифмической кривой. Вы не можете этого сделать. (И кроме того, это точно то, что вы пытаетесь сделать здесь.)

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

Итак, вот моя другая идея: в целочисленном "заголовке" напишите по одному для каждого байта, от которого требуется целое число переменной длины. Первый 0 обозначает конец "заголовка" и начало самого целого.

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

РЕДАКТИРОВАТЬ 2 Вот уравнения:

• Решение одно, 7 бит на бит кодирования (один полный байт за раз):
  y = 8 * ceil(log(x) / (7 * log(2)))
• Решение одного, 3 бита на бит кодирования (один гвоздь за раз):
  y = 4 * ceil(log(x) / (3 * log(2)))
• Решение два, 1 байт на бит кодирования плюс разделитель:
  y = 9 * ceil(log(x) / (8 * log(2))) + 1
• Решение два, 1 nibble на бит кодирования плюс разделитель:
  y = 5 * ceil(log(x) / (4 * log(2))) + 1

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

Ответ 4

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

Отъезд Арифметическое кодирование - он работает на битах и ​​может адаптироваться к динамическим входным вероятностям. Я также вижу, что есть BSD-лицензированная

Ответ 5

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

Конечно, большинство алгоритмов сжатия работают в предположении, что вход каким-то образом повторяется в будущем (или в прошлом), как в семействе компрессоров LZxx, или имеет заданное распределение частот для символов.

Учитывая ваши предпосылки и алгоритмы сжатия, я бы посоветовал сделать следующее:

• Упакуйте биты каждого списка, используя меньшее количество байтов, используя байты как битовые поля, кодируя длину и т.д.
• Попробуйте huffman, арифметику, LZxx и т.д. в результирующем потоке байтов.

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

БЕСПОКОЕННО, вы знаете что-то из своих данных или какое-то преобразование в этих списках, которые заставляют их поднять какой-то шаблон. Возьмем, например, кодирование коэффициентов DCT в кодировке JPEG. Способ перечисления этих коэффициентов (диагональный и зигзагообразный) делается для того, чтобы способствовать формированию паттерна различных коэффициентов преобразования. Таким образом, традиционные результаты сжатия могут быть применены к полученным данным. Если вы знаете что-то из этих списков битов, которые позволяют вам переупорядочивать их более сжимаемым способом (способ, который показывает некоторую структуру), тогда вы получите сжатие.

Ответ 6

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

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

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

http://en.wikipedia.org/wiki/Information_theory

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

Практически вы всегда можете попробовать эффект "jiggle", когда вы кодируете данные несколько раз несколькими способами (попробуйте интерпретировать как аудио, видео, 3d, периодические, последовательные, основанные на ключах, diffs и т.д.) и в несколько страниц и выбрать лучшее. Вы почти гарантированно получите лучшее УЛУЧШЕЕ сжатие, и ваш худший случай будет не хуже вашего исходного набора данных.

Невероятно, если бы это принесло вам теоретические результаты.

Ответ 7

Теоретические пределы

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

Например, из раздел Ограничения в статье Википедии об сжатии без потерь:

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

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

Практический компромисс

Просто используйте Huffman, DEFLATE, 7Z или какой-то ZIP-подобный алгоритм сжатия в полке и enocde бит в виде массивов байтов переменной длины (или списков, или векторов, или того, что они вызывают на Java или на любом языке, который вы как). Конечно, для чтения бит может потребоваться немного декомпрессии, но это можно сделать за кулисами. Вы можете создать класс, который скрывает внутренние методы реализации, чтобы возвращать список или массив логических элементов в некотором диапазоне индексов, несмотря на то, что данные хранятся внутри пакетов массивов пакетов. Обновление булевых индексов индекса или индексов может быть проблемой, но отнюдь не невозможно.

Ответ 8

Список списков-in-Ints-Encoding:

• Когда вы перейдете к началу списка, запишите биты для ASCII '['. Затем перейдите в список.

• Когда вы приходите к произвольному двоичному числу, записывайте биты, соответствующие десятичному представлению числа в ASCII. Например, число 100, напишите 0x31 0x30 0x30. Затем напишите биты, соответствующие ASCII ','.

• Когда вы подходите к концу списка, запишите бит для ']'. Затем напишите ASCII ','.

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

Ответ 9

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

Ответ 10

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

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

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

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

Ответ 11

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

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

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

Ответ 12

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

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

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

Ответ 13

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

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

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

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

Если все внутренние списки имеют одинаковый размер (т.е. у вас есть 2D-массив), вам понадобятся только два измерения.

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

Ответ 14

Список-оф-List-оф-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. 

Ответ 15

У этого вопроса есть определенная индукция. Вам нужна функция: (список списка bool) → (список bool), так что обратная функция (список bool) → (список списка bool) генерирует ту же исходную структуру, а длина кодированного списка bool минимальна, без налагая ограничения на структуру ввода. Поскольку этот вопрос настолько абстрактен, я думаю, что эти списки могут быть невероятно большими - 10 ^ 50, может быть, или 10 ^ 2000, или они могут быть очень маленькими, например, 10 ^ 0. Кроме того, может быть большое количество списков, опять же 10 ^ 50 или просто 1. Таким образом, алгоритм должен адаптироваться к этим широко различным входам.

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

let encode2d(list1d::Bs) = encode1d(length(list1d), true) @ list1d @ encode2d(Bs)
    encode2d(nil)       = nil

let encode1d(1, nextIsValue) = true :: nextIsValue :: []
    encode1d(len, nextIsValue) = 
               let bitList = toBoolList(len) @ [nextIsValue] in
               encode1d(length(bitList), false) @ bitList

let decode2d(bits) = 
               let (list1d, rest) = decode1d(bits, 1) in
               list1d :: decode2d(rest)

let decode1d(bits, n) = 
               let length = fromBoolList(take(n, bits)) in
               let nextIsValue :: bits' = skip(n, bits) in
               if nextIsValue then bits' else decode1d(bits', length)

assumed library functions
-------------------------

toBoolList : int -> bool list
   this function takes an integer and produces the boolean list representation
   of the bits.  All leading zeroes are removed, except for input '0' 

fromBoolList : bool list -> int
   the inverse of toBoolList

take : int * a' list -> a' list
   returns the first count elements of the list

skip : int * a' list -> a' list
   returns the remainder of the list after removing the first count elements

Накладные расходы на каждый отдельный список bool. Для пустого списка накладные расходы - это 2 дополнительных элемента списка. Для 10 ^ 2000 bools накладные расходы будут 6645 + 14 + 5 + 4 + 3 + 2 = 6673 дополнительных элементов списка.

Ответ 16

Если я правильно понимаю, наша структура данных (1 2 (33483 7) 373404 9 (337652222 37333788))

Формат так:

byte 255 - escape code
byte 254 - begin block
byte 253 - list separator
byte 252 - end block

Итак, мы имеем:

 struct {
    int nmem; /* Won't overflow -- out of memory first */
    int kind; /* 0 = number, 1 = recurse */
    void *data; /* points to array of bytes for kind 0, array of bigdat for kind 1 */
 } bigdat;

 int serialize(FILE *f, struct bigdat *op) {
   int i;
   if (op->kind) {
      unsigned char *num = (char *)op->data;
      for (i = 0; i < op->nmem; i++) {
         if (num[i] >= 252)
            fputs(255, f);
         fputs(num[i], f);
      }
   } else {
      struct bigdat *blocks = (struct bigdat *)op->data
      fputs(254, f);
      for (i = 0; i < op->nmem; i++) {
          if (i) fputs(253, f);
          serialize(f, blocks[i]);
      }
      fputs(252, f);
 }

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

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