Skutecznie znajdź ciągi binarne z małą odległością Hamminga w dużym zestawie

Problem:

Biorąc pod uwagę dużą (~ 100 milionów) listę 32-bitowych liczb całkowitych bez znaku, 32-bitową wartość wejściową liczby całkowitej bez znaku i maksymalną odległość Hamminga , zwraca wszystkie elementy listy, które znajdują się w określonej odległości Hamminga wartości wejściowej.

Rzeczywista struktura danych do przechowywania listy jest otwarta, wymagania dotyczące wydajności narzucają rozwiązanie w pamięci, koszt budowy struktury danych jest drugorzędny, niski koszt zapytań o strukturę danych jest krytyczny.

Przykład:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

Moje dotychczasowe przemyślenia:

W przypadku zdegenerowanej odległości Hamminga równej 0 po prostu użyj posortowanej listy i wykonaj binarne wyszukiwanie określonej wartości wejściowej.

Gdyby odległość Hamminga wynosiłaby tylko 1, mógłbym odwrócić każdy bit w oryginalnym wejściu i powtórzyć powyższe 32 razy.

Jak skutecznie (bez skanowania całej listy) odkrywać członków listy z Odległość Hamminga> 1.

Pytanie: Co wiemy o odległości Hamminga d (x, y)?

Odpowiedź:

1. Jest nieujemna: d (x, y) ≥ 0
2. Jest to tylko zero dla identycznych wejść: d (x, y) = 0 ⇔ x = y
3. Jest symetryczny: d (x, y) = d (y, x)
4. Przestrzega nierówności trójkąta , d (x, z) ≤ d (x, y) + d (y, z)

Pytanie: Dlaczego nas to obchodzi?

Odpowiedź: Bo to oznacza, że odległość Hamminga jest metryka dla przestrzeni metrycznej . Istnieją algorytmy indeksowania przestrzeni metrycznych.

• Drzewo metryczne (Wikipedia)
• BK-tree (Wikipedia)
• M-tree (Wikipedia)
• Drzewo VP (Wikipedia)
• Drzewo okładki (Wikipedia)

Możesz również poszukać algorytmów „indeksowania przestrzennego” w ogóle, mając świadomość, że twoja przestrzeń nie jest euklidesowa, ale jest przestrzenią metryczną. Wiele książek na ten temat obejmuje indeksowanie ciągów za pomocą miernika, takiego jak odległość Hamminga.

Przypis: Jeśli porównujesz odległość Hamminga ciągów o stałej szerokości, możesz uzyskać znaczną poprawę wydajności, używając elementów składowych zespołu lub procesora. Na przykład z GCC ( manual ) robisz to:

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

Jeśli następnie poinformujesz GCC, że kompilujesz dla komputera z SSE4a, to uważam, że powinno to zredukować się do kilku rozkazów.

Edycja: według wielu źródeł jest to czasami / często wolniejsze niż zwykły kod maski / przesunięcia / dodania. Benchmarking pokazuje, że w moim systemie wersja C przewyższa GCC __builtin_popcounto około 160%.

Dodatek: sam byłem zaciekawiony problemem, więc sprofilowałem trzy implementacje: wyszukiwanie liniowe, drzewo BK i drzewo VP. Zauważ, że drzewa VP i BK są bardzo podobne. Elementy potomne węzła w drzewie BK są „skorupami” drzew zawierającymi punkty, z których każdy jest w stałej odległości od środka drzewa. Węzeł w drzewie VP ma dwoje dzieci, z których jedno zawiera wszystkie punkty w sferze wyśrodkowanej na środku węzła, a drugie zawiera wszystkie punkty na zewnątrz. Możesz więc myśleć o węźle VP jako o węźle BK z dwoma bardzo grubymi "powłokami" zamiast wielu drobniejszych.

Wyniki zostały zarejestrowane na moim komputerze 3,2 GHz, a algorytmy nie próbują wykorzystywać wielu rdzeni (co powinno być łatwe). Wybrałem bazę danych o rozmiarze 100 mln pseudolosowych liczb całkowitych. Wyniki to średnia z 1000 zapytań dla odległości 1..5 i 100 zapytań dla 6..10 i wyszukiwania liniowego.

