Доброго времени суток!

Упрошённая схема:
Имеется 2 компьютера, клиент и сервер.
Клиент достаточно часто запрашивает одни и те же данные (QByteArray) у сервера.
Объём данных будем считать относительно большим.
Иногда данные могут незначительно меняться.

Задача:
Максимально сократить объём трафика между клиентом и сервером.

Возможно запоминание последних отданных данных клиенту на стороне сервера и последних принятых данных клиентом на стороне клиента.

Сейчас используется qCompress. Заметный выигрыш в размере пакетов, но всё равно, теоретически, можно посылать только различия между новым и предыдущим QByteArray + хеш, указывающий на то, какие данные были использованы при сравнении (на всякий случай, для коррекции ошибок).

Смотрю в сторону Delta кодирования. Но помоему это немного не то, или я просто не умею его использовать. Как его адаптировать для сравнения двух массивов данных?

Ковыряю пример с википедии по дельта-кодированию.

Что-то забывать я стал чистый C... Вообще не пойму, как получается 127+10 программа выдаёт -119:

char aa = 127;
char bb = 10;
aa += bb;
qDebug() << (int) aa;

Помоему должно быть переполнение буфера и вылет с ошибкой, ведь тип char может принимать значения от -127 до 127, судя по той же википедии

А ведь тут на этом свойстве весь алгоритм построен..

Вот это почитай: http://ru.wikipedia.org/wiki/Целое_(тип_данных)

Эм, спс, почитал...

Правда всё равно не понял как применить эти знания к конкретному случаю..

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

Насколько я понял из опытов:

qDebug() << (int)(char) 0xff + 0x02;

Выдаёт 1. Т.е после FF, байт как бы перезаписывается при переполнении.

qDebug() << (int) (char) 257;

Тут тоже. Число, большее максимального значения байта, спокойно конвентируется и программа выдаёт 1.



Так вот, если всё это работает. То возникает вопрос, если этот код:

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;
        }
}

Модифицировать таким способом, чтобы вместо того чтобы текущий с предыдущим символом в одном массиве вычитать.
Он бы сравнивал 2 массива и разность (delta) записывал в третий.

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



Так вот.. Почему нигде об этом в инете не написано?? Вроде идея простая... Вместо этого есть достаточно сложные программы типа xdelda, diff...


И ещё вопрос, разве нету в C++ или Qt специальных методов чтобы сделать это проще? Не прибегая к перебору байт...

Тыкс.. Отвечаю сам себе.

В задуманном мною аглоритме есть один огромный недостаток. Если к одному из сравниваемых массивов добавить в середину (а ещё лучше в начало) хоть один байт, то при проверке данные съедут и получим практически несжимаемый файл.

Однако есть всётаки умные люди которые уже всё придумали до нас!
http://www.daemonology.net/bsdiff/ тут даже докторскую диссертацию можно почитать на эту тему!

И именно bsdiff использовался системой обновления Google Chrome, пока они не придумали свой алгоритм. Но новый гугловский алгоритм только для выполняемых файлов, т.к. дизасемблирует код а потом заново ассемблирует.

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

Iron Bug, Но сделали же!


А вообще, по теме:
Может кто смог бы написать обёртку над bsdiff для Qt?)

Вроде кода совсем немного, но для меня так запутано...
А главное, там пишут в файл через BZ2_bzWriteOpen, BZ2_bzWrite тоесть через библиотеку BZip2, сразу архивируя. А мне надо в QByteArray сохранить, можно уже запакованные данные...

Для Ruby например, уже есть обёртка
Для питона есть даже модуль

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

Опробовано лично на передаче изображения на экране на удалённый комп

Размер динамический. Вообщем утилита bsdiff просто гениальна! Она находит повторяющиеся блоки данных рекурсивным алгоритмом. Потом жмёт патч файл через библиотеку BZip2. Жаль только много памяти кушает.
Данные можно подавать абсолютно любые и разных размеров.

В качестве проверки утилиты я дал ей 2 файла базы sqlite. Одна размером 3.3мб, вторая 4.1. Это был оригинал и один из бекапов.

На выходе получил патч файл размером 40к!!

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

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


дык, аналогичные алгоритмы работают в пожатии разных mpеg'ов, например. там есть ключевой кадр и потом несколько "кадров" с изменениями. потом снова ключевой и серия изменений. и так далее. есть разные варианты выбора ключевых кадров и от этого зависит степень пожатия.

