Implementazione efficiente di un filtro Bloom in C?

Questa domanda è stata posta in precedenza ma a quell'ora non c'era una risposta, quindi ho deciso di richiederlo.Implementazione efficiente di un filtro Bloom in C?

Ho bisogno di un'implementazione efficiente di un filtro Bloom in C (non C++). Se non è disponibile una cosa del genere, non mi dispiacerebbe implementarne una, se avessi dato qualche buon riferimento in modo che non mi ci volesse molto del mio tempo.

Desidero utilizzare questa struttura dati per inserti e test in un rapporto (1: 20k), quindi in primo luogo è un test intensivo. I dati da testare sono interi a 64 bit.

fonte

2012-06-13 Aman Deep Gautam

È probabilistico. Se vuoi una risposta esatta, usa Union Trova Disjoint Set. Cerca questo su topcoder, dovrebbe esserci qualche tutorial per questo. – nhahtdh

Se stai scrivendo C, questo non è il tipo di cosa per cui hai bisogno di una biblioteca generale. Dovrebbe contenere meno di 100 righe di codice e impiegare meno tempo per scrivere rispetto all'integrazione di una libreria di terze parti. Basta leggere la tua descrizione preferita dell'algoritmo su Wikipedia o simili .. –

@R scrivendo ci vorrà meno tempo che io conosca ma in modo efficiente scrivendolo in modo che si riduca bene è un problema.Devo testare l'appartenenza ai dati nell'ordine di 10^7 e rendere questa query più veloce della query count (*) sul risultato di un equi join. Non posso permettermi di perdere nemmeno un ms nella mia implementazione –

cromo ha uno in C++

github link

fonte

2012-06-13 02:40:15 eqzx

Man, hanno davvero bisogno di includere il copyright di Bob Jenkins per il loro uso della sua funzione di hashing (di dominio pubblico) ... – tbert

Per non fare troppo auto-promozione, ma ho scritto un plugin per il Geany editor/IDE che filtra righe di testo duplicati, si utilizza un filtro di Bloom.

L'implementazione è in C, e puoi trovarla right here on GitHub. È GPL v3, quindi a seconda delle tue esigenze è possibile che tu possa o meno essere in grado di usarlo.

Alcune note sulla mia realizzazione:

è progettato per filtrare le stringhe, e non fa astratto il tipo di chiave. Ciò significa che dovrai modificare la gestione delle chiavi in base alle tue esigenze.
Supporta semantica non caratteristica, è possibile utilizzarlo per test di esistenza totalmente non probabilistici, se lo si desidera (vedere il puntatore della funzione di richiamata utilizzato da bloom_filter_new()). Basta passare NULL per ottenere un filtro "puro".
La funzione di hash della stringa è MurmurHash2 di Austin Appleby. Ho valutato MurmurHash3 più attuale, ma la versione 2 era più facile da lavorare.
Per adattarsi al sistema eco Geany, questo codice utilizza tutti i tipi GLib.

Non è stato ottimizzato per le prestazioni, ma dovrebbe essere a posto. Apprezzerei qualsiasi feedback che potresti avere dopo averlo provato, ovviamente!

fonte

2012-06-13 06:59:12 unwind

Ehi, grazie può essere davvero molto utile. farò un tentativo e parlartene. –

puoi suggerire alcune altre librerie per alte prestazioni diverse da glib –

puoi suggerire un motivo particolare dell'utilizzo della libreria glib, fatta eccezione per la possibilità di rendere il codice portatile. –

Ho una libreria a se stante pianura C qui che può essere utile: https://github.com/jvirkki/libbloom

fonte

2013-02-13 08:50:33

quali vantaggi? – bsiamionau

+11

+1 per licenza BSD. –

So che questa è una vecchia questione, ma per riferimento, qui ci sono alcuni risultati di ricerca github.

Una semplice ricerca su github per 'bloomfilter' produce una tonnellata di risultati (per C):

https://github.com/search?q=extension%3Ac+bloomfilter&type=Code&ref=searchresults

Questo è per RIFERIMENTO solo.

fonte

2013-06-02 05:46:44

Implementazione efficiente di un filtro Bloom in C?

risposta

Problemi correlati