• Baza danych: 100 mln pseudolosowych liczb całkowitych
• Liczba testów: 1000 dla dystansu 1..5, 100 dla dystansu 6..10 i liniowego
• Wyniki: średnia liczba trafień w zapytaniach (bardzo przybliżona)
• Prędkość: liczba zapytań na sekundę
• Pokrycie: średni procent sprawdzanej bazy danych na zapytanie

                - Drzewo BK - - Drzewo VP - - Liniowe -
Dystans Wyniki Prędkość Cov Prędkość Cov Prędkość Cov
1 0,90 3800 0,048% 4200 0,048%
2 11300 0,68% 330 0,65%
3130 56 3,8% 63 3,4%
4 970 18 12% 22 10%
5 5700 8,5 26% 10 22%
6 2,6e4 5,2 42% 6,0 37%
7 1, 1e5 3,7 60% 4, 1 54%
8 3,5e5 3,0 74% 3,2 70%
9 1,0e6 2,6 85% 2,7 82%
10 2, 5e6 2, 3 91% 2, 4 90%
dowolne 2,2 100%

W swoim komentarzu wspomniałeś:

Myślę, że drzewa BK można ulepszyć, generując kilka drzew BK z różnymi węzłami korzeniowymi i rozpraszając je.

Myślę, że to jest dokładnie powód, dla którego drzewo VP działa (nieco) lepiej niż drzewo BK. Będąc raczej „głębiej” niż „płytko”, porównuje się z większą liczbą punktów, zamiast korzystać z dokładniejszych porównań z mniejszą liczbą punktów. Podejrzewam, że różnice są bardziej ekstremalne w wyższych przestrzeniach wymiarowych.

Ostatnia wskazówka: węzły liści w drzewie powinny być po prostu płaskimi tablicami liczb całkowitych dla skanowania liniowego. W przypadku małych zestawów (może 1000 punktów lub mniej) będzie to szybsze i bardziej wydajne w pamięci.

Napisałem rozwiązanie, w którym reprezentuję liczby wejściowe w zbiorze bitów 2 ³² bitów bity, więc mogę sprawdzić w O (1), czy na wejściu znajduje się określona liczba. Następnie dla zadanej liczby i maksymalnej odległości rekurencyjnie generuję wszystkie liczby w tej odległości i porównuję je z zestawem bitów.

Na przykład dla maksymalnej odległości 5 jest to 242825 liczb ( suma _{d = 0 do 5} {32 wybierz d} ). Dla porównania, rozwiązanie drzewa VP firmy Dietrich Epp przechodzi na przykład przez 22% ze 100 milionów liczb, czyli przez 22 miliony liczb.

Użyłem kodu / rozwiązań Dietricha jako podstawy do dodania mojego rozwiązania i porównania go z jego. Oto prędkości w zapytaniach na sekundę dla maksymalnych odległości do 10:

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

W przypadku małych odległości rozwiązanie bitowe jest zdecydowanie najszybszym z czterech. Autor pytania Eric skomentował poniżej, że największa odległość będąca przedmiotem zainteresowania będzie prawdopodobnie wynosić 4-5. Oczywiście, moje rozwiązanie bitowe staje się wolniejsze dla większych odległości, nawet wolniejsze niż wyszukiwanie liniowe (dla odległości 32 przechodzi przez 2 ³² liczby). Ale na dystansie 9 nadal łatwo prowadzi.

Zmodyfikowałem też testy Dietricha. Każdy z powyższych wyników ma na celu umożliwienie algorytmowi rozwiązania co najmniej trzech zapytań i tylu zapytań, ile może w około 15 sekund (robię rundy z 1, 2, 4, 8, 16 itd., Aż co najmniej 10 sekund przeszedł łącznie). To dość stabilne, nawet otrzymuję podobne liczby tylko przez 1 sekundę.

Mój procesor to i7-6700. Mój kod (na podstawie Dietricha) jest tutaj (zignoruj ​​tam dokumentację przynajmniej na razie, nie jestem pewien, co z tym zrobić, ale tree.czawiera cały kod i moje test.batpokazy, jak skompilowałem i uruchomiłem (użyłem flag z Dietricha Makefile)) . Skrót do mojego rozwiązania .

