Сжатие небольшого количества данных

Question

У меня есть программа, в которой я генерирую потоки битов, примерно от 80 до 150 бит или около того, которые я хотел бы сжать, потому что я собираюсь превратить их в некую строку ASCII, чтобы люди могли передавать их вокруг.

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

Дополнительно:

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

Вот пример для тех, кто хотел бы его увидеть. Я добавлю форматирование, чтобы его было легче читать:

110 110 - This is a 6x6 grid (the maximum is 7x7, so we only need 3 bits!)

000000
011110
010010
010010
011110
000000 - This is one layout grid

000000
000000
001000
000100
000000
000000 - This is the second layout grid

Теперь перечислим несколько штук

010 11111111 - A piece is a 3-bit colour code, then an 8-bit list of 'on / off' bits.
001 10101010 - Another bit!
001 10101010 - Another, identical bit!

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

Answer 1

Чего вы надеетесь достичь, сжав 150 бит? Если вы не соберете несколько из этих 19b сообщений, я не уверен, что вы надеетесь получить. Это проблема пользовательского интерфейса - когда вы хотите, чтобы ваши пользователи отправляли / получали «коды»?

Как насчет base 64 кодировки ? Это будет принимать двоичные данные и превращать их в кодированные символы для легкой передачи или ввода.

Answer 2

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

http://en.wikipedia.org/wiki/Run-length_encoding

Будет хорошо работать со всеми этими последовательными нулями.

Итак, основная причина сжатия этих строк в том, чтобы их было легче вырезать и вставлять? Имеет смысл; это звучит как интересный проект.

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

Удачи!

Answer 3

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

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

Answer 4

Мое первое предложение - посмотреть кодировку диапазона . Вместо

1: сжатие битовых данных в двоичные данные, а затем

2: кодирование двоичных данных в данные base64 ASCII,

вы можете упаковать свои биты непосредственно в диапазон 0- N (где N - это количество печатаемых символов, которые вы используете минус 1), а затем выполнить непростое отображение.

Мое второе предложение - изучить методы фильтрации, используемые PNG, и подумать о том, можно ли использовать подобные методы, чтобы сделать ваши данные более сжимаемыми. Трудно сказать только из двух примерных сеток компоновки, но из вашей первой сетки очень вероятно, что какой-то метод, такой как «предсказать каждый пиксель на основе его соседей сверху и слева, а затем преобразовать каждый пиксель в 0, если он соответствует Предсказание и 1, если оно не поддается прогнозу, "может дать вам гораздо более однородный набор данных и, следовательно, большее сжатие.

Answer 5

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

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

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

Answer 6

Поскольку потоки такие маленькие, вы можете опубликовать некоторые из них здесь?

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

Это своего рода длинный снимок, но при отсутствии каких-либо конкретных ответов вы можете заглянуть в сцену ПЗУ и проверить, как строки текста были сжаты в играх на основе картриджей, таких как «Chrono Trigger» или «Final». Фантазия III. " Я знаю, что текстовые строки были сжаты в этих играх (в те времена байты были так ценны), и распутывание схемы оказалось интересной задачей для хакеров. Это только вещь, которая пришла мне в голову, когда вы упомянули множество сжатых коротких маленьких строк.

Однако ваша корневая проблема может остаться. Я полагаю, что схемы сжатия в этих ПЗУ используют избыточность во многих строках (т. Е. Если «Тимбукту» встречается в 58 разных строках), а не в одном потоке.

Answer 7

JBIG может дать вам то, что вам нужно.

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

http://www.jpeg.org/jbig/index.html

http://www.cl.cam.ac.uk/~mgk25/jbigkit/

JBIG используется для сжатия факсимильных изображений размером 1 бит / с.

Answer 8

CCITT Группы 3 и Группы 4 схемы кодирования без потерь, используемые при сжатии TIFF G3 и G4, были разработаны с учетом двоичных данных. GIF TIFF - это черно-белые изображения, обычно используемые для распознавания текста и факсов. На ум приходит еще одна простая схема: RLE .

Answer 9

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

Что касается битов против ascii - я не совсем уверен, к чему вы клоните, но, как упоминал Майкл, Base64 предоставляет способ сделать произвольный двоичный код более дружественным.

Обратите внимание, что любое преобразование из двоичного файла в ascii является противоположностью сжатия.

Answer 10

У меня была та же мысль, что и у Тима - такое небольшое количество данных едва ли стоит сжимать. На самом деле, я бы предположил, что вы действительно хотите рассмотреть какой-то метод кодирования ascii, такой как uuencode или mime-encode (он же " Base64 ").