Эффективно сжимать строки из 10-1000 символов в Java?

Question

Мне нужно сжать строки (написанные на известном, но переменном языке) длиной от 10 до 1000 символов в отдельные пакеты UDP.

Какие алгоритмы сжатия, доступные в Java, хорошо подходят для этой задачи?

Возможно, для этого есть библиотеки Java с открытым исходным кодом?

Answer 1

"Это зависит".

Я бы начал только с основных кандидатов: LZMA ("7-zip"), deflate (direct, zlib:deflate + маленькая обертка, gzip: deflate + немного большая обертка, zip: deflate + еще большая обертка), bzip2 (я сомневаюсь, что это было бы очень хорошо, лучше всего работает с относительно большим окном), возможно, даже одна из других ветвей LZ *как LZS, у которого есть RFC для сжатия полезной нагрузки IP , но ...

... выполнить некоторый анализ на основе фактических данных и сжатия / пропускной способности используя несколько разных подходов.Java имеет как GZIPOutputStream ("deflate in gzip wrapper"), так и DeflaterOutputStream ("plain deflate", рекомендуется использовать gzip или zip "wrappers"), и существует LZMA Javaреализации (нужен только компрессор, а не контейнер), поэтому все они должны быть тривиальны для макета.

Если есть регулярность между пакетами, то возможно, что это можно использовать - например, кэш сборкисопоставления, таблицы Хаффмана или просто изменение «окон» одного из других алгоритмов, но, вероятно, необходимо учитывать потери пакетов и «сжимаемость».Спуск по этому маршруту, хотя добавляет гораздо больше сложности .Дополнительные идеи по оказанию помощи компрессору можно найти в SO: Как найти хороший / оптимальный словарь для zlib 'setDictionary' при обработке заданного набора данных? .

Также протоколвероятно, должно иметь место простое «отступление» от нулевого сжатия, потому что некоторые [особенно небольшие случайные] данные могут быть практически не сжимаемыми или могут «сжимать» до большего размера (zlib на самом деле имеет эту защиту, но такжеимеет «накладные расходы на обертку», так что было бы лучше кодировать отдельно для очень маленьких данных).Издержки «обертки» для сжатых данных, таких как gzip или zip, также необходимо учитывать при таких небольших размерах.Это особенно важно учитывать для строковых данных длиной менее ~ 100 символов.

Счастливое кодирование.

---

Еще одна вещь, которую следует учитывать, - это кодировка, используемая для помещения символов в выходной поток.Сначала я бы начал с UTF-8, но это не всегда может быть идеально.

---

См. SO: Лучший алгоритм сжатия для коротких текстовых строк , который предлагает SMAZ , но я не знаю, как этот алгоритм перейдет в Unicode / двоичный файл.

---

Также учтите, что не все реализации deflate (или другого формата) созданы равными.Я не знаком со стандартным дефлятом Java по сравнению с третьей стороной (скажем, JZlib ) с точки зрения эффективности для небольших данных, но рассмотрим Сжатие небольших полезных нагрузок [.NET] , которое показывает довольно негативноцифры для формата "одинаковое сжатие".Статья также приятно заканчивается:

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

Мой окончательный вывод: всегда проверяйте с использованием реальных данных и измеряйте преимущества, иначе в итоге вас может немного удивить!

Удачного кодирования.На этот раз по-настоящему.

Answer 2

Большинство стандартных алгоритмов сжатия не очень хорошо работают с небольшими объемами данных. Часто есть заголовок и контрольная сумма, и для разогрева сжатия требуется время. То есть он строит словарь данных на основе данных, которые он видел.

По этой причине вы можете найти, что

• маленькие пакеты могут быть меньше или иметь одинаковый размер без сжатия.
• простое сжатие, специфичное для приложения / протокола, лучше
• Вы должны предоставить предварительно скомпилированный словарь данных для алгоритма сжатия и максимально удалить заголовки.

Обычно я выбираю второй вариант для небольших пакетов данных.

Answer 3

Самое простое, что можно сделать, - это наложить слой GZIPOutputStream поверх ByteArrayOutputStream, так как он встроен в JDK, используя

ByteArrayOutputStream baos = new ByteArrayOutputStream();
GZIPOutputStream zos = new GZIPOutputStream(baos);

zos.write(someText.getBytes());
zos.finish();
zos.flush();


byte[] udpBuffer = baos.toByteArray();

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

Answer 4

Хороший алгоритм сжатия для коротких строк / URL - это реализация lzw, он в java и может быть легко перенесен для клиента gwt: https://code.google.com/p/lzwj/source/browse/src/main/java/by/dev/madhead/lzwj/compress/LZW.java

некоторые замечания

• используйте длину 9-битового кодового слова для небольших строк (хотя вы можете попробовать, что лучше). исходное соотношение составляет от 1 (очень маленькие строки, сжатые не больше исходной строки) до 0,5 (большие строки)
• в случае клиентского gwt для других длин кодового слова было необходимо настроить обработку ввода / вывода для работы на основе байтов, чтобы избежать ошибок при буферизации битовой последовательности в long, которая эмулируется для js.

Я использую его для комплексного кодирования параметров URL-адресов в клиентском gwt вместе с кодировкой base64 и автоматической сериализацией в json.

upd: реализация base64 здесь: http://www.source -code.biz / base64coder / java Вы должны изменить его, чтобы сделать URL-адрес безопасным, то есть изменить следующие символы:

'+' -> '-' '/' -> '~' '=' -> '_'