"имеет только алгоритмы, включающие фактор n ^ 2 (если только K не очень большой). Это даже для нахождения только одной пары. Поэтому кажется, что это трудно улучшить, если вы не сделаете дополнительных предположений о структуре ваших экземпляров. Например, если вы предполагаете, что расстояние Хэмминга не очень велико, вы можете выбрать несколько столбцов, хешировать строки в сегменты в соответствии с ними в предположении, что эти столбцы точно совпадают, а затем выполнить попарное сравнение в каждом сегменте в отдельности. для другого набора случайных столбцов, чтобы минимизировать вероятность того, что вы пропустите некоторые пары.
ема
Предположим, что у вас есть 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 он должен возвратить pairlist {(i3, i4)}. Для k = 3 он должен вернуть {(i1, i2), (i1, i4), (i3, i4)}. И так далее.
АлгоритмНаивная реализация вычисляет все попарные расстояния, сортирует пары и возвращает k с наименьшим расстоянием: O (N ^ 2). Есть ли лучшие структуры данных или алгоритмы? Похоже, идеи изЭффективно найти двоичные строки с малым расстоянием Хэмминга в большом наборе не может использоваться, так как нет единого целого числа запроса.