Trova in modo efficiente le stringhe binarie con bassa distanza di marce in grande set
https://stackoverflow.com/questions/6389841
-
29-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Problema:
Dato un grande elenco (~ 100 milioni) di numeri interi non firmati a 32 bit, un valore di input intero non firmato a 32 bit e un massimo Distanza di ket, Restituisci tutti i membri dell'elenco che si trovano nella distanza di martello specificata del valore di input.
La struttura effettiva dei dati per trattenere l'elenco è aperta, i requisiti delle prestazioni determinano una soluzione in memoria, il costo per costruire la struttura dei dati è secondario, a basso costo per interrogare la struttura dei dati è fondamentale.
Esempio:
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.
I miei pensieri finora:
Per il caso degenerato di una distanza di martellina di 0, basta utilizzare un elenco ordinato e fare una ricerca binaria per il valore di input specifico.
Se la distanza di Hamming sarebbe sempre 1, potrei capovolgere ogni bit nell'ingresso originale e ripetere i 32 volte sopra.
Come posso (senza scansionare l'intero elenco) Scopri i membri dell'elenco con una distanza di Hamming> 1.
Soluzione
Domanda: Cosa sappiamo della distanza di Hamming D (x, y)?
Risposta:
- È non negativo: d (x, y) ≥ 0
- È solo zero per input identici: d (x, y) = 0 ⇔ x = y
- È simmetrico: d (x, y) = d (y, x)
- Obbedisce al disuguaglianza del triangolo, d (x, z) ≤ d (x, y) + d (y, z)
Domanda: Perché ci preoccupiamo?
Risposta: Perché significa che la distanza di Hamming è a metrica per un spazio metrico. Esistono algoritmi per gli spazi metrici di indicizzazione.
- Albero metrico (Wikipedia)
- BK-Tree (Wikipedia)
- M-albero (Wikipedia)
- VP-Tree (Wikipedia)
- Albero di copertura (Wikipedia)
Puoi anche cercare algoritmi per "indicizzazione spaziale" in generale, armato della consapevolezza che il tuo spazio non è euclideo ma esso è uno spazio metrico. Molti libri su questo argomento coprono l'indicizzazione delle stringhe usando una metrica come la distanza di Hamming.
Nota: Se si confronta la distanza di martelle delle stringhe di larghezza fissa, potresti essere in grado di ottenere un significativo miglioramento delle prestazioni utilizzando l'intrinseca di assemblaggio o processore. Ad esempio, con GCC (Manuale) tu lo fai:
static inline int distance(unsigned x, unsigned y)
{
return __builtin_popcount(x^y);
}
Se ti informi di GCC che stai compilando per un computer con SSE4A, credo che ciò dovrebbe ridurre solo un paio di codici operativi.
Modificare: Secondo una serie di fonti, questo è talvolta/spesso più lento del solito codice maschera/shift/aggiungi. Il benchmarking mostra che sul mio sistema, una versione C sovraperform __builtin_popcount entro circa il 160%.
Addendum: Ero curioso del problema da solo, quindi ho profilato tre implementazioni: ricerca lineare, albero BK e VP Tree. Si noti che gli alberi VP e BK sono molto simili. I bambini di un nodo in un albero BK sono "gusci" di alberi contenenti punti che sono ciascuno una distanza fissa dal centro dell'albero. Un nodo in un albero VP ha due bambini, uno contenente tutti i punti all'interno di una sfera centrata sul centro del nodo e l'altro figlio contenente tutti i punti all'esterno. Quindi puoi pensare a un nodo VP come a un nodo BK con due "gusci" molto spesse anziché molti più fini.
I risultati sono stati catturati sul mio PC da 3,2 GHz e gli algoritmi non tentano di utilizzare più core (che dovrebbero essere facili). Ho scelto una dimensione del database di interi pseudorandom da 100 m. I risultati sono la media di 1000 query per la distanza 1..5 e 100 query per 6..10 e la ricerca lineare.
- Database: interi pseudorandom 100m
- Numero di test: 1000 per la distanza 1..5, 100 per la distanza 6..10 e lineare
- Risultati: # medio di colpi di query (molto approssimativo)
- Velocità: numero di domande al secondo
- Copertura: percentuale media del database esaminato per query
-- BK Tree -- -- VP Tree -- -- Linear -- Dist Results Speed Cov Speed Cov Speed Cov 1 0.90 3800 0.048% 4200 0.048% 2 11 300 0.68% 330 0.65% 3 130 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% any 2.2 100%
Nel tuo commento, hai menzionato:
Penso che gli alberi BK potrebbero essere migliorati generando un mucchio di alberi BK con diversi nodi radicali e diffondendoli.
Penso che questo sia esattamente il motivo per cui l'albero VP si comporta (leggermente) meglio dell'albero BK. Essendo "più profondo" piuttosto che "superficiale", si confronta con più punti piuttosto che usare confronti a grana più fine con meno punti. Sospetto che le differenze siano più estreme negli spazi dimensionali più elevati.
Un suggerimento finale: i nodi fogliare nell'albero dovrebbero essere solo array piatti di numeri interi per una scansione lineare. Per piccoli set (forse 1000 punti o meno) questo sarà più veloce ed efficiente dalla memoria.
Altri suggerimenti
Ho scritto una soluzione in cui rappresento i numeri di input in un bitset di 232 bit, quindi posso controllare O (1) se un determinato numero è nell'input. Quindi per un numero interrogato e una distanza massima, genererò ricorsivamente tutti i numeri a quella distanza e li controllo contro il bitset.
Ad esempio per la distanza massima 5, questo è 242825 numeri (sommad = 0 a 5 {32 Scegli d}). Per confronto, la soluzione VP-tree di Dietrich EPP, ad esempio, passa il 22% dei 100 milioni di numeri, cioè attraverso 22 milioni di numeri.
Ho usato il codice/soluzioni di Dietrich come base per aggiungere la mia soluzione e confrontarla con la sua. Ecco le velocità, nelle query al secondo, per le massime distanze fino a 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)
Per piccole distanze, la soluzione bitset è di gran lunga la più veloce dei quattro. L'autore di domande Eric ha commentato di seguito che la più grande distanza di interesse sarebbe probabilmente 4-5. Naturalmente, la mia soluzione bitset diventa più lenta per distanze più grandi, anche più lente della ricerca lineare (per la distanza 32, passerebbe attraverso 232 numeri). Ma per la distanza 9 conduce ancora facilmente.
Ho anche modificato i test di Dietrich. Ognuno dei risultati di cui sopra è per consentire all'algoritmo di risolvere almeno tre domande e quante più domande possibile in circa 15 secondi (faccio round con 1, 2, 4, 8, 16, ecc. passato in totale). È abbastanza stabile, ottengo anche numeri simili per solo 1 secondo.
La mia CPU è un i7-6700. Il mio codice (basato su Dietrich) è qui (Ignora la documentazione almeno lì per ora, non sono sicuro di cosa fare al riguardo, ma il tree.c contiene tutto il codice e il mio test.bat mostra come ho compilato e corretto (ho usato le bandiere di Dietrich Makefile)). Scorciatoia alla mia soluzione.
Un avvertimento: i miei risultati di query contengono numeri solo una volta, quindi se l'elenco di input contiene numeri duplicati, che può o non può essere desiderato. Nel caso dell'autore di Eric, non c'erano duplicati (vedi commento sotto). In ogni caso, questa soluzione potrebbe essere buona per le persone che non hanno duplicati nell'input o non vogliono o necessitano di duplicati nei risultati della query (penso che sia probabile che i risultati della query puri siano solo un mezzo per un fine e quindi Qualche altro codice trasforma i numeri in qualcos'altro, ad esempio una mappa che mappa un numero in un elenco di file il cui hash è quel numero).
Un approccio comune (almeno comune a me) è quello di dividere la tua stringa di bit in diversi pezzi e interrogare su questi pezzi per una corrispondenza esatta come fase pre-filtro. Se lavori con i file, crei tanti file che hai blocchi (ad es. 4 qui) con ogni pezzo permutato davanti e quindi ordina i file. Puoi utilizzare una ricerca binaria e puoi persino espandere la ricerca sopra e sotto un pezzo corrispondente per il bonus.
È quindi possibile eseguire un calcolo della distanza di keting in bit sui risultati restituiti che dovrebbe essere solo un sottoinsieme più piccolo del set di dati complessivo. Questo può essere fatto utilizzando file di dati o tabelle SQL.
Quindi per ricapitolare: supponiamo che tu abbia un sacco di stringhe a 32 bit in un DB o file e che vuoi trovare ogni hash che si trovano a una distanza di martellare a 3 bit o meno della tua stringa bit "query":
Crea una tabella con quattro colonne: ognuna conterrà una fetta di 8 bit (come stringa o int) degli hash a 32 bit, islice da 1 a 4. o se si utilizzano file, creare quattro file, ognuno è una permutazione delle sezioni un "islice" nella parte anteriore di ogni "riga"
Tagliare la stringa di bit di query allo stesso modo in QSLICE da 1 a 4.
interrogare questo tavolo in modo tale che uno di
qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Questo ti dà ogni stringa che si trovano entro 7 bit (8 - 1) della stringa di query. Se si utilizza un file, eseguire una ricerca binaria in ciascuno dei quattro file permutati per gli stessi risultati.Per ogni stringa di bit restituita, calcola l'esatta distanza di marcia con la tua stringa di bit di query (ricostruendo le stringhe bit lato indice dalle quattro sezioni dal DB o da un file perminato)
Il numero di operazioni nel passaggio 4 dovrebbe essere molto inferiore a un calcolo di martellare a coppie a coppie dell'intero tavolo ed è molto efficiente in pratica. Inoltre, è facile ranciare i file in file più piccoli necessari per una maggiore velocità usando il parallelismo.
Ora, naturalmente, nel tuo caso, stai cercando un tipo di se stesso, che sono tutti i valori che si trovano a una certa distanza l'uno dall'altro. Lo stesso approccio funziona ancora IMHO, anche se dovrai espanderti su e giù da un punto di partenza per le permutazioni (usando file o elenchi) che condividono il blocco iniziale e calcolano la distanza di martello per il cluster risultante.
Se si esegue in memoria anziché in file, il set di dati a stringhe da 32 bit da 100 m sarebbe nell'intervallo di 4 GB. Quindi le quattro liste permutate potrebbero aver bisogno di circa 16 GB+ di RAM. Anche se ho risultati eccellenti con file mappati di memoria e devo meno RAM per set di dati di dimensioni simili.
Sono disponibili implementazioni open source. Il meglio nello spazio è IMHO quello fatto per Simhash di Moz, C ++ ma progettato per stringhe da 64 bit e non 32 bit.
Questo approccio a distanza felice limitato è stato descritto per la prima volta da AFAIK Moses Charikar Nel suo seminale "Simhash" carta e il corrispondente Google brevetto:
- Ricerca approssimativa del vicino più vicino nello spazio del margine
[...]
Dati vettori di bit costituiti da bit D ciascuno, scegliamo permutazioni casuali n = O (n 1/(1+)) dei bit. Per ogni permutazione casuale σ, manteniamo un ordine ordinato o σ dei vettori di bit, in ordine lessicografico dei bit permutati da σ. Dato un vettore bit di query Q, troviamo il vicino approssimativo più vicino facendo quanto segue:
Per ogni permutazione σ, eseguiamo una ricerca binaria su O σ per individuare i vettori a due bit più vicini a Q (nell'ordine lessicografico ottenuto da bit permutati da σ). Ora cerchiamo in ciascuno degli ordini ordinati o σ che esaminano gli elementi sopra e sotto la posizione restituita dalla ricerca binaria in ordine della lunghezza del prefisso più lungo che corrisponde q.
Monika Henziger ampliato su questo nel suo documento "Trovare pagine Web quasi duplicate: una valutazione su larga scala degli algoritmi":
3.3 I risultati per l'algoritmo C
Abbiamo partizionato la stringa di bit di ogni pagina in 12 pezzi a 4 byte non sovrapposti, creando 20B di pezzi e calcolato la cimelia C di tutte le pagine che avevano almeno un pezzo in comune. Questo approccio è garantito per trovare tutte le coppie di pagine con differenza fino a 11, cioè, c-somiglianza 373, ma potrebbe perderne alcune per differenze maggiori.
Questo è anche spiegato nel documento Rilevare quasi duplicati per la strisciamento web Di Gurmeet Singh Manku, Arvind Jain e Anish Das Sarma:
- Il problema della distanza di Hamming
Definizione: data una raccolta di impronte digitali F -bit e un'impronta digitale di query f, identificare se un'impronta digitale esistente differisce da F in al massimo K bit. (Nella versione in modalità batch del problema sopra, abbiamo una serie di impronte digitali di query invece di una singola impronta digitale)
[...]
Intuizione: considera una tabella ordinata di impronte digitali veramente casuali 2 df -bit. Concentrati solo sui bit D più significativi nel tavolo. Un elenco di questi numeri D-BIT equivale a "quasi un contatore", nel senso che (a) esistono parecchie combinazioni di 2 d-bit e (b) pochissime combinazioni D-BIT sono duplicate. D'altra parte, i bit F - D meno significativi sono "quasi casuali".
Ora scegli D tale che | D - D | è un piccolo intero. Poiché la tabella è ordinata, una singola sonda è sufficiente per identificare tutte le impronte digitali che corrispondono a f-posizioni più significative. Dal momento che | D - D | è piccolo, il numero di tali corrispondenze dovrebbe anche essere piccolo. Per ogni impronta digitale corrispondente, possiamo facilmente capire se differisce da F nella maggior parte delle posizioni di bit K o meno (queste differenze sarebbero naturalmente limitate alle posizioni bit meno significative).
La procedura sopra descritta ci aiuta a individuare un'impronta digitale esistente che differisce dalle posizioni di bit F, che sono tutte limitate per essere tra i bit F-D di F. Questo si occupa di un discreto numero di casi. Per coprire tutti i casi, è sufficiente costruire un piccolo numero di tabelle ordinate aggiuntive, come formalmente indicato nella sezione successiva.
Nota: ho pubblicato una risposta simile a un Domanda di sola DB correlata
È possibile pre-computare ogni possibile variazione dell'elenco originale nella distanza di martello specificata e conservarlo in un filtro Bloom. Questo ti dà un veloce "no" ma non necessariamente una risposta chiara su "Sì".
Per sì, memorizza un elenco di tutti i valori originali associati a ciascuna posizione nel filtro Bloom e passarli attraverso uno alla volta. Ottimizza le dimensioni del filtro Bloom per compromessi di velocità / memoria.
Non sono sicuro che tutto funzioni esattamente, ma sembra un buon approccio se hai la RAM di runtime da bruciare e sei disposto a trascorrere molto tempo nella pre-computazione.
Che ne dici di ordinare l'elenco e quindi effettuare una ricerca binaria in quell'elenco ordinato sui diversi valori possibili nella distanza di martellare?
Un possibile approccio per risolvere questo problema è l'utilizzo di un Struttura dati disgiunta. L'idea sono i membri di unione dell'elenco con distanza di martello <= K nello stesso set. Ecco lo schema dell'algoritmo:
Per ciascuno Membro dell'elenco Calcola ogni possibile valore con distanza di martello <= k. Per k = 1, ci sono 32 valori (per valori a 32 bit). Per k = 2, 32 + 32*31/2 valori.
Per ciascuno calcolato valore, test se è nell'input originale. È possibile utilizzare un array con dimensioni 2^32 o una mappa hash per fare questo controllo.
Se la valore è nell'input originale, fai un'operazione "sindacale" con il Membro dell'elenco.
- Mantenere il numero di operazioni sindacali eseguite in una variabile.
Si avvia l'algoritmo con n set disgiunti (dove n è il numero di elementi nell'ingresso). Ogni volta che si esegue un'operazione sindacale, si diminuisce di 1 il numero di set disgiunti. Quando l'algoritmo termina, la struttura dei dati disgiunta avrà tutti i valori con la distanza di keting <= k raggruppata in set disgiunti. Questa struttura dati disgiunta può essere calcolata in quasi tempo lineare.
