Кодирование длины двоичного прогона - PullRequest
Новая
       51

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

5 голосов
/ 29 сентября 2011

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

Что я пробовал до сих пор - запуск RLE для двоичной строки с использованием десятичных счетчиков и «A» в качестве разделителя, обозначающего изменение между 0 и 1, а затем преобразование результата из базы 11 в базу 64. Например: 

00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100

становится 

10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A

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

CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o

или, в базе 62, 

6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK

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

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

Благодаря @ comingstorm я сократил сжатую строку еще немного. 

ILHHASCAASBYwwccDASYgAEgWDI=

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

Ответы [ 3 ]

6 голосов
/ 30 сентября 2011

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

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

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

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

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

1 голос
/ 29 сентября 2011

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

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

0 голосов
/ 29 сентября 2011

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

...