Оптимальное представление изменения двоичных данных C++
На сервере хранится строка размером, приблизительно равным двадцати килобайтам. Это строка регулярно заменяется на похожую, изменения могут быть:
- добавить небольшой фрагмент, при необходимости сдвинув вправо, все, что правее
- удалить небольшой фрагмент, при необходимости сдвинув влево, все, что левее
- заменить данные в небольшом фрагменте на другие
и всевозможные их сочетания. Под небольшим фрагментов подразумевается, как правило, не более пятидесяти байт.
Серверу необходимо после каждого обновления этой строки обеспечить всех добросовестных клиентов последней ее версией. Так как изменения небольшие относительно размера строки и происходят часто, отправлять полностью строку слишком расточительно с точки зрения потребляемого трафика. Соединение гарантирует, что все пакеты будут доставлены без повреждений, потерь, дубликатов, в том же порядке.
Я подумал, что проблему можно решить следующим образом. Сервер, помимо текущего состояния строки, будет хранить то состояние строки, которое должно находится у клиентов по приходу последнего отправленного им пакета. В таком случае будет достаточно не заново отправлять все двадцать килобайт, а только специальным образом закодированное изменение. Какие алгоритмы или реализации можно посмотреть на тему генерации этого специальным образом закодированного изменения по старой и новой версии двоичных данных?
Ответы (1 шт):
Вам нужен вариант расстояния Левенштейна, расстояния Дамерау — Левенштейна. Вычислите его для пары (строка на клиенте, строка на сервере). Во время вычисления сохраните последовательность операций, которая переводит строку клиента в строку сервера. Отправьте клиенту последовательность. Клиент применит её к своей строке и получит строку идентичную серверной.