Можно ли применить известный трюк с операцией XOR, используемый для поиска в списках одного или двух пропущенных чисел, сделав так, чтобы он подошёл бы для поиска тысяч отсутствующих идентификаторов в таблицах, содержащих миллионы строк?

Да — можно! А именно — это реально сделать, воспользовавшись структурой данных, называемой обратимым фильтром Блума (Invertible Bloom Filter, IBF), которая позволяет сравнивать два множества. При этом пространственная сложность алгоритма, использующего IBF, зависит только от размера различий сравниваемых множеств. Прибегнув к обобщению трюка с XOR, можно взаимоуничтожить все идентичные значения, в результате размер этой структуры данных будет зависеть только от масштабов различий множеств.

Большинство руководств по IBF начинаются с описаний стандартных фильтров Блума (Bloom Filter), которые поддерживают две операции — insert и maybeContains. Идя дальше — рассказывают о фильтрах Блума с подсчётом (Counting Bloom Filters), которые поддерживают ещё и операцию delete. И наконец — выходят на обратимые фильтры Блума, поддерживающие операцию get, возвращающую точные данные, и операцию listing, дающую вероятностный результат. В этой статье я применю иной подход, придя к IBF через трюк с XOR.

Обратимые фильтры Блума всё ещё недостаточно широко известны в сообществе программистов, а трюк с XOR, благодаря LeetCode, стал весьма популярным. Цель, которую я хочу достигнуть благодаря этой статье, заключается в том, чтобы построить связь между трюком с XOR и IBF, повысив таким образом количество разработчиков, которые умеют работать с этой замечательной и мощной структурой данных.

Поиск трёх отсутствующих чисел

Начнём с конкретного примера:

A = [1,2,3,4,5,6,7,8,9,10]
B = [1,2,4,5,7,8,10]

В множестве B нет трёх чисел: {3, 6, 9}.

Классический трюк с XOR хорошо подходит для поиска одного или двух отсутствующих значений, а что если их три или больше? Если мы не знаем о том, сколько чисел отсутствует — можно использовать поле count (количество элементов) для выявления ситуаций, в которых обычный трюк с XOR не сработает:

XOR(A) = 1 ^ 2 ^ ... ^ 10 = 11
COUNT(A) = 10
COUNT(B) = 7

Так как в B имеется 7 элементов, а в A — 10, мы знаем о том, что количество отсутствующих чисел — 3, что слишком много для стандартного трюка с XOR.

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

// Хеш-функция помещает каждое из чисел в некий раздел
H(1) = 2, H(2) = 1, H(3) = 1, H(4) = 0, H(5) = 0
H(6) = 0, H(7) = 2, H(8) = 1, H(9) = 2, H(10) = 1

// Множества, распределённые по разделам
A_0 = [4,5,6]     B_0 = [4,5]
A_1 = [2,3,8,10]  B_1 = [2,8,10]
A_2 = [1,7,9]     B_2 = [1,7]

Теперь в каждом из разделов имеется, самое большее, 1 отсутствующий элемент, поэтому к каждому из них можно применить трюк с XOR:

XOR(B_0) ^ XOR(A_0) = (4 ^ 5) ^ (4 ^ 5 ^ 6) = 6
XOR(B_1) ^ XOR(A_1) = (2 ^ 8 ^ 10) ^ (2 ^ 3 ^ 8 ^ 10) = 3
XOR(B_2) ^ XOR(A_2) = (1 ^ 7) ^ (1 ^ 7 ^ 9) = 9

Успех! Все три пропущенных элемента — {3, 6, 9} — восстановлены.

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

Обнаружение ситуаций, когда трюк с XOR не работает

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

Обобщим задачу, перейдя от понятия «пропущенных чисел» к понятию симметрической разности. Симметрическая разность двух множеств A и B — это множество элементов, которые присутствуют либо в одном множестве, либо во втором, но не в обоих множествах сразу: (A \ B) ∪ (B \ A), часто это записывают как A Δ B.

Рассмотрим пример:

A = [1,2,3,4,6]
B = [1,2,4,5]

Симметрическая разность этих множеств — {3, 6, 5}. Элементы 3 и 6 присутствуют только в множестве A, а элемент 5 — только в B.

Примитивный подход, предусматривающий проверку вида |COUNT(A) - COUNT(B)| = 1, здесь не сработает, так как, хотя разница в количестве элементов и равняется 1, симметрическая разность множеств представлена тремя элементами. Здесь применение стандартного трюка с XOR даёт бессмысленный результат.

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

COUNT(A) = 5, XOR(A) = 2
COUNT(B) = 4, XOR(B) = 2
XOR_HASH(A) = H(1) ^ H(2) ^ H(3) ^ H(4) ^ H(6)
XOR_HASH(B) = H(1) ^ H(2) ^ H(4) ^ H(5)

