Mam kompilacje mieszane spamsum dla około dziesięciu milionów plików w tabeli bazy danych i chciałbym znaleźć pliki, które są rozsądnie podobne do siebie. Spamsum skróty składają się z dwóch mieszań CTPH maksymalnych 64 bajtów i wyglądają tak:Najlepszy sposób wyszukiwania milionów rozmytych skrótów
384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND
Mogą one być podzielone na trzy sekcje (Split ciąg na dwukropkiem): wielkość
- Blok :
384
w hash powyżej - Pierwszy podpis:
w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
- drugi podpis:
wemfOGxqCfOTPi0ND
Rozmiar bloku odnosi się do rozmiaru bloku dla pierwszego podpisu, a rozmiar bloku dla drugiego podpisu jest dwa razy większy niż pierwszego podpisu (tutaj: 384 x 2 = 768). Każdy plik ma jeden z tych złożonych skrótów, co oznacza, że każdy plik ma dwie sygnatury o różnych rozmiarach bloków.
Sygnatury spamsum można porównywać tylko wtedy, gdy odpowiadają rozmiarom bloków. Oznacza to, że powyższy hasz złożony można porównać z dowolnym innym hashiem złożonym, który zawiera sygnaturę o rozmiarze bloku 384 lub 768. Podobieństwo łańcuchów sygnatur dla skrótów o podobnej wielkości bloku może być miarą podobieństwa między pliki reprezentowane przez skróty.
Więc jeśli mamy:
file1.blk2 = 768
file1.sig2 = wemfOGxqCfOTPi0ND
file2.blk1 = 768
file2.sig1 = LsmfOGxqCfOTPi0ND
możemy uzyskać poczucie stopnia podobieństwa dwóch plików przez obliczenie część ważonej odległości edycyjnej (np. odległość Levenshteina) dla t on dwa podpisy. Tutaj dwa pliki wydają się dość podobne.
leven_dist(file1.sig2, file2.sig1) = 2
Można obliczyć znormalizowanej wartości podobieństwa pomiędzy dwoma skrótów (patrz szczegóły here).
Chciałbym znaleźć dwa pliki, które są podobne w ponad 70% na podstawie tych skrótów, i mam zdecydowaną wolę do korzystania z dostępnych pakietów oprogramowania (lub API/SDK), chociaż nie boję się kodowania moja droga przez problem.
Próbowałem odciąć hashe i indeksować je za pomocą Lucene (4.7.0), ale wyszukiwanie wydaje się być powolne i nudne. Oto przykład zapytań Lucene próbowałem (dla każdego pojedynczego podpisu - dwa razy hash i stosując wielkość liter KeywordAnalyzer):
(blk1:768 AND sig1:wemfOGxqCfOTPi0ND~0.7) OR (blk2:768 AND sig2:wemfOGxqCfOTPi0ND~0.7)
Wydaje się, że Lucene na incredibly fast Levenshtein automata nie akceptuje limity edit odległości powyżej 2 (Potrzebuję go do obsługi 0,7 x 64 ≃ 19) i że jego normalny algorytm redagowania nie jest zoptymalizowany pod kątem długich terminów wyszukiwania (the brute force method used does not cut off calculation once the distance limit is reached.) Powiedział, że może to być, że moje zapytanie nie jest zoptymalizowane pod kątem tego, co chcę robić , więc nie wahaj się mnie poprawić.
Zastanawiam się, czy mogę wykonać to, czego potrzebuję, używając dowolnego z algorytmów oferowanych przez Lucene, zamiast bezpośrednio obliczać odległość edycji. Słyszałem, że drzewa BK są najlepszym sposobem indeksowania takich wyszukiwań, ale nie znam dostępnych implementacji algorytmu (czy Lucene w ogóle je wykorzystuje?). Słyszałem również, że prawdopodobnym rozwiązaniem jest zawężenie listy wyszukiwania za pomocą metod n-gramowych, ale nie jestem pewien, jak to się ma do edytowania obliczania odległości pod względem inkluzywności i szybkości (jestem prawie pewien, że Lucene to obsługuje). A tak przy okazji, czy istnieje sposób, aby Lucene przeprowadziła wyszukiwanie w trybie równoległym?
Biorąc pod uwagę, że używam Lucene tylko do wstępnego dopasowania skrótów i że obliczam rzeczywisty wynik podobieństwa za pomocą odpowiedniego algorytmu później, po prostu potrzebuję metody, która jest co najmniej tak samo skuteczna jak odległość Levenshteina użyta w obliczaniu wyniku podobieństwa - to znaczy, nie chcę, aby metoda wstępnego dopasowywania wykluczała skróty, które zostałyby oznaczone jako dopasowania przez algorytm oceny.
Każda pomoc/teoria/odniesienie/kod lub wskazówka na początek jest mile widziane.