¿Representa los conjuntos de enteros dispersos?

Question

¿Cuál es una buena manera de representar un conjunto disperso de enteros (realmente direcciones de memoria C) de una manera compacta y rápida. Ya sé sobre las cosas obvias como los vectores de bits y la codificación de longitud de ejecución. pero quiero algo mucho más compacto que una palabra por conjunto de elementos. Necesito agregar y eliminar elementos y probar la membresía. No necesito otras operaciones de conjunto, como la unión.

Leí acerca de una de esas bibliotecas hace muchos años, pero desde entonces he olvidado su nombre. Creo que fue lanzado como fuente abierta por HP y tenía un nombre de mujer.

Answer 1

Usted se está refiriendo a una matriz judy. Fue un proyecto de HP. Creo que se usan en ruby ​​y están disponibles en c. Estructura de datos muy interesante. Haciendo uso del hecho de que las asignaciones están (al menos) alineadas con palabras, teniendo estructuras separadas para rangos densos y dispersos.

http://judy.sourceforge.net/index.html

Answer 2

Si todo lo que necesita es inserción, eliminación y prueba de membresía, entonces una tabla hash le conviene. Puedes encontrar algunas buenas funciones hash para hash enteros de 32 bits here.

Answer 3

Si desea que la estructura sea más pequeña que el conjunto de datos, probablemente debería considerar algún tipo de arreglo de árbol. Realice cada nivel de 4 maneras en que la clave del árbol se separa de 2 bits comenzando en el extremo superior y puede compactarse bastante bien (si los punteros tienen algún grado de localidad espacial). El truco sería codificarlo lo suficientemente compacto (índices en matrices de nodos, un árbol mapeado en una matriz?).

Answer 4

Una estructura de datos muy compacta sería un filtro de floración, quizás un filtro de recuento de floración para admitir eliminaciones.

http://en.wikipedia.org/wiki/Bloom_filter

El filtro de Bloom, concebido por Burton H. Bloom en 1970, es una estructura de datos probabilística eficiente con el espacio que se utiliza para probar si un elemento es un miembro de un conjunto. Los falsos positivos son posibles, pero los falsos negativos no lo son. Se pueden agregar elementos al conjunto, pero no se eliminan (aunque esto se puede solucionar con un filtro de conteo)