Есть ли способ сжать строку в меньшую строку с обратимостью?

Question

Я пытаюсь передать строки по сети iridium, и затраты на отправку данных довольно велики.Мне интересно, есть ли способ сжать большую строку, например: {"packet":01,"reporting time":1500, "altitude":6500,"latitude":0,"longitude": 0,"ballast":34,"parachute":0}

в намного меньшую строку, например: f5fk43d2 .Процесс должен быть обратимым, чтобы данные могли быть декодированы и прочитаны на другом конце.Возможно ли это, если да, как бы мне поступить так.

Я попробовал этот ответ с помощью jwr: Сокращение строки в Java , однако это кажется необратимым.Он конвертирует большую строку в меньшую.

В результате процесса должна получиться строка, меньшая оригинала.

Любая помощь приветствуется!

Answer 1

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

Тем не менее, есть некоторые популярные алгоритмы, которые работают довольно хорошо:

Кодировка Хаффмана : довольно удобна для начинающих и может быть реализована самостоятельно.Основная идея состоит в том, чтобы сопоставить более общие символы с более короткими двоичными строками, а менее распространенные - с более длинными двоичными строками, а затем упаковать их в карту, которая скажет вам, как декодировать результирующую цепочку битов.Недостатком является дополнительное пространство, необходимое для хранения инструкций по декодированию

Lempel-Ziv : я никогда не реализовывал это сам, но это основа для многих распространенных форматов файлов, которые мы знаемсегодня как гифки.Для этого должны быть библиотеки.

Answer 2

Давайте начнем с вашего примера в качестве характеристики вашего расплывчатого "гораздо меньшего размера".Вы сжимаете 107 символов (856 бит) в восемь буквенно-цифровых символов, которые в любом случае ограничены 36 возможностями для каждого символа.Я буду щедрым и предположу, что заглавные буквы также разрешены, и, возможно, два знака препинания для специй, увеличивая его до 64 возможных символов.Так что это шесть бит на символ умножить на восемь символов или 48 бит.Это фактор сжатия 18.Нет, вы не получите этого без потерь, по крайней мере, без огромного количества избыточности в данных, которые не были продемонстрированы в примере.Я снова буду щедрым и предположу, что сжатые сообщения ограничены 96 возможными символами ASCII (скажем, удаление 127 и включение новой строки).Тогда сообщение составляет 705 бит с коэффициентом сжатия почти 15, чтобы получить 48 бит.Все еще не происходит.

Сжатие без потерь происходит из-за статистической погрешности и избыточности.Статистическое смещение - это преобладание одних символов над другими, а избыточность - это повторяющиеся шаблоны в данных, например, повторяющиеся подстроки, такие как «itude» и «500» в вашем примере.Чтобы получить хорошее сжатие, вам нужно использовать эти вещи, и вам нужно много данных, чтобы использовать их в своих интересах.Короткие строки, подобные вашему примеру, вряд ли будут сжиматься или часто вообще не сжиматься, если их использовать изолированно.

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

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

Answer 3

Рассмотрим математику попыток преобразовать некоторую строку символов X в строку символов Y, так что X> Y (то есть вы пытаетесь сократить длину строки).

Тогда, скажем, строка является буквенно-цифровой;это дает нам 26 возможных строчных букв, 26 возможных заглавных букв и 10 возможных цифр, которые мы можем использовать (то есть 62 варианта).Это означает, что для X-символьной строки у нас будет 62 ^ X возможных строк, а для Y-символьной строки у нас будет 62 ^ Y возможных строк.

Теперь рассмотрим, попробуем ли мы сопоставить все наши строки X-символов с нашими строками Y-символов.Давайте позволим функции f (S) отобразить строку S (X-символьную строку) в Y-символьную строку.Тогда, поскольку X> Y, мы обязательно должны отобразить некоторые строки X-символов на некоторые из тех же строк Y-символов.Рассмотрим следующий простой пример:

X = 3. Y = 2. Тогда у нас есть 62 ^ 3 возможных 3-символьных строки (238 000) и 62 ^ 2 (3800) возможных Y-символьных строк.Затем мы имеем на 234 000 больше трехсимвольных строк, чем двухсимвольных.

Теперь представьте, что мы попытались создать некоторую функцию f (S), в которой мы пытались превратить каждую 3-символьную строку в 2-символьную строку.Тогда у нас, естественно, возникнет проблема, когда мы попытаемся преобразовать 2-символьную строку обратно в 3-символьную строку, потому что это означает, что f (S) должен преобразовать некоторые 3-символьные строки в одну строку (поэтому мы не моглине знаю, на какую карту вернуться!).Это связано с тем, что область 2-символьных строк меньше, чем область 3-символьных строк (и происходит потому, что f (S) не может быть инъективной, т. Е. Нет действительного обратного).

Таким образом, существует2-символьных строк недостаточно для сопоставления с каждой 3-символьной строкой, и вы обнаружите, что это обобщает все X> Y.

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

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