Быстрое вычисление пар с наименьшим расстоянием Хэмминга

Question

Задача

Предположим, у вас есть N (~ 100k-1m) целых / битовых строк каждая K (например, 256) бит длиной. Алгоритм должен возвращать k пар с наименьшим парным расстоянием Хэмминга.

Пример

N = 4
K = 8
i1 = 00010011
i2 = 01010101
i3 = 11000000
i4 = 11000011


HammingDistance(i1,i2) = 3
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 3
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 4
HammingDistance(i3,i4) = 2

Для k = 1 он должен возвратить список участников {(i3, i4)}. Для k = 3 он должен вернуть {(i1, i2), (i1, i4), (i3, i4)}. И так далее.

Алгоритм

Наивная реализация вычисляет все попарные расстояния, сортирует пары и возвращает k с наименьшим расстоянием: O (N ^ 2). Есть ли лучшие структуры данных или алгоритмы? Похоже, идеи из Эффективно найти двоичные строки с малым расстоянием Хэмминга в большом наборе нельзя использовать, так как нет единого целого числа запроса.

Answer 1

В недавней статье " Проблема ближайших пар по метрике Хемминга " есть только алгоритмы, включающие фактор n ^ 2 (если только K не очень большой).Это даже для нахождения только одной пары.Таким образом, кажется, что это трудно улучшить, если вы не сделаете дальнейшие предположения о структуре ваших экземпляров.Например, если вы предполагаете, что расстояние Хэмминга не очень велико, вы можете выбрать несколько столбцов, хешировать строки в сегменты в соответствии с ними в предположении, что эти столбцы точно совпадают, а затем выполнить попарное сравнение в каждом блоке в отдельности.Повторите это для другого набора случайных столбцов, чтобы минимизировать вероятность того, что вы пропустите некоторые пары.