Pytanie: Co wiemy o odległości Hamminga d (x, y)?
Odpowiedź:
- Jest nieujemna: d (x, y) ≥ 0
- Jest to tylko zero dla identycznych wejść: d (x, y) = 0 ⇔ x = y
- Jest symetryczny: d (x, y) = d (y, x)
- 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.
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.