Доброго времени суток!
Упрошённая схема:
Имеется 2 компьютера, клиент и сервер.
Клиент достаточно часто запрашивает одни и те же данные (QByteArray) у сервера.
Объём данных будем считать относительно большим.
Иногда данные могут незначительно меняться.
Задача:
Максимально сократить объём трафика между клиентом и сервером.
Возможно запоминание последних отданных данных клиенту на стороне сервера и последних принятых данных клиентом на стороне клиента.
Сейчас используется qCompress. Заметный выигрыш в размере пакетов, но всё равно, теоретически, можно посылать только различия между новым и предыдущим QByteArray + хеш, указывающий на то, какие данные были использованы при сравнении (на всякий случай, для коррекции ошибок).
Смотрю в сторону Delta кодирования. Но помоему это немного не то, или я просто не умею его использовать. Как его адаптировать для сравнения двух массивов данных?
Ковыряю пример с http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D1%8C%D1%82%D0%B0-%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 по дельта-кодированию.
Что-то забывать я стал чистый C... Вообще не пойму, как получается 127+10 программа выдаёт -119:
char aa = 127;
char bb = 10;
aa += bb;
qDebug() << (int) aa;
Вот это почитай: http://ru.wikipedia.org/wiki/Целое_(тип_данных)
Эм, спс, почитал...
Правда всё равно не понял как применить эти знания к конкретному случаю..
Я просто лишь хочу убедиться что данным примером можно складывать любые массивы данных, и это не вызовет переполнения буфера.
Насколько я понял из опытов:
qDebug() << (int)(char) 0xff + 0x02;
qDebug() << (int) (char) 257;
void delta_encode(char *bp, size_t n)
{
char last = 0, tmp;
int i;
for (i = 0; i < n; ++i) {
tmp = bp[i];
bp[i] -= last;
last = tmp;
}
}
Тыкс.. Отвечаю сам себе.
В задуманном мною аглоритме есть один огромный недостаток. Если к одному из сравниваемых массивов добавить в середину (а ещё лучше в начало) хоть один байт, то при проверке данные съедут и получим практически несжимаемый файл.
Однако есть всётаки умные люди которые уже всё придумали до нас!
http://www.daemonology.net/bsdiff/ тут даже докторскую диссертацию можно почитать на эту тему!
И именно bsdiff использовался системой обновления Google Chrome, пока они не придумали свой алгоритм. Но новый гугловский алгоритм только для выполняемых файлов, т.к. дизасемблирует код а потом заново ассемблирует.
Iron Bug, http://dev.chromium.org/developers/design-documents/software-updates-courgette
А вообще, по теме:
Может кто смог бы написать обёртку над bsdiff для Qt?)
Вроде кода совсем немного, но для меня так запутано...
А главное, там пишут в файл через BZ2_bzWriteOpen, BZ2_bzWrite тоесть через библиотеку BZip2, сразу архивируя. А мне надо в QByteArray сохранить, можно уже запакованные данные...
Для Ruby например, уже есть https://github.com/taf2/rb-bsdiff
Для питона есть даже http://starship.python.net/crew/atuining/cx_bsdiff/index.html
незначительное изменение данных влияет на размер данных, или же размер постоянный ? Если размер постоянный, то можно тупо вычитать новый и старый вариант. В разности будет куча нулевых байтов, что любой алгоритм сжатия очень хорошо сожмёт. Кроме того, цепь нулей в начале и в конце можно отбросить, передав лишь их количество
Опробовано лично на передаче изображения на экране на удалённый комп
Размер динамический. Вообщем утилита bsdiff просто гениальна! Она находит повторяющиеся блоки данных рекурсивным алгоритмом. Потом жмёт патч файл через библиотеку BZip2. Жаль только много памяти кушает.
Данные можно подавать абсолютно любые и разных размеров.
В качестве проверки утилиты я дал ей 2 файла базы sqlite. Одна размером 3.3мб, вторая 4.1. Это был оригинал и один из бекапов.
На выходе получил патч файл размером 40к!!
Теперь, имея в наличии лишь этот патч файл и бекап, можно запросто получить исходный файл.
Iron Bug, и в GIF похоже делается.
512es, алгоритм то, может, и хороший, а вот как насчёт скорости работы ? При передаче экрана скорость была критична - задержек и так куча: сжатие, передача, распаковка.
Быть может немного не в тему, но может не стоит изобретать велосипед и просто попробовать данные упаковать? Например тем-же самым http://doc.crossplatform.ru/qt/4.6.x/qbytearray.html#qCompress
Быть может немного не в тему, но может не стоит изобретать велосипед и просто попробовать данные упаковать? Например тем-же самым http://doc.crossplatform.ru/qt/4.6.x/qbytearray.html#qCompress ? А если уж в упор хочется diff иметь, то может стоит посмотреть в сторону http://code.google.com/p/google-diff-match-patch
PS: господа модераторы, грохните мое предыдущее сообщение, если не трудно. накосячил с разметкой
zloiia, всё зависит от критичности времени обработки. Если ему скорость неважна, но важен траф - пусть изголяется )) Архиватор будет пошустрее, но траф вырастет. А в случае с постоянным объёмом (видеокадры) - лучшее решение - именно разность
Алексей1153, скорость да, уступает простому вычитанию, зато в трафике выигрыш реальный.
Кстати, ещё по поводу передачи экрана. Представьте ситуацию когда окно двигают по однородному фону рабочего стола. Если использовать простое вычитание, то трафик будет достаточно большой, так как надо перерисовывать всю затронутую область экрана. А если использовать умные алгоритмы то окно не придётся постояно передавать. Этот блок данных как был неизменным, так и останется. Просто он будет подвинут вслед за окном.
Скорость создания патча bsdiff-ом на моих опытах составляет около 1.5 секунды, а скорость применения патча всего 0.02 секунды. В реалтайм программах ксожалению врядли получится использовать.
У bsdiff-а больше область использования в заранее подготавливаемых данных. Например кодирование фильмов, бекапы, обновлялки.
zloiia,
google-diff-match-patch это для текстовых данных. А тут речь идёт о бинарных.
А про qCompress сказано ещё в первом посте. Так и используется сейчас. Просто разница в том что, например, передавать 580кб (архив) данных или 40кб (дельта-патч)? Если цифры кажутся не внушительными, помножте оба значения на 10, на 100, на 1000...
Алексей1153, кстати, а что вас заставило изобретать велосипед? Ведь есть же VLC, где используются эффективные и быстрые алгоритмы сжатия. Работает даже при совсем плохом инете и имеет кучу настроек.
512es, задача была - написать систему удалённого администрирования (простенькую, но достаточную) , не использующую левого кода. Там даже парочка недоделок осталась, когда-нибудь на досуге доведу до ума )) А заказчик уже был доволен. Жалею только, что маловато запросил по цене - но потом переобуваться было уже несолидно. Да и перерыв в три недели был в середине проекта - я переезжал в новую квартиру в тот момент - зак очень нервничал
http://www.free-lance.ru/users/alex1153/viewproj.php?prjid=2826191
http://fabiensanglard.net/quake3/network.php
Вообще все ревью достаточно интересные.
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)