Есть ли способ сжать строку в меньшую строку с обратимостью?
Я пытаюсь передать строки по сети iridium, и затраты на отправку данных довольно велики. Мне интересно, если есть способ сжать большую строку, например:
{"packet":01,"reporting time":1500, "altitude":6500,"latitude":0,"longitude": 0,"ballast":34,"parachute":0}
в гораздо меньшую строку, как: f5fk43d2 , Процесс должен быть обратимым, чтобы данные могли быть декодированы и прочитаны на другом конце. Возможно ли это, если да, как бы я поступил так?
Я попробовал этот ответ с помощью jwr: сокращение строки в Java, однако это кажется необратимым. Он конвертирует большую строку в меньшую.
Процесс должен привести к строке меньше, чем оригинал.
Любая помощь приветствуется!
3 ответа
Во-первых, мы надеемся, что ясно, что не существует никакого алгоритма сжатия без потерь, который может принимать произвольную строку длины n и всегда сжимать ее в уникальную более короткую строку. Это факт математики.
При этом есть некоторые популярные алгоритмы, которые работают довольно хорошо:
Кодировка Хаффмана: довольно удобна для начинающих и может быть реализована самостоятельно. Основная идея состоит в том, чтобы сопоставить более общие символы с более короткими двоичными строками, а менее распространенные - с более длинными двоичными строками, а затем упаковать их в карту, которая скажет вам, как декодировать результирующую цепочку битов. Недостатком является дополнительное пространство, необходимое для хранения инструкций по декодированию.
Лемпель-Зив: я никогда не реализовывал это сам, но это основа для многих распространенных форматов файлов, которые мы знаем сегодня, таких как GIF. Там должны быть библиотеки для этого.
Рассмотрим математику попыток преобразовать некоторую строку символов 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) не может быть инъективным, то есть не существует действительного обратного).
Таким образом, недостаточно двухсимвольных строк, чтобы, возможно, отобразить их обратно на каждую трехсимвольную строку, и вы обнаружите, что это обобщает все X > Y.
Вы могли бы ограничить некоторые символы из области ваших больших строк, хотя в точности, как вы заявили о проблеме, это невозможно.
Отредактируйте, потому что я чувствую, что должен упомянуть следующее: существуют алгоритмы, используемые для сжатия строк меньших символов в меньшие строки большего количества символов. Учитывая сказанное, я бы рекомендовал взглянуть на это: эффективный алгоритм сжатия коротких текстовых строк.
Давайте начнем с вашего примера в качестве характеристики вашего смутного "гораздо меньше". Вы сжимаете 107 символов (856 бит) в восемь буквенно-цифровых символов, которые в любом случае ограничены 36 возможностями для каждого символа. Я буду щедрым и предположу, что заглавные буквы также разрешены, и, возможно, два знака препинания для специй, увеличивая его до 64 возможных символов. Так что это шесть бит на символ умножить на восемь символов или 48 бит. Это фактор сжатия 18. Нет, вы не получите этого без потерь, по крайней мере, без огромного количества избыточности в данных, которые не были продемонстрированы в примере. Я снова буду щедрым и предположу, что сжатые сообщения ограничены 96 возможными символами ASCII (скажем, удаление 127 и включение новой строки). Тогда сообщение составляет 705 бит с коэффициентом сжатия почти 15, чтобы получить 48 бит. Все еще не происходит.
Сжатие без потерь происходит от статистического смещения и избыточности. Статистическое смещение - это преобладание одних символов над другими, а избыточность - это повторяющиеся шаблоны в данных, например, повторяющиеся подстроки, такие как "itude" и "500" в вашем примере. Чтобы получить хорошее сжатие, вам нужно использовать эти вещи, и вам нужно много данных, чтобы использовать их в своих интересах. Короткие строки, подобные вашему примеру, вряд ли будут сжиматься или часто вообще не сжиматься, если их брать изолированно.
Вы можете попытаться сохранить контекст сжатия и связанный с ним декомпрессированный контекст на другом конце, через который вы отправляете серию сообщений в четко определенном порядке. Т.е. их нужно распаковывать в том же порядке, в котором они были сжаты. Тогда вы сможете воспользоваться избыточностью и смещением для многих сообщений и, возможно, получить приличное сжатие. Если те же свойства JSON продолжают появляться, и еще лучше, если они часто имеют одинаковые значения, вы можете получить значительное сжатие.
Операция очистки, например, zlib, позволила бы посылать сжатые до сих пор данные, чтобы избежать задержки, которую компрессор мог бы создать для создания блока. Вы бы хотели избегать сбросов, если это возможно, поскольку они уменьшают сжатие. Таким образом, у вас может быть ограничение по времени, в течение которого вы готовы подождать, пока другое сообщение не будет отправлено, прежде чем сбросить последнее отправленное сообщение.