Jedno zastrzeżenie: moje wyniki zapytania zawierają liczby tylko raz, więc jeśli lista wejściowa zawiera zduplikowane liczby, może to być pożądane lub nie. W przypadku kwestionowanego autora Erica nie było duplikatów (patrz komentarz poniżej). W każdym razie to rozwiązanie może być dobre dla osób, które albo nie mają żadnych duplikatów w danych wejściowych, albo nie chcą lub potrzebują duplikatów w wynikach zapytania (myślę, że wyniki czystego zapytania są tylko środkiem do celu jakiś inny kod zamienia liczby w coś innego, na przykład mapowanie liczby do listy plików, których hash jest tym numerem).

Powszechnym podejściem (przynajmniej dla mnie powszechnym) jest podzielenie ciągu bitów na kilka fragmentów i zapytanie o te fragmenty w celu uzyskania dokładnego dopasowania jako kroku przed filtrem. Jeśli pracujesz z plikami, tworzysz tyle plików, ile masz porcji (np. 4 tutaj) z każdą porcją permutowaną z przodu, a następnie sortujesz pliki. Możesz skorzystać z wyszukiwania binarnego, a nawet rozszerzyć wyszukiwanie powyżej i poniżej pasującego fragmentu, aby otrzymać bonus.

Następnie możesz wykonać bitowe obliczenia odległości hammingu na zwróconych wynikach, które powinny być tylko mniejszym podzbiorem całego zestawu danych. Można to zrobić za pomocą plików danych lub tabel SQL.

Podsumowując: załóżmy, że masz kilka 32-bitowych ciągów w bazie danych lub plikach i chcesz znaleźć każdy skrót, który znajduje się w odległości do 3 bitów hamming lub mniejszej od ciągu bitowego zapytania:

1. utwórz tabelę z czterema kolumnami: każda będzie zawierała 8-bitowy fragment 32-bitowych skrótów, islice 1 do 4. Lub, jeśli używasz plików, utwórz cztery pliki, z których każdy będzie permutacją wycinków o jedna „wyspa” z przodu każdego „rzędu”

2. podziel swój ciąg bitów zapytania w ten sam sposób w qslice od 1 do 4.

3. przeszukaj tę tabelę w taki sposób, że dowolny z qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Daje to każdy ciąg, który znajduje się w obrębie 7 bitów ( 8 - 1) od ciągu zapytania. Jeśli używasz pliku, przeprowadź wyszukiwanie binarne w każdym z czterech plików permutowanych, aby uzyskać te same wyniki.

4. dla każdego zwróconego ciągu bitowego oblicz dokładną odległość Hamminga parami z zapytaniem o ciąg bitów (rekonstruując ciągi bitów po stronie indeksu z czterech wycinków z bazy danych lub z pliku permutowanego)

Liczba operacji w kroku 4 powinna być znacznie mniejsza niż pełne obliczenie hammujące w parach całej tabeli i jest bardzo wydajne w praktyce. Co więcej, łatwo jest podzielić pliki na mniejsze pliki, aby uzyskać większą szybkość przy użyciu równoległości.

Teraz oczywiście w twoim przypadku szukasz swego rodzaju samosprzężenia, czyli wszystkich wartości, które są w pewnej odległości od siebie. To samo podejście nadal działa IMHO, chociaż będziesz musiał rozszerzać w górę iw dół od punktu początkowego dla permutacji (używając plików lub list), które współdzielą początkowy fragment i obliczają odległość Hamminga dla wynikowego klastra.

Jeśli działasz w pamięci zamiast w plikach, zestaw danych 100M 32-bitowych ciągów danych będzie w zakresie 4 GB. Stąd cztery permutowane listy mogą wymagać około 16 GB + pamięci RAM. Chociaż uzyskuję doskonałe wyniki z plikami mapowanymi w pamięci i muszę mniej pamięci RAM dla zestawów danych o podobnej wielkości.

Dostępne są implementacje open source. Najlepsze w przestrzeni jest IMHO to zrobione dla Simhash przez Moz , C ++, ale zaprojektowane dla ciągów 64-bitowych, a nie 32-bitowych.

To ograniczone podejście na odległość zostało po raz pierwszy opisane jako AFAIK przez Mosesa Charikara w jego nowatorskim artykule „simhash” i odpowiednim patencie Google :

5. PRZYBLIŻONE WYSZUKIWANIE NAJBLIŻSZEGO SĄSIADA W PRZESTRZENI UDERZENIA

[…]