Iron Bug, и в GIF похоже делается.

512es, алгоритм то, может, и хороший, а вот как насчёт скорости работы ? При передаче экрана скорость была критична - задержек и так куча: сжатие, передача, распаковка.

Быть может немного не в тему, но может не стоит изобретать велосипед и просто попробовать данные упаковать? Например тем-же самым QByteArray::qCompress[\url] ? А если уж в упор хочется diff иметь, то может стоит посмотреть в сторону [url=http://code.google.com/p/google-diff-match-patch/]google-diff-match-patch

Быть может немного не в тему, но может не стоит изобретать велосипед и просто попробовать данные упаковать? Например тем-же самым QByteArray::qCompress ? А если уж в упор хочется diff иметь, то может стоит посмотреть в сторону google-diff-match-patch
PS: господа модераторы, грохните мое предыдущее сообщение, если не трудно. накосячил с разметкой

zloiia, всё зависит от критичности времени обработки. Если ему скорость неважна, но важен траф - пусть изголяется )) Архиватор будет пошустрее, но траф вырастет. А в случае с постоянным объёмом (видеокадры) - лучшее решение - именно разность

Алексей1153, скорость да, уступает простому вычитанию, зато в трафике выигрыш реальный.

Кстати, ещё по поводу передачи экрана. Представьте ситуацию когда окно двигают по однородному фону рабочего стола. Если использовать простое вычитание, то трафик будет достаточно большой, так как надо перерисовывать всю затронутую область экрана. А если использовать умные алгоритмы то окно не придётся постояно передавать. Этот блок данных как был неизменным, так и останется. Просто он будет подвинут вслед за окном.

Скорость создания патча bsdiff-ом на моих опытах составляет около 1.5 секунды, а скорость применения патча всего 0.02 секунды. В реалтайм программах ксожалению врядли получится использовать.
У bsdiff-а больше область использования в заранее подготавливаемых данных. Например кодирование фильмов, бекапы, обновлялки.

zloiia,
google-diff-match-patch это для текстовых данных. А тут речь идёт о бинарных.
А про qCompress сказано ещё в первом посте. Так и используется сейчас. Просто разница в том что, например, передавать 580кб (архив) данных или 40кб (дельта-патч)? Если цифры кажутся не внушительными, помножте оба значения на 10, на 100, на 1000...

тут ещё следует учесть, что для снижения трафика отключают обои, Аэро и прочую хрень. Даже если окно сдвинуто, всё равно там много одинаковых цветов друг на друга наложилось (белый фон, серый фон) , плюс искусственное ограничение глубины цвета (4 бита/пиксел - вполне нормально для техподдержки). Так что разность всё равно обычно хорошо сжимается, а редкие всплески трафа на одиночном кадре утонут в общей экономии. Ну и, опять же, рекомендуется безлимит для таких вещей


ага, потом прибавим 1 секунду передачи по тырнету... Слайдшоу обеспечено. Ещё учти запыхавшийся процессор

Алексей1153, кстати, а что вас заставило изобретать велосипед? Ведь есть же VLC, где используются эффективные и быстрые алгоритмы сжатия. Работает даже при совсем плохом инете и имеет кучу настроек.

512es, задача была - написать систему удалённого администрирования (простенькую, но достаточную) , не использующую левого кода. Там даже парочка недоделок осталась, когда-нибудь на досуге доведу до ума )) А заказчик уже был доволен. Жалею только, что маловато запросил по цене - но потом переобуваться было уже несолидно. Да и перерыв в три недели был в середине проекта - я переезжал в новую квартиру в тот момент - зак очень нервничал
http://www.free-lance.ru/users/alex1153/vi...p?prjid=2826191

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


VLC не опенсорц, и для многих систем он платный. а старый не будет работать под новой 64-битной семёркой, например (проверено на практике).

не у всех 8-яйцевые монстры с 4 гигами на борту Не забывай.

любой комп при общении с памятью шустрее периферии. даже x86-е. это аппаратная фича: не может шина пропускать поток с девайсов быстрее, чем обращения от проца к памяти. а уж всякие там TCP-стеки и подавно тормозные, а есть ещё сеть, которая даёт сбои и прочее, и прочее.

http://fabiensanglard.net/quake3/network.php

Вообще все ревью достаточно интересные.