Estructura de datos para la intersección de conjuntos?

21

¿Existe alguna estructura de datos que mantenga una colección de conjuntos (de conjuntos finitos) que respalde las siguientes operaciones? ¿Se apreciará algún tiempo de ejecución sublineal?

  1. Inicia un conjunto vacío.
  2. Agregar un elemento a un conjunto.
  3. Dado dos conjuntos, informe si se cruzan.
Dawei Huang
fuente
1
Esta es una pregunta muy general, porque cualquier estructura de datos puede soportar esas operaciones con dominio finito. Podrías ser un poco más específico ? P.ej. Lo complejidad que necesita, lo que está dispuesto a sacrificar para conseguir operaciones de conjuntos, etc.
Bartosz Przybylski

Respuestas:

13

Si cada conjunto mantiene un registro de qué otros conjuntos existen, y tiene un total de conjuntos, puede convertir fácilmente cualquier estructura de datos para una colección ( por ejemplo , árboles de búsqueda binarios, etc. ) en una donde pueda recuperar Un elemento de la intersección de dos conjuntos en el tiempo .O ( log s )s>0 0O(Iniciar sesións)

  • Cada conjunto debe tener un identificador único de un conjunto totalmente ordenado. Si nombra explícitamente sus conjuntos S1,S2,... entonces el identificador podría ser simplemente el índice.

  • Debe implementar un "registro" de los conjuntos; una estructura de datos que mantiene una colección de todos los conjuntos que ha definido. El registro debe implementarse como una estructura de datos del árbol de búsqueda, para permitir una recuperación fácil ( por ejemplo,  si desea eliminar el conjunto) y un recorrido en tiempo lineal de los conjuntos.

  • Cada conjunto también mantiene un "índice" de cada uno de los otros conjuntos, no una copia de ellos, sino más bien una estructura de datos indexada por las etiquetas de los otros conjuntos. Este índice se utilizará para mantener, para cada conjunto S k , un árbol de búsqueda binario de todos los elementos de S jS k . (Los dos conjuntos S j y S k comparten una copia de ese árbol de búsqueda).SjSkSjSkSjSk

Inicialización

La inicialización de un conjunto consiste en operaciones O ( 1 ) para inicializar el árbol de sus elementos, operaciones O ( s ) a medida que inicializa (copiando del registro) el índice del conjunto T y O ( s log s ) operaciones a medida que recorre el registro para agregar T en los índices de cada uno de los otros conjuntos S j . En el índice de T , creamos árboles de búsqueda que representan T S j = T=O(1)O(s)TO(sIniciar sesións)TSjTTSj=para los otros conjuntos ; copiamos el mismo puntero para el índice de .SjSj

Agregar un elemento a un conjuntoT

Agregar algo de al conjunto toma tiempo como de costumbre, donde. También probamos la membresía de en cada uno de los otros conjuntos , lo que lleva tiempo dondees el tamaño del universo (o del conjunto más grande ) y es el número de conjuntos en el registro. Para cada conjunto S j tal que x S j , inserte también x en el índice del conjunto S jT O ( log n T ) n T = | T | x S 1 , S 2 , O ( log n S 1 + log n S 2 + ) O ( s log n ) , n = | V | S j sXVTO(Iniciar sesiónnorteT)norteT=El |TEl |XS1,S2,...

O(Iniciar sesiónnorteS1+Iniciar sesiónnorteS2+)O(sIniciar sesiónnorte),
norte=El |VEl |SjsSjXSjX . Para cada uno de estos conjuntos S j , esto lleva tiempo O ( log s + log n T ) , buscar S j en el índice de T e insertar x en S jT ; en todos los conjuntos S 1 , S 2 , ... esto lleva tiempo O ( s log s + s log n T ) . Si suponemos que el número de conjuntos SSjTSjO(Iniciar sesións+Iniciar sesiónnorteT)SjTXSjTS1,S2,...O(sIniciar sesións+sIniciar sesiónnorteT) es mucho menor que el tamaño del universo V (es decir, si suponemos que s n ), el tiempo total para la inserción del elemento es entonces O ( s log n ) .SjVsnorteO(sIniciar sesiónnorte)

Si usted no permite duplicados en conjuntos, podemos ahorrar tiempo en el caso de que ya renunciando a la prueba de pertenencia y las inserciones de los otros conjuntos T . La "inserción" en el caso de que x ya esté presente, entonces toma tiempo solo O ( log n T ) .XSTXO(Iniciar sesiónnorteT)

Prueba de intersección

