Najlepszy sposób wyszukiwania milionów rozmytych skrótów

Question

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:

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND 

Mogą one być podzielone na trzy sekcje (Split ciąg na dwukropkiem): wielkość

1. Blok : 384 w hash powyżej
2. Pierwszy podpis: w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
3. 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.

Answer 1

To nie jest ostateczna odpowiedź na to pytanie, ale od tamtej pory próbowałem wielu metod. Zakładam, że skróty są zapisywane w bazie danych, ale sugestie pozostają ważne również w strukturach danych w pamięci.

1. Zapisz wszystkie podpisy (2 na hasz) wraz z odpowiadającymi im rozmiarami bloków w osobnej tabeli podrzędnej. Ponieważ tylko sygnatury o tym samym rozmiarze mogą być porównywane ze sobą, możesz filtrować tabelę według rozmiaru bloku przed rozpoczęciem porównywania podpisów.
2. Zmniejsz wszystkie powtarzające się sekwencje złożone z więcej niż trzech znaków do trzech znaków ("bbbbb" -> "bbb"). Algorytm porównania Spamsum robi to automatycznie.
3. Spamsum używa ruchomego okienka 7 do porównywania podpisów i nie porównuje żadnych dwóch sygnatur, które nie mają siedmiokrotnego nałożenia po wyeliminowaniu nadmiernych powtórzeń. Jeśli używasz bazy danych, która obsługuje listy/tablice jako pola, utwórz pole z listą wszystkich możliwych 7-znakowych sekwencji wyodrębnionych z każdego podpisu. Następnie utwórz najszybszy indeks dokładnych dopasowań, do którego masz dostęp w tym polu. Zanim spróbujesz znaleźć odległość dwóch podpisów, najpierw spróbuj wykonać dokładne dopasowania na tym polu (każde siedmiogodzinne wspólne?).
4. Ostatnim krokiem, w którym eksperymentuję, jest zapisanie sygnatur i ich siedmiu gramów jako dwóch trybów dwuczęściowego wykresu, rzutowanie wykresu na tryb pojedynczy (złożony tylko z skrótów), a następnie obliczenie odległości Levenshteina tylko na sąsiednich węzłach o podobnych rozmiarach bloków.

Powyższe czynności zapewniają dobre wstępne dopasowanie i znacznie zmniejszają liczbę podpisów, z którymi każdy podpis musi być porównywany. Dopiero potem należy obliczyć zmodyfikowaną odległość Levenshtein/Damreau.