Теория, как сократить объём трафика по сети, Что-то вроде дельта кодирования.. Опции

[512es]

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

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

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

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

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

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

[512es]

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

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

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

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

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

Сообщение отредактировал 512es - 17.1.2012, 20:50

[BRE]

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

[512es]

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

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

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

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

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 специальных методов чтобы сделать это проще? Не прибегая к перебору байт...

Сообщение отредактировал 512es - 17.1.2012, 22:10

[512es]

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

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

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

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

[Iron Bug]

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

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

Сообщение отредактировал Iron Bug - 17.1.2012, 23:33

[512es]

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


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

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

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

Сообщение отредактировал 512es - 18.1.2012, 0:14

Прикрепленные файлы

 bsdiff.zip ( 5,88 килобайт ) Кол-во скачиваний: 0

 

[Алексей1153]

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

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

Сообщение отредактировал Алексей1153 - 18.1.2012, 7:33

[512es]

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

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

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

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

[Iron Bug]

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

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

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

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