crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

3 страниц V   1 2 3 >  
Ответить в данную темуНачать новую тему
> Теория, как сократить объём трафика по сети, Что-то вроде дельта кодирования..
512es
  опции профиля:
сообщение 17.1.2012, 18:28
Сообщение #1


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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

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

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

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

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

Смотрю в сторону Delta кодирования. Но помоему это немного не то, или я просто не умею его использовать. Как его адаптировать для сравнения двух массивов данных?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
512es
  опции профиля:
сообщение 17.1.2012, 20:49
Сообщение #2


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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

Что-то забывать я стал чистый 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
  опции профиля:
сообщение 17.1.2012, 21:25
Сообщение #3


Профессионал
*****

Группа: Участник
Сообщений: 1112
Регистрация: 6.3.2009
Из: Ростов-на-Дону
Пользователь №: 591

Спасибо сказали: 264 раз(а)




Репутация:   44  


Вот это почитай: http://ru.wikipedia.org/wiki/Целое_(тип_данных)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
512es
  опции профиля:
сообщение 17.1.2012, 22:09
Сообщение #4


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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

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

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

Насколько я понял из опытов:
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
  опции профиля:
сообщение 17.1.2012, 22:56
Сообщение #5


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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

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

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

И именно bsdiff использовался системой обновления Google Chrome, пока они не придумали свой алгоритм. Но новый гугловский алгоритм только для выполняемых файлов, т.к. дизасемблирует код а потом заново ассемблирует.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 17.1.2012, 23:32
Сообщение #6


Профессионал
*****

Группа: Модератор
Сообщений: 1611
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 219 раз(а)




Репутация:   12  


Цитата(512es @ 18.1.2012, 1:56) *
Но новый гугловский алгоритм только для выполняемых файлов, т.к. дизасемблирует код а потом заново ассемблирует.

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

Сообщение отредактировал Iron Bug - 17.1.2012, 23:33
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
512es
  опции профиля:
сообщение 17.1.2012, 23:54
Сообщение #7


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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


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

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

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

Сообщение отредактировал 512es - 18.1.2012, 0:14
Прикрепленные файлы
Прикрепленный файл  bsdiff.zip ( 5.88 килобайт ) Кол-во скачиваний: 0
 
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 18.1.2012, 7:32
Сообщение #8


фрилансер
******

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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

Сообщение отредактировал Алексей1153 - 18.1.2012, 7:33
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
512es
  опции профиля:
сообщение 18.1.2012, 17:37
Сообщение #9


Участник
**

Группа: Участник
Сообщений: 135
Регистрация: 31.10.2008
Пользователь №: 407

Спасибо сказали: 5 раз(а)




Репутация:   0  


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

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

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

Теперь, имея в наличии лишь этот патч файл и бекап, можно запросто получить исходный файл.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 18.1.2012, 17:54
Сообщение #10


Профессионал
*****

Группа: Модератор
Сообщений: 1611
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 219 раз(а)




Репутация:   12  


Цитата(512es @ 18.1.2012, 2:54) *

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

Цитата(Алексей1153 @ 18.1.2012, 10:32) *
Опробовано лично на передаче изображения на экране на удалённый комп :)

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

3 страниц V   1 2 3 >
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 28.3.2024, 21:45