Алгоритм двоичных различий для небольших двоичных объектов

Question

Существует много информации о бинарных разностных алгоритмах для довольно больших файлов (1MB+). Тем не менее, мой вариант использования отличается. Вот почему это не дубликат.

У меня есть коллекция многих объектов, каждый в диапазоне 5-100 байт. Я хочу отправлять обновления по этим объектам по сети. Я хочу скомпилировать обновления в отдельные пакеты TCP (с приемлемым MTU ~1400). Я хочу попытаться установить как можно больше обновлений в каждом пакете: сначала добавьте их идентификаторы, а затем объедините двоичные различия всех двоичных объектов.

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

Answer 1

С такими маленькими объектами вы можете использовать классический алгоритм Longest-Common-Subsequence, чтобы создать 'diff'.

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

Ваша цель на самом деле использовать пример исходных объектов для сжатия новых объектов, и вы должны думать об этом в этих терминах.

Есть много, много способов, но вы, вероятно, имеете некоторое представление о том, как вы хотите кодировать эти новые объекты. Вероятно, вы думаете о замене разделов новых объектов ссылками на разделы исходных объектов.

В этом случае было бы целесообразно создать массив суффиксов для каждого исходного объекта ( https://en.wikipedia.org/wiki/Suffix_array). Затем, когда вы кодируете соответствующий новый объект, в каждом байте вы можете использовать массив суффиксов, чтобы найти самый длинный совпадающий сегмент старого объекта. Если этого достаточно, чтобы сэкономить, вы можете заменить соответствующие байты ссылкой.

Answer 2

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

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

Это теоретически не оптимально. Однако учтите следующее:

1. Реализация проста.
2. Код проверен в бою - вашему коду потребуется много времени, чтобы достичь такого же уровня надежности.
3. Эта реализация охватывает крайние случаи, когда состояние принимающей стороны отличается от ожидаемого отправителем. Это может произойти, если, скажем, у получателя произошел сбой / перезапуск.

Есть случаи, когда это неправильное решение. Но я бы настаивал на том, чтобы это прямое решение не сработало, прежде чем быть умным и искушенным.