XOR(B) ^ XOR(A) = 0
XOR_HASH(B) ^ XOR_HASH(A) = H(3) ^ H(5) ^ H(6) 
H(3) ^ H(5) ^ H(6) ≠ H(0) // Следовательно — результаты применения XOR ненадёжны

Теперь, хотя мы ещё и не можем получить полную симметрическую разность — мы уже способны, проверяя согласованность поведения хеш-накопителей, обнаружить ситуацию, когда результаты применения XOR окажутся ненадёжными.

Обратимые фильтры Блума

Основная идея

Трюк с XOR основан на накопителе, который хранит результат поэлементного применения операции XOR к элементам списка. Опираясь на эту идею, мы вводим следующие механизмы:

1. Разбиение наборов данных на разделы: это нужно для разделения исходных множеств на множества меньших размеров.

2. Дополнительные накопители: они хранят сведения о количестве элементов и хеши результатов поэлементного применения операции XOR к элементам множества.

Для того чтобы полностью обобщить эту идею и перейти к надёжной структуре данных, нам нужно следующее:

1. Схема разбиения наборов данных на разделы, способная, с высокой вероятностью, формировать разделы, устроенные так, чтобы хранящиеся в них данные поддавались восстановлению.

2. Итеративный процесс, использующий восстановленные значения для разблокировки дополнительных разделов.

Это — именно то, что даёт нам IBF. В IBF используются схема хеширования, созданная в стиле фильтра Блума, применяемая для распределения элементов по множеству разделов. После этого используется графовый алгоритм, который называется «Peeling». Он итеративно и с очень высокой вероятностью успеха восстанавливает симметрическую разность разделов.

Структура

Структура данных IBF представляет собой массив ячеек, каждая из которых содержит три накопителя:

• idSum: результат поэлементного применения операции XOR к значениям элементов.

• hashSum: результат поэлементного применения операции XOR к хешам элементов.

• count: количество элементов в ячейке.

Операции

Для вычисления симметрических разностей IBF поддерживает три основных операции:

1. Encode: создание IBF на основе множества элементов.

2. Subtract: вычитание одной структуры данных из другой. Идентичные значения взаимоуничтожаются, остаётся лишь симметричная разность.

3. Decode: восстановление сохранённых значений через поиск «чистых» ячеек (count = ±1 и H(idSum) = hashSum) и итеративное применение к ним алгоритма «Peeling».

У IBF имеется один параметр — d — ожидаемый размер симметрической разности. Если правильно выбрать размер структуры (обычно — m > 1.22d ячеек), IBF с очень высокой вероятностью восстанавливает полную симметрическую разность множеств.

Пример реализации

Мне, ни на одном из языков программирования, не удалось найти надёжной, хорошо поддерживаемой библиотеки, реализующей возможности IBF (если вам о такой известно — пожалуйста дайте мне знать). Поэтому я создал базовую реализацию IBF на Python. Если хотите с ней поэкспериментировать — загляните сюда.

Вот пример её использования:

# -- Генерирование множеств  --
a = [1, 2, 4, 5, 6, 7, 9, 10]
b = [1, 3, 4, 5, 6, 7, 9, 10]
set_a = set(a)
set_b = set(b)
ibf_size = 100
k = 4

# -- Кодирование множеств в виде IBF --
ibf_a = IBF(size=ibf_size, k=k)
for item in a:
   ibf_a.insert(item)

ibf_b = IBF(size=ibf_size, k=k)
for item in b:
   ibf_b.insert(item)

# -- Вычитание IBF --
diff_ibf = ibf_a.subtract_ibf(ibf_b)

# --- Декодирование ---
success, decoded_added, decoded_removed = diff_ibf.decode()

# --- Проверка ---
assert(success)
expected_added = set_a - set_b
expected_removed = set_b - set_a

print("--- Verification ---")
print(f"Expected added (in A, not B): {len(expected_added)} items")
print(f"Decoded added:                  {len(decoded_added)} items")
assert(expected_added == decoded_added)

print(f"Expected removed (in B, not A): {len(expected_removed)} items")
print(f"Decoded removed:                  {len(decoded_removed)} items")
assert(expected_removed == decoded_removed)

О задаче сравнения и согласования множеств

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

Итоги

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

Если вы хотите глубже разобраться в этой теме — вот небольшой список публикаций, которые показались мне интересными.

• Invertible Bloom Lookup Tables, Mitzenmacher (2011)

• Simple Multi-Party Set Reconciliation, Mitzenmacher (2013)

• Simple Set Sketching, Bæk (2022)

• Practical Rateless Set Reconciliation, Yang (2024)