Кодирование - эффективно отправлять разреженный логический массив

Question

У меня есть 256 x 256 булевский массив. Эти массивы постоянно меняются, и бит устанавливается практически случайно.

Мне нужно отправить текущий список установленных бит на многие клиенты по мере их запроса.

Следующие числа являются приблизительными.

Если я пошлю координаты для каждого набора бит:

set bits data transfer (bytes) 
    0   0 
    100   200 
    300   600 
    500   1000 
1000   2000 

Если я посылаю расстояние (сканирование слева направо) на следующий установленный бит:

set bits data transfer (bytes) 
    0    0 
    100   256 
    300   300 
    500   500 
1000   1000 

Типичное количество биты, которые установлены в этом разреженном массиве, составляют около 300-500, поэтому второе решение лучше.

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

Answer 1

Поскольку вы говорите «практически случайным образом распределенным», давайте предположим, что каждое место - это исследование Бернулли с вероятностью p. p выбирается так, чтобы получить желаемую скорость заполнения. Вы можете подумать о длительности «пробега» (ваш вариант 2) в качестве количества испытаний Бернулли, необходимых для достижения успеха. Оказывается, это число испытаний следует за геометрическим распределением (с вероятностью р). http://en.wikipedia.org/wiki/Geometric_distribution

Что вы сделали до сих пор в варианте № 2, чтобы определить максимальную длину прогона в каждом случае p и зарезервировать это множество бит для отправки всех из них. Обратите внимание, что эта максимальная длина по-прежнему остается лишь вероятностью, и схема будет терпеть неудачу, если вы получите ДЕЙСТВИТЕЛЬНО ДЕЙСТВИТЕЛЬНО неудачу, и все ваши биты сгруппированы в начале и конце.

Как @Mike Dunlavey рекомендует в комментарии, кодирование Хаффмана или какую-либо другую форму энтропийного кодирования, может перераспределить бит, потраченный в соответствии с частотой длины. То есть короткие прогоны намного более распространены, поэтому используйте меньшее количество бит для отправки этих длин. Теоретический предел для этой эффективности кодирования - это «энтропия» распределения, которую вы можете посмотреть на этой странице в Википедии, и оценить разные вероятности. В вашем случае эта энтропия колеблется от 7,5 бит за один проход (за 1000 записей) до 10,8 бит за ход (за 100).

На самом деле, это означает, что вы не можете сделать намного лучше, чем вы делаете сейчас в случае ввода 1000. 8 бит = 1 байт за значение. В случае 100 записей вы в настоящее время тратите 20,5 бита на один прогон вместо теоретически возможных 10.8, так что у конечной точки есть максимальный шанс для улучшения. И в случае 300: я думаю, вы не зарезервировали достаточно битов для представления этих последовательностей. Энтропия выходит в 9,23 бит на пиксель, и вы в настоящее время отправляете 8. Вы найдете много случаев, когда пробел между true превышает 256, что переполнит ваше представление.

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

Наконец, также обратите внимание, что настоящие энтропийные кодеры только приближают энтропию. Например, Huffman coding должен назначать целое число бит для каждой длины выполнения. Arithmetic coding может назначать дробные биты.