Mając wektory bitowe składające się z d bitów każdy, wybieramy N = O (n 1 / (1+)) losowych permutacji bitów. Dla każdej losowej permutacji σ, utrzymujemy posortowaną kolejność O σ wektorów bitowych, w leksykograficznym porządku bitów permutowanych przez σ. Mając wektor bitowy zapytania q, znajdujemy przybliżonego najbliższego sąsiada, wykonując następujące czynności:

Dla każdej permutacji σ wykonujemy przeszukiwanie binarne na O σ, aby zlokalizować dwa wektory bitowe najbliższe q (w porządku leksykograficznym uzyskanym przez bity permutowane przez σ). Teraz przeszukujemy każde z posortowanych porządków O σ badając elementy powyżej i poniżej pozycji zwróconej przez wyszukiwanie binarne w kolejności według długości najdłuższego prefiksu, który pasuje do q.

Monika Henziger rozwinęła to w swoim artykule „Znajdowanie prawie zduplikowanych stron internetowych: ocena algorytmów na dużą skalę” :

3.3 Wyniki dla algorytmu C

Podzieliliśmy ciąg bitów każdej strony na 12 nienakładających się fragmentów 4-bajtowych, tworząc 20-bajtowe fragmenty i obliczyliśmy podobieństwo C wszystkich stron, które mają co najmniej jeden wspólny element. Takie podejście gwarantuje znalezienie wszystkich par stron z różnicą do 11, tj. C-podobieństwo 373, ale może pominąć niektóre dla większych różnic.

Jest to również wyjaśnione w artykule Detecting Near-Duplicates for Web Crawling autorstwa Gurmeeta Singha Manku, Arvinda Jaina i Anisha Das Sarmy:

3. PROBLEM Z ODLEGŁOŚCIĄ UDERZENIA

Definicja: Mając zbiór f-bitowych odcisków palców i kwerendy F, należy określić, czy istniejący odcisk palca różni się od F w co najwyżej k bitach. (W wersji wsadowej powyższego problemu mamy zestaw odcisków palców zamiast pojedynczego odcisku cyfrowego zapytania)

[…]

Intuicja: Weź pod uwagę posortowaną tabelę zawierającą 2-bitowe, prawdziwie losowe odciski palców. Skoncentruj się tylko na najbardziej znaczących bitach d w tabeli. Lista tych liczb d-bitowych daje „prawie licznik” w tym sensie, że (a) istnieje całkiem sporo kombinacji 2-bitowych i (b) bardzo niewiele kombinacji d-bitowych jest zduplikowanych. Z drugiej strony najmniej znaczące bity f - d są „prawie losowe”.

Teraz wybierz d takie, że | d - d | jest małą liczbą całkowitą. Ponieważ tabela jest posortowana, wystarczy jedna sonda, aby zidentyfikować wszystkie odciski palców, które pasują do F w najbardziej znaczących pozycjach bitów. Ponieważ | d - d | jest niewielka, oczekuje się, że liczba takich dopasowań również będzie niewielka. Dla każdego pasującego odcisku palca możemy łatwo ustalić, czy różni się on od F w co najwyżej k-bitowej pozycji, czy nie (różnice te byłyby naturalnie ograniczone do f - d najmniej znaczących pozycji bitowych).

Opisana powyżej procedura pomaga nam zlokalizować istniejący odcisk palca, który różni się od F w k-bitowych pozycjach, z których wszystkie są ograniczone do najmniej znaczących f - d bitów F. Zajmuje się to sporą liczbą przypadków. Aby uwzględnić wszystkie przypadki, wystarczy zbudować niewielką liczbę dodatkowych posortowanych tabel, jak formalnie opisano w następnej sekcji.

Uwaga: opublikowałem podobną odpowiedź na pytanie dotyczące tylko bazy danych

Możesz wstępnie obliczyć każdą możliwą odmianę swojej oryginalnej listy w określonej odległości Hamminga i zapisać ją w filtrze bloom. Daje to szybkie „NIE”, ale niekoniecznie jasną odpowiedź „TAK”.

Aby ustawić TAK, zapisz listę wszystkich oryginalnych wartości związanych z każdą pozycją w filtrze poświaty i przeglądaj je pojedynczo. Zoptymalizuj rozmiar filtra poświaty pod kątem kompromisów między szybkością a pamięcią.

Nie jestem pewien, czy wszystko działa dokładnie, ale wydaje się dobrym podejściem, jeśli masz pamięć RAM do nagrania w czasie wykonywania i chcesz spędzić bardzo dużo czasu na wstępnych obliczeniach.

