Приложение "A" регулярно запрашивает у приложения "B" некоторый набор байт, отражающий состояние приложения "B" (условно время на часах, температура процессора, наличие свободного места на жестком диске и т.д.). Ответ имеет фиксированную длину и формат (парсится приведением указателя на полученный набор байт к структуре, что не важно).
В целях экономии трафика между приложениями (допустим, связь между ними построена посредством сокетов, а сами приложения находятся на разных материках) хотелось бы возвращать от приложения "B" не целиком состояние, а только изменившуюся часть (предполагается, что таких изменений обычно немного).
В общем нужен алгоритм, сравнивающий разницу между прошлым и настоящим значениями набора байт и генерирующий последовательность байт на этой основе, по которой принимающая сторона однозначно восстановит настоящее значение.

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

ну тык передавай маркер+{"смещение в структуре,новое значение"} пары. Где маркер описывает: либо мы пеердаем всю инфу, либо части (например можно в нем же передавать id прошлого состояния а на сервере запоминать не одно предыдущее состояние, а например 100 их). Ну а сравнение, это фигня уже (по байтам черт возьми)). Только я сомневаюсь что это даст такую уж огромную экономию трафика.

Сохраняй ранее отправленный массив. А при отправке следующего, сравнивай, сравнивай, извлекай разницу, отправляй.

Это сообщение отредактировал(а) andrew_121 - 14.6.2009, 12:42

А примерный объём данных можно озвучить? 

если по протоколу UDP данные будут передаваться - необходимо будет удостовериться в их корректности. т.е. использовать бит чётности или ещё какой-то механизм.

andrew_121, 

Собственно в каком минимальном виде передать эту разницу и стоит вопрос.
Если

то, кажется, будет передаваться избыточная информация.


W4FhLF, 

Около 200 байт. В общем случае для универсальности пытаюсь не обращать на это внимание.

zim22, 

Пока предусмотрена контрольная сумма по модулю 2, возможно, кончено, имеет смысл crc32 или другой более достоверный метод.

Сейчас применяю следующую схему ( некий упрощенный гибрид дельта кодирования и RLE компрессии ).
1. На отправляющей стороне генерирую новый массив - побайтовую разницу между предыдущим значением (изначально это нули) и текущим.
2. Полученный массив имеет большое кол-во нулевых значений, так как многие исходные данные не изменились.
3. Теперь кодируем полученный массив с помощью последовательностей - <1 байт длины>< n-кол-во исходных байт >, <1 байт кол-во пробелов-нулей>, опять <1 байт длины>< n-кол-во исходных байт > и <1 байт кол-во пробелов-нулей>. Т.е. области со значением 0 заменяются байтом, обозначающим их количество.
4. На принимаемой стороне этих данных достаточно для восстановления исходного значения массива.
Получение разницы и сжатие заменой нулевых последовательностей может быть произведено циклом в один проход.




Это сообщение отредактировал(а) semibug - 14.6.2009, 13:42

а нужно ли его регулярно опрашивать? пусть приложение B само сообщает при изменении своих показателей

Либо я не понял, либо здесь действительно могут возникать неопределённости. 

Как определить, с чего начинается последовательность, с <1 байт кол-во пробелов-нулей> или <1 байт длины>? Насколько я понял может начинаться и с того и с другого? 

Я предлагаю передавать так: id:data, где id - идентификатор параметра, data - данные параметра. Ессно передавать только изменившиеся параметры. 

id = 1 байт (т.е. до 256 параметров)
data = n, где n - объём данных того типа, которому соответствует id

Такая схема избыточна, если количество изменяющихся параметров примерно равно количеству параметров в целом. 

W4FhLF, 

Начинается (хотя можно и наоборот) с последовательности байт, чередуется с нулевыми последовательностями. соответственно если нужно пропустить в самом начале последовательность значимых байт (и не только) ставим нулевую длину.



Согласен, то же неплохой вариант, но он привязан к формату данных (к размеру параметров), т.е. их изменении придется корректировать код, определяющий адреса и размеры параметров.

zim22, 

Ну в общем то большого значения не имеет, пусть даже приложение "B" само сообщает изменения без лишних запросов, все равно задача сократить объем этих данных. (здесь экономия только на запросе, который может иметь минимальную длину.

Это сообщение отредактировал(а) semibug - 14.6.2009, 14:54

Ну в твоём случае типы и их размеры тоже должны быть известны приложениям "А" и "B", но ты к тому же их ещё и передаёшь. В моём случае поток данных выглядит следующим образом:

n id2:data_1 id5:data_2 ... id8:data_n

Причём порядок следования параметров неважен. А в твоём случае, я так понял, он "зашит" намертво в протокол. Адреса, размер... Тут тоже достаточно знать id, всё остальное становится известно. 

Это сообщение отредактировал(а) W4FhLF - 14.6.2009, 15:12

W4FhLF, 

Через общий заголовочный файл в виде описания структуры. Что то вроде



Далее приводим адрес на буфер с принятыми данными к указателю на эту структуру и получаем через него нужные значения (не думая о адресах и размерах).
Пи необходимости добавить новое поле данных оно вписывается в эту структуру.

Теперь посмотрим как распарсить принятые по схеме

данные. Возможно ошибаюсь, но выходит, что через условия (switch), где для каждого ID параметра нужна ветка, выбирающая адрес и размер данных, для того чтобы иметь возможность их использовать. Ну как вариант задать массив и выбирать по индексу.
В этому случае при изменении кол-ва и размеров передаваемых параметров имеем большое поле для совершения ошибок. В отличии от алгоритма не привязанного к формату исходных  данных.


Сомнительная польза.


Это сообщение отредактировал(а) semibug - 14.6.2009, 15:41

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



Если на С пишите, то не ошибаетесь в прицнипе) 

В целом я согласен, мой вариант менее гибок и масштабируем. Он он более экономичен. 

W4FhLF, 

В моем случае операции происходит сразу над всей структурой линейно, без разделения на параметры. Это позволяет менять набор данных не меняя алгоритма. В вашем случае чтобы распарсить поток нужно как минимум знать размеры параметров. Иначе как определить сколько байт за идентификатором соответствуют данным. С другой стороны, конечно, если размер передаваемой информации имеет критическое значение в вашем случае (при условии минимальных изменений в данных) алгоритм предпочтительнее.



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


Это сообщение отредактировал(а) semibug - 14.6.2009, 16:19

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

200 байт, оптимизация обмена  .  Уважаемый автор, вы будите оптимизировать то, что и так передастся одним пакетом (можно передавать до ~1,5КБ). Вы все равно, не больше не меньше, передадите этот пакет, хоть с оптимизацией, хоть без нее. Выигрыш в трафике на таком объеме информации с передачей разницы в данных будет слишком малым для того, чтобы задумываться над этим.

ЗЫ Также, нельзя говорить о 200 байтах без упоминания частоты отправки, т.е. трафика данных, необходимого для работы приложения. В случае датчиков, например, температуры, в большенстве случаев нет смысла передавать даные очень часто, а в масштабах сети интернет (про разные материки) и вовсе не имеет смысла т.к. скорость передачи будет непредсказуема (соответственно и задержки тоже). Т.е. в данном случае ответ однозначен.