Какова лучшая библиотека сжатия для очень небольших объемов данных (3-4 кибибита?)
Я работаю над игровым механизмом, который свободно происходит от Quake 2, добавляя некоторые вещи как эффекты в виде сценария (позволяющий сервер указать специальные эффекты подробно клиенту, вместо того, чтобы иметь только ограниченное количество hardcoded эффектов, к которым клиент способен.) Это - компромисс эффективности использования сети для гибкости.
Я поразил интересный барьер. Посмотрите, максимальный размер пакета составляет 2 800 байтов, и только один может выйти на клиент на кадр.
Вот сценарий, чтобы сделать эффект "искр" (могло быть хорошо для искр влияния маркера, поражений электрическим током, и т.д.), http://pastebin.com/m7acdf519 (Если Вы не понимаете это, не потейте он; это - пользовательский синтаксис, который я сделал и не относящийся к вопросу, который я задаю.)
Я сделал все возможное для уменьшения размера того сценария. Я даже уменьшил имена переменной до одних букв. Но результат - точно 405 байтов. Значение Вас может соответствовать самое большее 6 из них на кадр. Я также имею в виду несколько изменений серверной стороны, которые могли побрить его вниз еще 12 и изменение протокола, которое могло бы сохранить еще 6. Хотя сбережения варьировались бы, в зависимости от какого сценария Вы работаете с.
Однако тех 387 байтов, я оцениваю, что только 41 были бы уникальны между несколькими использованиями эффекта. Другими словами, это - главный кандидат на сжатие.
Это именно так происходит, что R1Q2 (обратно совместимый механизм Quake 2 с протоколом расширенной сети) имеет код сжатия Zlib. Я мог снять этот код или по крайней мере следовать за ним тесно как за ссылкой.
Но Zlib является обязательно лучшим выбором здесь? Я могу думать о по крайней мере одной альтернативе, LZMA, и могло легко быть больше.
Требования:
- Должно быть очень быстрым (должны были поразить очень маленькую производительность, если работается 100 раз в секунду.)
- Должен переполнить как можно больше данных в 2 800 байтов
- Маленькое место метаданных
- Совместимый GPL
Zlib выглядит хорошим, но является там чем-нибудь лучше? Следует иметь в виду, ни один из этого кода еще не объединяется, таким образом, существует много комнаты для экспериментирования.
Спасибо, - Макс
Править: Благодаря тем, кто предложил компилировать сценарии в байт-код. Я должен был ясно дать понять это - да, я делаю это. Если Вам нравитесь Вы, может просмотреть соответствующий исходный код на моем веб-сайте, хотя это все еще не "prettied".
Это - серверный код:
Компонент Lua: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/lua/scriptedfx.lua
C компонент: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/game/g_scriptedfx.c
Для определенного сценария в качестве примера я отправил, это снижает 1 172-байтовый источник к 405 байтам - все еще не достаточно маленький. (Следует иметь в виду, что я хочу соответствовать как можно большему количеству из них в 2 800 байтов!)
EDIT2: нет никакой гарантии, что любой данный пакет прибудет. Каждый пакет, как предполагается, содержит "состояние мира", не полагаясь на информацию связался в предыдущих пакетах. Обычно эти сценарии будут использоваться для передачи "услады для глаз". Если нет никакой комнаты для одной, это отбрасывается от пакета, и это не грандиозное предприятие. Но если слишком многие отбрасываются, вещи начинают выглядеть странными визуально, и это - нежелательный.
6 ответов
Окончательное обновление: Эти две библиотеки выглядят примерно одинаково. Zlib обеспечивает примерно на 20% лучшее сжатие, а скорость декодирования LZO примерно в два раза выше, но падение производительности для любой из них очень мало, почти пренебрежимо мало. Это мой окончательный ответ. Спасибо за все остальные ответы и комментарии!
UPDATE: После внедрения LZO-сжатия и лишь незначительного улучшения производительности, стало ясно, что в снижении производительности виноват мой собственный код (значительно увеличилось количество сценарных эффектов, возможных на пакет, поэтому мой "интерпретатор" эффектов работает гораздо больше). Я хотел бы смиренно извиниться за то, что пытался переложить вину, и надеюсь, что нет никаких обид. Я проведу некоторое профилирование, и тогда, возможно, я смогу получить некоторые цифры, которые будут более полезны для кого-то другого.
ОРИГИНАЛЬНЫЙ ПОСТ:
ОК, я наконец-то добрался до написания кода для этого. Я начал с Zlib, вот первые из моих выводов.
Сжатие в Zlib безумно великолепно. Он надежно сокращает пакеты, скажем, 8,5 киб до, скажем, 750 байт или меньше, даже при сжатии с Z_BEST_SPEED (вместо Z_DEFAULT_COMPRESSION.) Время сжатия также довольно хорошее.
Однако я даже не представлял, что скорость распаковки чего-либо может быть настолько плохой. У меня нет точных цифр, но, должно быть, это занимает 1/8 секунды на пакет, по крайней мере! (Core2Duo T550 @ 1.83 Ghz.) Совершенно неприемлемо.
Насколько я слышал, LZMA - это компромисс между худшей производительностью и лучшим сжатием по сравнению с Zlib. Поскольку сжатие Zlib уже чрезмерно, а его производительность уже невероятно плоха, LZMA пока не рассматривается.
Если время распаковки LZO будет таким же хорошим, как заявлено, то я буду использовать именно его. Я думаю, что в конце концов сервер все же сможет посылать Zlib-пакеты в крайних случаях, но клиенты могут быть настроены на их игнорирование, и это будет использоваться по умолчанию.
Как насчет отправки двоичного представления вашего скрипта?
Итак, я думаю о строки абстрактного синтаксического дерева с каждой процедурой, имеющей идентификатор.
Это означает повышение производительности клиентов за счет однократного синтаксического анализа и уменьшение размера за счет удаления имен методов.
zlib может быть хорошим кандидатом - лицензия очень хорошая, работает быстро, и ее авторы говорят у него очень мало накладных расходов, а накладные расходы - это то, что проблематично для небольших объемов данных.
Я был бы склонен использовать самый старший бит каждого символа, который в настоящее время тратится впустую, сдвигая группы по 9 байтов влево, вы уместитесь в 8 байтов.
Вы можете пойти дальше и отобразить символы в небольшом пространстве - можно ли уменьшить их до 6 бит (т.е. иметь только 64 действительных символа), например, не разрешая заглавные буквы и вычитая 0x20 из каждого символа (чтобы пробел становится значением 0)
Вы можете пойти дальше, сопоставив частоту каждого символа и сделав сжатие типа Хаффмана, чтобы уменьшить бит среднего числа каждого символа.
Я подозреваю, что не существует алгоритмов, которые лучше сохраняли бы данные, чем в общем случае, поскольку, по сути, нет избыточности в сообщении после изменений, которые вы уже сделали.
вам стоит посмотреть на OpenTNL и адаптировать некоторые из техник, которые они там используют, например, концепцию сетевых строк