Il modo migliore per cercare milioni di hash sfocati

Question

Ho gli hash compositi spamsum per circa dieci milioni di file in una tabella di database e mi piacerebbe trovare i file che sono ragionevolmente simili tra loro. hash Spamsum sono composti da due hash CTPH di massimo 64 byte e sembrano in questo modo:

384:w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND:wemfOGxqCfOTPi0ND 

Essi possono essere suddivisi in tre sezioni (dividere la stringa sui due punti): dimensioni

1. Block : 384 nell'hash sopra
2. Prima firma: w2mhnFnJF47jDnunEk3SlbJJ+SGfOypAYJwsn3gdqymefD4kkAGxqCfOTPi0ND
3. seconda firma: wemfOGxqCfOTPi0ND

La dimensione del blocco si riferisce alla dimensione del blocco per la prima firma e la dimensione del blocco per la seconda firma è doppia rispetto a quella della prima firma (qui: 384 x 2 = 768). Ogni file ha uno di questi hash compositi, il che significa che ogni file ha due firme con blocchi di dimensioni diverse.

Le firme dello spamsum possono essere confrontate solo se corrispondono alle dimensioni dei blocchi. Ciò significa che l'hash composito sopra può essere paragonato a qualsiasi altro hash composito che contiene una firma con una dimensione di blocco di 384 o 768. La somiglianza delle stringhe di firma per gli hash con dimensioni di blocco simili può essere presa come misura della somiglianza tra i file rappresentati dagli hash.

Quindi, se abbiamo:

• file1.blk2 = 768
• file1.sig2 = wemfOGxqCfOTPi0ND
• file2.blk1 = 768
• file2.sig1 = LsmfOGxqCfOTPi0ND

possiamo ottenere un senso del grado di somiglianza tra i due file calcolando qualche distanza di modifica ponderata (come la distanza di Levenshtein) per t lui due firme. Qui i due file sembrano essere abbastanza simili.

leven_dist(file1.sig2, file2.sig1) = 2 

Si può anche calcolare un punteggio di somiglianza normalizzato tra i due hash (vedi i dettagli here).

Mi piacerebbe trovare due file più simili al 70% in base a questi hash e ho una forte preferenza per l'utilizzo dei pacchetti software disponibili (o API/SDK), anche se non ho paura della codifica la mia strada attraverso il problema.

Ho provato a rompere gli hash e indicizzarli con Lucene (4.7.0), ma la ricerca sembra essere lenta e noiosa. Ecco un esempio delle domande Lucene che ho provato (per ogni firma singola - due volte al cancelletto e utilizzando il KeywordAnalyzer maiuscole e minuscole):

(blk1:768 AND sig1:wemfOGxqCfOTPi0ND~0.7) OR (blk2:768 AND sig2:wemfOGxqCfOTPi0ND~0.7) 

Sembra che Lucene di incredibly fast Levenshtein automata non accetta limiti modificare a distanza di cui sopra 2 (Ne ho bisogno per supportare fino a 0,7 x 64 ≃ 19) e che il suo normale algoritmo di distanza di modifica non è ottimizzato per lunghi termini di ricerca (the brute force method used does not cut off calculation once the distance limit is reached). Detto questo, può darsi che la mia query non sia ottimizzata per quello che voglio fare quindi non esitate a correggermi su questo.

Mi chiedo se posso realizzare ciò di cui ho bisogno utilizzando uno degli algoritmi offerti da Lucene, invece di calcolare direttamente la distanza di modifica. Ho sentito che gli alberi BK sono il modo migliore per indicizzare tali ricerche, ma non conosco le implementazioni disponibili dell'algoritmo (Lucene li usa del tutto?). Ho anche sentito che una soluzione probabile è quella di restringere la lista di ricerca usando i metodi n-grammi, ma non sono sicuro di come si possa confrontare il calcolo della distanza in termini di inclusività e velocità (sono sicuro che Lucene lo supporta). E a proposito, c'è un modo per far eseguire a Lucene una ricerca per termine in modalità parallela?

Dato che sto usando Lucene solo per pre-abbinare gli hash e che calcolo il punteggio di somiglianza reale utilizzando l'algoritmo appropriato più avanti, ho solo bisogno di un metodo che sia almeno inclusivo come la distanza di Levenshtein usata nel calcolo del punteggio di somiglianza - cioè, non voglio che il metodo di pre-abbinamento escluda gli hash che verrebbero contrassegnati come corrispondenze dall'algoritmo di punteggio.

Qualsiasi aiuto/teoria/riferimento/codice o indizio per iniziare è apprezzato.

Answer 1

Questa non è una risposta definitiva alla domanda, ma da allora ho provato un certo numero di metodi. Suppongo che gli hash vengano salvati in un database, ma i suggerimenti rimangono validi anche per le strutture di dati in memoria.

1. Salva tutte le firme (2 per hash) insieme alle dimensioni dei blocchi corrispondenti in una tabella figlio separata. Poiché solo le firme della stessa dimensione possono essere confrontate tra loro, è possibile filtrare la tabella in base alla dimensione del blocco prima di iniziare a confrontare le firme.
2. Riduce tutte le sequenze ripetitive da più di tre caratteri a tre caratteri ('bbbbb' -> 'bbb'). L'algoritmo di confronto di Spamsum lo fa automaticamente.
3. Spamsum utilizza una finestra a rotazione di 7 per confrontare le firme e non confronta le due firme che non hanno una sovrapposizione di 7 caratteri dopo aver eliminato le ripetizioni eccessive. Se si utilizza un database che supporta elenchi/matrici come campi, creare un campo con un elenco di tutte le possibili sequenze di 7 caratteri estratte da ciascuna firma. Quindi crea l'indice di corrispondenza più veloce a cui hai accesso in questo campo. Prima di provare a trovare la distanza di due firme, provare prima a fare corrispondenze esatte su questo campo (qualsiasi sette grammi in comune?).
4. L'ultimo passo che sto sperimentando è quello di salvare le firme e i loro sette grammi come le due modalità di un grafico bipartito, proiettando il grafico in modalità singola (composto solo da hash) e quindi calcolando la distanza di Levenshtein solo su nodi adiacenti con dimensioni di blocco simili.

I passaggi precedenti eseguono un buon pre-abbinamento e riducono sostanzialmente il numero di firme con cui ciascuna firma deve essere confrontata. Solo dopo questi è necessario calcolare la distanza modificata di Levenshtein/Damreau.