Оптимизировать массив трибунов для космоса

Question

Позвольте мне начать с некоторого фона:

Под «трибоулем» я понимаю переменную, которая может содержать одно из следующих значений: true, false или null.

В вопросе Копируя массив целых и указателей в bools , ОП хотел иметь массив трибоолов (более или менее), который был бы как можно меньше.

Имея "немного" самого базового бит-фу, я нашел решение, которое использовало 2 бита на трибула и позволяло хранить массив OP из 64 трибул в 16 байтах, что нормально.

Механика трибула, которую я использовал, была проста, как:

• логический A означает «ноль или не ноль»,
• логическое значение B означает «истина или ложь, если не ноль».

---

Но потом я подумал ... Алгоритмическое определение «бита»:

A бит - это объем информации, который указывает, какое из двух одинаково вероятных событий должно произойти.

Очевидно, что значение true / false составляет 1 бит. Два значения true-false в целом имеют размер 2 бита.

А как насчет нашего концептуального трибуна?

Моя точка зрения такова: С точки зрения размера содержащейся информации трибула больше 1 бита, но меньше 2 бит .

• Обоснование 1: Предположим, мы реализуем нашу логическую переменную if, как описано выше. Если логическое значение A равно нулю, значение логического значения B является избыточным и не содержит никакой соответствующей информации.
• Обоснование 2: Невозможно хранить информацию из двух независимых логических значений в одной трибоуле, поэтому она имеет

(Ничто из вышеперечисленного не является формальным доказательством, но я считаю, что мы можем согласиться с тем, что «размер» трибула строго больше 1 бита и строго меньше 2).

---

Мой вопрос:

Как программно воспользоваться преимуществом того факта, что трибула имеет меньше информации, чем 2 бита, и реализовать в программном обеспечении (c, c ++?) массив из N трибулей, который будет иметь память занимаемая площадь меньше N/4 байтов для некоторых N?

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

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

Answer 1

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

Самый простой способ подумать об этом - представить кодирование вашего массива «трибоул» в виде числа в базе 3 - например, 0 = ЛОЖЬ, 1 = ИСТИНА, 2 = НУЛЬ. Тогда следующий массив:

{TRUE, FALSE, NULL, NULL, FALSE, FALSE, TRUE}

кодируется в число

1022001

, который затем можно преобразовать в десятичное число обычным способом:

(1*3^0)+(0*3^1)+(0*3^2)+(2*3^3)+(2*3^4)+(0*3^5)+(1*3^6) = 946

Каждый трибоул занимает ln (3) / ln (2) бит (около 1,58), поэтому, используя этот метод, вы можете хранить 20 трибул в 32 битах, чтобы вы могли хранить массив N=20 в 4 байта (где 1015 * - это 5).

Answer 2

Вы можете теоретически упаковать X переменных N-состояния в

ln(N^X) / ln M

M-состояния (или log_M (N ^ X) в LaTeX-подобной записи) переменных.Для хранения переменных трех состояний в двоичных разрядах приведенная выше формула выглядит следующим образом:

ln(3^N) / ln 2

Например, в 8-битном байте можно разместить 5 переменных трех состояний.

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

Следует отметить, что байт для 5 переменных с тремя состояниями довольно экономичен в пространстве.Плотность остается неизменной для каждого байта, пока у вас не будет пакета из 22 байтов, который может соответствовать 111 значениям трех состояний вместо 110. Однако обработка такого типа упаковки может привести к путанице.

Любойстоит ли дополнительной работы по сравнению с непосредственным сохранением 4-х значений трех состояний в байте?

Answer 3

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

3 ** 5 == 243, то есть почти 256. Это означает, что вы можете легко сжать 5 значений трибула в байте. Он имеет ту же степень сжатия, но поскольку каждый байт независим, он может быть реализован с использованием LUT:

unsigned char get_packed_tribool(unsigned char pk, int num)
{ // num = (0..4), pk = (0..242)
    return LUT[num][pk];    // 5*243 bytes of LUTs
};

unsigned char update_packed_tribool(unsigned char old_pk, int num, int new_val)
{ // new_val = 0..2
    return old_pk + (new_val - LUT[num][old_pk])*POW3_LUT[num];
};

Answer 4

@ psmears верно, для случая, когда все 3 значения одинаково вероятны.Однако, если они не были одинаково вероятны или не были независимыми, если у вас была достаточно длинная строка из них, вы можете просто использовать 2-битное или любое другое кодирование и запустить на нем gzip .Это должно сжать его примерно до теоретического предела.Как и в пределе, где все значения были равны 0, он должен быть не намного больше, чем лог длины строки.

Кстати: мы говорим о энтропии здесь,Простое определение в этом случае: -P (0) logP (0) - P (1) logP (1) - P (null) logP (null).Так, например, если P (0) = P (1) = 1/2 и P (null) = 0, то энтропия равна 1 биту.Если P (0) = 1/2, P (1) = 1/4, P (ноль) = 1/4, то энтропия также равна 1/2 * 1 + 1/4 * 2 + 1/4 * 2= 1 битЕсли вероятности составляют 1022/1024, 1/1024, 1/1024, то энтропия равна (почти 1) * (почти 0) + 10/1024 + 10/1024, что примерно равно 20/1024 или примерно 2 сотых долей !Чем более определенным является что-то, тем меньше оно сообщает вам, когда это происходит, тем меньше места требуется.

Answer 5

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

Затем можно кодировать его следующим образом:

0 для нуля 1 для ненулевого значения, а затем 1 или 0 для истины или ложи.

Это приведет кмаксимум 2 бита на трибула и всего 1 бит, если все они нулевые.