El índice de cada conjunto se mantiene con precisión para permitir una evaluación rápida de si dos conjuntos y S k se cruzan o no . Para un conjunto S j , simplemente comprobando su índice para el conjunto S k , no solo podemos determinar en el tiempo O ( log s ) si S j intersecta o no S k , sino que también podemos recuperar un árbol binario que contiene todo el conjunto S jS k .SjSkSjSkO(Iniciar sesións)SjSkSjSk

Eliminación de elementos

Para eliminar un elemento de un conjunto T , lo eliminamos no solo del árbol de búsqueda de T , sino de cada una de las intersecciones S jT para los conjuntos S j en su índice. Esto lleva tiempo O ( s log n T ) , donde n T = | T | .XTTSjTSjO(sIniciar sesiónnorteT)norteT=El |TEl |

Establecer eliminación

Debido a la sobrecarga de buscar en el registro, si tiene muchos conjuntos, puede ser conveniente eliminarlos una vez que ya no sean necesarios. Al recorrer todo el registro, podemos eliminar del índice de todos los demás conjuntos S j en el tiempo O ( s n T ) , dominado por el costo de eliminar el árbol de búsqueda que representa S jT para cada uno de los otros conjuntos S j , donde n T = | T | .SSjO(snorteT)SjTSjnorteT=El |TEl |

Observaciones

Si solo espera implementar un número constante de conjuntos, los tiempos de ejecución anteriores se reducen a:

  • inicialización: O(1)

  • inserción de elemento: O(Iniciar sesiónnorte)

  • prueba de intersección (y recuperación de la intersección): O(1)

  • eliminación de elementos: O(Iniciar sesiónnorteT)

  • borrar conjunto: O(norteS)

donde es el tamaño del conjunto más grande en el registro yn T = | T | para el conjunto T en el que está operando.nortenorteT=El |TEl |T

Si espera tener conjuntos , donde V es su universo, es posible que necesite una estructura de datos diferente si desea que estas operaciones operen en tiempo sub-lineal. Sin embargo, si tiene pares de conjuntos cuya intersección sabe que nunca probará, es posible que pueda reducir el tamaño del índice de los conjuntos (al no incluir ningún conjunto cuya intersección probará) o usar más de un registro ( uno para cada colección de conjuntos cuya intersección puede probar). De hecho, un registro solo es útil si desea un control centralizado para garantizar que cada par de conjuntos tenga un registro entre sí en el índice: puede ser práctico en algunos casos, en la inicialización de un conjunto S , simplemente registrarO(El |VEl |)VSad hoc cada nuevo conjunto en los índices de los otros conjuntos cuya intersección con S le interesa.TS

Niel de Beaudrap
fuente
6

Existen estructuras de datos que le permiten hacer esto en menos tiempo lineal, incluso para las entradas en el peor de los casos. Consulte http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (y las referencias de los documentos allí).

Si sus dos conjuntos S y T tienen una intersección grande y tiene un diccionario para S, buscar elementos de T en orden aleatorio debería darle rápidamente un elemento común. El caso más difícil es cuando el tamaño de la intersección es 0 o 1.

Rasmus Pagh
fuente
3

Por lo general, el lenguaje de programación que elija admitirá una estructura de datos con elementos únicos. En general, hay tres enfoques populares: árboles, hashes y máscaras de bits. Los elementos de árbol deben ser comparables, los elementos de hash deben ser hashable y los elementos de máscara de bits deben tener alguna forma de conversión a enteros.

Un conjunto de árbol admitirá la inserción en O (log n) y las pruebas de intersección en el peor caso O (n log n).

Un conjunto de hash admitirá la inserción en Amortized O (1 * h) donde 'h' es el tiempo de ejecución del algoritmo de hash y la prueba de intersección en el peor caso O (n).

Los conjuntos de máscaras de bits generalmente no se usan como conjuntos de árbol y hash.

Karl Damgaard Asmussen
fuente
2
Esta sería una respuesta de Stack Overflow decente , pero aquí nos gustaría obtener algunos detalles sobre cómo y por qué funciona.
Raphael
3

Si su caso permite respuestas falsas positivas, usaría Bloom Filter con una sola función hash.

Puede implementarlo de la siguiente manera:

Iniciar un conjunto vacío

  • Bnn

Agregar un elemento a un conjunto.

  • B[hash(element)]=1

Dados dos conjuntos (B1, B2), informe si se cruzan.

  • B1 AND B2 = 0

Complejidad

  • nO(1)
Grisha Weintraub
fuente