Znajdź wszystkie pary wartości bliskich odległości Hamminga

Mam kilka milionów wartości 32-bitowych. Dla każdej wartości chcę znaleźć wszystkie inne wartości w odległości Hamminga wynoszącej 5. W podejściu naiwnym wymaga to porównań $O(N^2)$ , których chcę uniknąć.

Uświadomiłem sobie, że jeśli potraktowałem te 32-bitowe wartości jako liczby całkowite i posortowałem listę raz, to wartości, które różniły się tylko najmniej znaczącymi bitami, były bardzo blisko siebie. To pozwala mi mieć krótsze „okno” lub zakres liczb, w którym mogę wykonać rzeczywiste porównania par dla dokładnej odległości uderzenia. Jednak gdy 2 wartości różnią się tylko bitami wyższego rzędu, kończą się poza tym „oknem” i pojawiają się na przeciwnych końcach posortowanej listy. Na przykład

11010010101001110001111001010110

01010010101001110001111001010110

byłoby bardzo daleko od siebie, nawet jeśli ich odległość uderzenia wynosi 1. Ponieważ odległość uderzenia między 2 wartościami jest zachowana, gdy obie są obracane, pomyślałem, że wykonując 32 obroty w lewo, a następnie sortując listę za każdym razem, prawdopodobne jest, że 2 wartości skończy wystarczająco blisko na posortowanej liście w co najmniej jednym z nich.

Chociaż to podejście daje mi dobre wyniki, staram się formalnie ustalić poprawność tego podejścia.
Biorąc pod uwagę, że szukam pasujących wartości o odległości uderzenia $k$ lub mniejszej, czy naprawdę muszę wykonywać wszystkie 32-bitowe obroty? Na przykład, jeśli $k=1$ a mój rozmiar okna wynosi 1000, muszę to robić przy maks. 24-bitowych obrotach, ponieważ nawet jeśli bit zbłąkany pojawił się w jednym z 8 bitów niższego rzędu, uzyskane liczby nie będą się różnić o więcej niż 1000.

ds.algorithms co.combinatorics approximation-algorithms

— karterk
źródło

Tylko pomysły z 20 sekund myślenia: Co powiesz na coś według Gray-Code? Co powiesz na podzielenie listy 32-bitowych map bitowych na cztery listy 8-bitowych map bitowych, a następnie użycie swojej techniki?

— Karl Damgaard Asmussen

2^{20}

$2^{20}$

2^{30}

$2^{30}$

@minar: Mam 3-4 miliony takich 32-bitowych map bitowych.

— karterk

A [i]

$A[i]$

4 \times 10^{9}

$4\times 10^9$ A[i].close

i

$i$

myślę, że istnieje podobna koncepcja „czworokątów”, z wyjątkiem tego, że można zastosować hipersześciany. algorytm lokalizuje i rekurencyjnie lokalizuje wektory w hipersześcianach, a następnie, gdy chcesz wyszukać „pobliskie” bitvektory, przeszukujesz tylko „pobliskie” hipersześciany. podejrzewam, że może to być studiowane i gdzieś w gazecie .... nie jestem pewien, czy właściwe warunki ....

— dniu

Odpowiedzi:

Jak powiedziano, twoje podejście jest problematyczne, ponieważ jeśli 2 bitmapy mają równomiernie rozmieszczone różnice, to przy każdym obrocie będą różnice na niektórych bitach wyższego rzędu.

$5$ $1/50$ $64\cdot N$ $N\approx 2^{22}$

$4$ $5$ $529\cdot N$ $4960\cdot N$

Dodatkowe informacje:

$5$ $16$ $32$ $\frac{(\binom{16}{5})}{(\binom{32}{5})} \approx 0.0217$ $\frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217$
Konstrukcja list dla każdego elementu z oryginalnej listy umieszczona jest na liście rozszerzonej: sam element, wszystkie elementy różniące się w jednej pozycji i wszystkie elementy różniące się w dwóch pozycjach (zachowując informacje o oryginalnym elemencie). Liczba kopii dla każdego elementu wynosiWszelkie kolizje na tej liście (wykryte po sortowaniu) odpowiadają dwóm oryginalnym elementom na odległość maksymalnie . Pamiętaj, że każdą parę można wykryć kilka razy, więc będziesz musiał usunąć duplikaty (ale tak było już w przypadku początkowego algorytmu). $1+32+\binom{32}{2}=529.$ $4$
Do ostatniego przejścia lepiej przyciąć rozszerzoną listę elementów, aby zachować tylko te w dokładnej odległości od ich oryginalnego elementu. Następnie dla każdego oryginalnego elementu utwórz elementów w odległości i wyszukaj je na liście rozszerzonej. Jeszcze raz musisz usunąć duplikaty, ponieważ każda para zostanie wykryta razy. [Z większą ostrożnością możesz prawdopodobnie przewidzieć / uniknąć większości duplikatów, ale nie jestem pewien, czy warto.] $2$ $\binom{32}{3}=4960$ $3$ $\binom{5}{3}=10$

— minar
źródło

Czy w pierwszym podejściu mówisz, że permutuję mapę bitową w niektórych wcześniej ustalonych zleceniach zamiast wykonywać tylko rotacje bitów? Czy możesz wyjaśnić, w jaki sposób uzyskałeś prawdopodobieństwo 1/50? Ponadto, w przypadku drugiego podejścia, czy muszę najpierw zbudować indeks mojej listy, a następnie dla każdego elementu - wygenerować kombinacje (32C1 + 32C2) i porównać je z tym indeksem, aby zidentyfikować wszystkie mapy bitowe różniące się odległością 2? Byłoby wspaniale, gdybyś mógł to wyjaśnić dalej. Dzięki.

— karterk

odpowiedź minara jest doskonała i prawdopodobnie jest właściwym podejściem do tego konkretnego problemu. Wymienię jednak jeszcze jedno możliwe podejście:

Możesz użyć funkcji skrótu wrażliwej na lokalizację (LSH). Wrażliwa na lokalizację funkcja skrótu została zaprojektowana w taki sposób, że jeśli są bliskie odległości Hamminga, to . Jeśli masz taki skrót , możesz zapisać wszystkie wartości w tabeli skrótów (używając funkcji skrótu i otwartego skrótu ), a następnie bardzo szybko będziesz w stanie znaleźć wszystkie pary wartości, które są bliskie w odległości Hamminga . Istnieją różne techniki konstruowania LSH; możesz przejrzeć odniesienia do tego tematu, aby znaleźć kilku kandydatów. $H$ $x,y$ $H(x)=H(y)$ $H$ $H$

To powiedziawszy, dla twojego konkretnego problemu (z określonymi parametrami, o których wspomniałeś), oczekuję, że dwa algorytmy minara okażą się lepsze w praktyce niż jakikolwiek schemat oparty na LSH. Wspominam o tym tylko w przypadku, gdy inni czytelnicy przychodzą tutaj na to pytanie z podobnym problemem, ale z różnymi parametrami, w których LSH może mieć większy sens.

— DW
źródło