В продолжение хранения таблиц в виде патчей

Автор: IID
Дата: 08.08.22

Раздумываю как эти патчи правильнее генерить.

Задача:
Есть множество из N снапшотов.
Каждый снапшот — набор уникальных tuple, состоящих из двух (или трёх) 32битных целых чисел.
Количество tuple'ов внутри снапшота 100-200 тысяч.

В "естественной среде обитания" снапшоты получаются друг из друга, путём внесения изменений. Какие-то числа убираются, какие-то добавляются.
Изменения нелинейные, и представляют собой дерево. Можно даже попытаться восстановить это дерево (но лучше не надо, это непросто, и даже не всегда возможно).
Назовём набор изменений между снапшотами "патчем". Каждый патч состоит из набора tuple'ов для удаления, и для добавления.

Требуется "сжать" эти полновесные снапшоты, в форму (ссылка на базовый снапшот + патч).
Понятно, что взяв в качестве ключевого один снапшот, и представив остальные в виде патчей, мы можем получить результат, далёкий от оптимального.
Данный результат мог быть лучше, если сделать патчи рекурсивными (ни в коем случае!). Если периодически добавлять полный снапшот в качестве доп. базы, и создавать патчи уже от него.

Пока придумалось только решение "в лоб", полным перебором, представляя снапшоты в виде отсортированных множеств для сравнения между собой за линейное время.
1) Сначала в качестве базовго берём один снапшот, на позиции P0 ∈ [0..(N-1)]. Считаем размеры получившихся патчей. Выбираем лучшее положение.
2) Затем в качестве базововых берём два снапшлота. Второй, соотв. на позиции P1 ∈ [(P0+2)..(N-1)] (+2 потому что подряд идущие снапшоты смысла не имеют).
Также берём точку отсечения, S01, между P0 и P1, начиная с которой роль базы переходит от P0 к P1.
3) ... три снапшота...
...
5) стоп-шаг, т.к. выглядит малоперспективным, с учётом асимптотики и количества элементов.

Есть ли более оптимальный способ ?
Может быть можно сосчитать какие-то хитрые граничные условия, позволяющие избежать полного перебора ?