Co powiesz na sortowanie listy, a następnie wyszukiwanie binarne na tej posortowanej liście według różnych możliwych wartości w obrębie odległości Hamminga?

Jednym z możliwych sposobów rozwiązania tego problemu jest użycie struktury danych typu rozłącznego . Pomysł polega na scaleniu członków listy z odległością Hamminga <= k w tym samym zestawie. Oto zarys algorytmu:

• Dla każdego członka listy oblicz każdą możliwą wartość z odległością Hamminga <= k. Dla k = 1 są 32 wartości (dla wartości 32-bitowych). Dla wartości k = 2, 32 + 32 * 31/2.

  • Dla każdej obliczonej wartości sprawdź, czy znajduje się na oryginalnym wejściu. Aby to sprawdzić, możesz użyć tablicy o rozmiarze 2 ^ 32 lub mapy skrótów.

  • Jeśli wartość znajduje się w oryginalnym wejściu, wykonaj operację "sumowania" z elementem listy .

  • Zachowaj liczbę operacji sumowania wykonanych w zmiennej.

Rozpoczynasz algorytm od N rozłącznych zbiorów (gdzie N to liczba elementów na wejściu). Za każdym razem, gdy wykonujesz operację sumowania, zmniejszasz o 1 liczbę rozłącznych zestawów. Kiedy algorytm się zakończy, rozłączna struktura danych będzie miała wszystkie wartości z odległością Hamminga <= k pogrupowane w rozłączne zbiory. Tę rozłączną strukturę danych można obliczyć w czasie prawie liniowym .

Oto prosty pomysł: wykonaj sortowanie bajtowe radix 100m wejściowych liczb całkowitych, zaczynając od najbardziej znaczących bajtów, śledząc granice segmentu na pierwszych trzech poziomach w jakiejś zewnętrznej strukturze.

Aby zapytać, zacznij od budżetu na odległość di słowa wejściowego w. Dla każdego segmentu na najwyższym poziomie z wartością bajtu boblicz odległość Hamminga d_0między ba najwyższym bajtem w. Przeszukuj rekurencyjnie ten zasobnik z budżetem d - d_0: to znaczy dla każdej wartości bajtu b'niech d_1będzie odległość Hamminga między b'a drugim bajtem w. Przeszukuj rekursywnie w trzeciej warstwie z budżetem w wysokości d - d_0 - d_1itd.

Zwróć uwagę, że wiadra tworzą drzewo. Gdy budżet stanie się ujemny, przestań przeszukiwać to poddrzewo. Jeśli rekurencyjnie schodzisz do liścia bez nadmuchiwania budżetu odległości, ta wartość liścia powinna być częścią wyniku.

Oto jeden ze sposobów przedstawienia zewnętrznej struktury granic zasobnika: tablica o długości 16_777_216 ( = (2**8)**3 = 2**24), gdzie element pod indeksemi jest początkowym indeksem zawierającym wartości z przedziału [256 * i, 256 * i + 255]. Aby znaleźć indeks o jeden poza końcem tego segmentu, spójrz na indeks i + 1 (lub użyj końca tablicy dla i + 1 = 2 ** 24).

Budżet pamięci wynosi 100 m * 4 bajty na słowo = 400 MB na dane wejściowe i 2 ** 24 * 4 bajty na adres = 64 MB na strukturę indeksowania, czyli łącznie prawie pół gigabajta. Struktura indeksowania stanowi 6,25% narzutu na surowe dane. Oczywiście po skonstruowaniu struktury indeksowania wystarczy zapisać najniższy bajt każdego słowa wejściowego, ponieważ pozostałe trzy są ukryte w indeksie struktury indeksowania, co daje w sumie ~ (64 + 50) MB.

Jeśli twoje dane wejściowe nie są równomiernie rozłożone, możesz permutować bity swoich słów wejściowych za pomocą (pojedynczej, powszechnie dzielonej) permutacji, która umieszcza całą entropię w kierunku wierzchołka drzewa. W ten sposób pierwszy poziom przycinania wyeliminuje większe fragmenty przestrzeni wyszukiwania.

Wypróbowałem kilka eksperymentów, a to działa równie dobrze jak wyszukiwanie liniowe, czasem nawet gorzej. To tyle, jeśli chodzi o ten wymyślny pomysł. No cóż, przynajmniej to wydajna pamięć.