Кодировка двоичной длины пробега

Question

У меня есть веб-форма, для содержимого которой я хотел бы создать короткое представление в Base64. Форма, между прочим, содержит список из 264 двоичных значений, большая часть которых будет равна 0 в любой момент времени. (Они представляют регионы на географической карте). Даже в Base64 это 264-битное число генерирует длинную, запугающую строку. Я хочу как можно эффективнее внедрить кодирование во всю длину. ты можешь помочь мне с этим? Я искал бинарный RLE, но не нашел ничего полезного.

То, что я попробовал это далеко - работает РЛЭ на двоичную строку, используя десятичные счетчики и «A» в качестве разделителя, обозначающее изменение между 0 и 1, то преобразование результата от основания 11 на базу 64. Для пример:

00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100 

становится

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A 

, который, в свою очередь, становится

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o 

или, в базе 62,

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK 

Это лучше, но я до сих пор не могу помочь, но сомневаюсь, что, если я делаю что-то неправильно - использует цифру «A» в качестве разделителя является лучшим способом сделай это?

И еще одно обновление:

Благодаря @comingstorm, я сократил сжатые строки несколько больше.

ILHHASCAASBYwwccDASYgAEgWDI= 

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

Answer 1

Поскольку вы кодируете биты, вы, вероятно, захотите использовать RLE на основе бит вместо байт-основанного. В этом контексте вы должны рассмотреть Elias gamma coding (или какой-либо вариант) для эффективного кодирования длины выполнения.

Разумное первое приближение для формата кодирования может быть:

• первого бит = таким же, как первый бит несжатой строки (чтобы установить первоначальную полярность)
• оставшихся бит: Элиас кодированных длины последовательного (чередующиеся 1 и 0)

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

Обратите внимание, что всегда возможно «сжатие» длины выполнения для расширения вашей битовой строки; если вас это беспокоит, вы можете добавить еще один начальный бит, чтобы указать, находятся ли ваши данные в сжатом или несжатом формате, ограничивая накладные расходы на сжатие до 1 бит.

Answer 2

Альтернативой, что я думаю, что это более, что вы хотите разреженная матрица: http://en.wikipedia.org/wiki/Sparse_matrix

Answer 3

264 бит, что только 33 байт, а в base64 только 44 байта. Я думаю, что этот (очень маленький) объем информации вряд ли сжимается. Редкое представление nulvinge означает, что он просто хранит ненулевые элементы и их значения (как у вас есть только 0/1), то есть в вашем случае просто индекс ненулевых битов. Но поскольку у вас есть 264 возможных бита - вам нужно 9 бит для индекса, а это значит, что если у вас есть более 29 ненулевых записей, вам нужно уже больше, чем оригинал.

Возможно, ваш вопрос сформулирован неправильно, но я не вижу, как 264 бита могут привести к запугивающей строке base64 (как вы его генерируете - возможно, вы переводите не 264 бита, а 264 символа ASCII (со значением 0 и 1) - это объясняет вашу длинную строку результата?).