Implementación eficiente de un filtro Bloom en C?

Esta pregunta se ha formulado anteriormente, pero no hubo respuesta para ella en ese momento, así que decidí preguntar nuevamente.Implementación eficiente de un filtro Bloom en C?

Necesito una implementación eficiente de un filtro Bloom en C (no C++). Si no hay tal cosa disponible, no me importaría implementar una, si se me proporciona una buena referencia para que no ocupe demasiado tiempo.

Quiero utilizar esta estructura de datos para inserciones y pruebas en una proporción (1: 20k), por lo que principalmente es una prueba intensiva. Los datos que se probarán son enteros de 64 bits.

Fuente

2012-06-13 Aman Deep Gautam

Es probabilístico. Si quiere una respuesta exacta, use Union Find Disjoint Set. Busque esto en el topcoder, debe haber algún tutorial para ello. – nhahtdh

Si está escribiendo C, este no es el tipo de cosas para las que necesita una biblioteca general. Debería tener menos de 100 líneas de código, y debería tomarse menos tiempo para escribir que integrar una biblioteca de terceros. Simplemente lea su descripción favorita del algoritmo en Wikipedia o similar. –

@R escribiendo me tomará menos tiempo que conozco, pero escribirlo de manera eficiente para que escale bien es un problema.Tengo que probar la pertenencia a los datos en el orden de 10^7 y hacer que esta consulta sea más rápida que la consulta de conteo (*) en el resultado de una combinación equi. No puedo permitirme perder ni siquiera un ms en mi implementación –

cromo tiene una en C++

github link

Fuente

2012-06-13 02:40:15 eqzx

Hombre, realmente necesitan incluir el copyright de Bob Jenkins para el uso de su función de hash (de dominio público) ... – tbert

Para no hacer demasiado auto-promoción, pero he escrito un plugin para el Geany editor/IDE que filtra las líneas de texto duplicados, se utiliza un filtro Bloom.

La implementación está en C, y lo puedes encontrar right here on GitHub. Es GPL v3, por lo que dependiendo de sus necesidades exactas, puede o no ser capaz de usarlo.

Algunas notas sobre mi aplicación:

Está diseñado para filtrar las cadenas, y no lo hace resumen el tipo de clave. Esto significa que tendrá que modificar el manejo de las teclas para satisfacer sus necesidades.
Es compatible con la semántica no característica, en realidad puede utilizarlo para pruebas de resistencia totalmente probabilísticas si lo desea (consulte el BloomContains puntero de función de devolución de llamada utilizado por bloom_filter_new()). Simplemente pase NULL para obtener un filtro "puro".
La función hash de cadena es MurmurHash2 por Austin Appleby. Evalué el MurmurHash3 más actual, pero era más fácil trabajar con la versión 2.
Para caber en el sistema ecológico de Geany, este código usa tipos de GLib en todas partes.

No se ha ajustado mucho para el rendimiento, pero debería estar bien. ¡Apreciaría cualquier comentario que pueda tener después de probarlo, por supuesto!

Fuente

2012-06-13 06:59:12 unwind

Oye, gracias, puede ser muy útil. Voy a intentarlo y contarte sobre eso. –

¿Puede sugerir que otras bibliotecas para alto rendimiento que no sean glib –

pueden sugerir algún motivo particular de uso de la biblioteca glib excepto que hace que el código sea portátil? –

que tienen una biblioteca independiente C plano aquí, que pueden ser de utilidad: https://github.com/jvirkki/libbloom

Fuente

2013-02-13 08:50:33

qué ventajas? – bsiamionau

+11

+1 para licencia BSD. –

Sé que esto es una cuestión de edad, sino por referencia, aquí están algunos resultados de búsqueda GitHub.

Una simple búsqueda en github de 'bloomfilter' produce una tonelada de resultados (para C):

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

Esto es para REFERENCIA solamente.

Fuente

2013-06-02 05:46:44

Implementación eficiente de un filtro Bloom en C?

Respuesta

Cuestiones relacionadas