Encontrar un subconjunto de un conjunto en una colección de conjuntos

¿Qué estructuras de datos recomendaría que representen una colección de subconjuntos de y admitan las siguientes operaciones? $\{1, \dots, n\}$

: inserta en la colección. $insert(S)$ $S$
: devuelve verdadero si existe en la colección tal que , falso en caso contrario. $query(S)$ $S'$ $S' \subset S$

Mi criterio principal sería la eficiencia práctica del tiempo.

ds.data-structures Caleb Poucher
fuente

La recomendación requiere criterios. ¿Cuáles son tus criterios? Por ejemplo, ¿simplicidad, espacio o tiempo? Cuanto más específico sea, más probable será que obtenga respuestas que le sean útiles.

Tsuyoshi Ito

Tienes razón, gracias por señalarlo. Mi criterio principal sería la eficiencia práctica del tiempo.

Caleb Poucher

¿Sabes cuántas inserciones harás en relación con la cantidad de consultas que harás? Es posible construir una enorme estructura de datos (tamaño exponencial en

) que le permitirá consultar un conjunto

en tiempo

. Por otro lado, si

es el número total de subconjuntos insertados, puede hacer una búsqueda ingenua sin almacenamiento adicional en el tiempo

. Todo lo demás, creo, será una compensación.

n

$n$

S

$S$

O (n)

$O(n)$

m

$m$

O (n m)

$O(nm)$

James King

100

$100$

{0, 1}^{n}

$\{0,1\}^n$

n

$n$

n

$n$

m

$m$

n

$n$

m

$m$

Respuestas:

Su problema me parece mucho a la recuperación de información (IR). Allí tiene una colección de conjuntos de palabras (también conocidos como documentos) y desea encontrar no solo la existencia, sino todos los conjuntos / documentos que satisfacen la condición de consulta.

Dado que los elementos establecidos son números, puede aprovechar la estructura aparente, por lo que un índice de firma sería de gran utilidad.

Recomendaría echar un vistazo a los documentos IR, especialmente relacionados con las estructuras del diccionario, como los árboles, pero tenga en cuenta que el espacio suele ser un problema para esos sistemas, mientras que podría no ser un problema para su caso.

chazisop
fuente

Buen punto, esto es de hecho muy similar a la búsqueda de términos en documentos, y la forma más común de resolver esto es usar un llamado archivo invertido , que funciona como el índice de un libro. Usted busca cada término en su consulta en el archivo invertido y obtiene una lista / conjunto de documentos que contienen ese término. Luego intersecta estas listas para obtener el resultado. (Se podría, por ejemplo, utilizar un ID de elemento mapeo de la tabla hash para listas ordenadas de ID de conjuntos; la clasificación ayuda a la intersección.)

Magnus Lie Hetland

Podrías usar un árbol de búsqueda. No es "estándar", como se usa para los universos ordenados (números reales, cadenas ...) sino un tipo más general, como los insinuados por el proyecto GiST . Hay árboles de búsqueda para consultas espaciales, así como las basadas en axiomas métricos , para indexar espacios métricos (distancia). La idea general (de la cual el enfoque orientado a intervalos "menor que / mayor que" de los árboles de búsqueda ordenados ordinarios es una especialización) es descomponer el conjunto de datos en subconjuntos, generalmente jerárquicamente. Esta jerarquía de subconjuntos está (obviamente) representada por un árbol, donde los hijos de cada nodo representan subconjuntos, y cada nodo tiene alguna forma de predicado., que le permite verificar si existe una superposición entre el conjunto (conceptual) de objetos relevantes para su consulta y los que se encuentran en ese subárbol (es decir, subconjunto).

Por ejemplo, para un árbol espacial en el plano euclidiano, cada objeto podría ser un punto, y los predicados podrían ser rectángulos delimitadores , que contienen todos los puntos encontrados en ese nodo o debajo de él. Si una consulta es un rectángulo (y desea encontrar todos los puntos en ese rectángulo), puede eliminar recursivamente los subárboles cuyos rectángulos delimitadores no se superponen con su consulta.

En su caso, podría construir un árbol donde cada nodo contenga una estructura de conjunto que le permita detectar si su consulta es un subconjunto. Si no, ese subárbol completo puede eliminarse, ya que su consulta nunca podría ser un subconjunto de ninguno de los nodos secundarios (y ciertamente no las hojas, que probablemente representarían los datos verdaderos).

A diferencia de los árboles de búsqueda ordinarios, aquí no hay una garantía de tiempo de búsqueda en general: probablemente visitará varias ramas, por lo que incluso si tiene un árbol perfectamente equilibrado, probablemente tendrá un tiempo de ejecución superlogarítmico. Este es un enfoque más heurístico, pero podría ser efectivo aún.

Lo que necesita, para construir este árbol, sería alguna forma de método de agrupamiento jerárquico que se ajuste a sus datos. El proyecto GiST en realidad tiene un árbol muy parecido a lo que necesita, con una implementación en C (aunque verifica si la consulta se superpone, no si es un subconjunto; debería ser fácil de modificar). Sin embargo, el árbol equilibrado estilo Gi-Tree basado en disco de GiST podría ser excesivo. Probablemente solo desee agrupar conjuntos similares, jerárquicamente, y podría hacerlo utilizando cualquier algoritmo de agrupación estándar, utilizando algo como la distancia de Hamming (o algo más elegante). Cuanto más parecidos sean los nodos hermanos, "más estricto" será el predicado delimitador del padre (es decir, el conjunto que representa su unión) y, por lo tanto, más eficiente será su búsqueda.

En resumen, mi sugerencia es:

Representa tus conjuntos para que puedas verificar la superposición con la consulta (vectores de bits, tablas hash).
Agrupe sus conjuntos jerárquicamente, utilizando una distancia adecuada (por ejemplo, Hamming) y un algoritmo estándar.
En cada nodo interno, almacene la unión de los conjuntos de nodos secundarios.
Durante la búsqueda, recorra recursivamente, podando / ignorando subárboles cuyas raíces tienen conjuntos que no se superponen con su consulta.

Si necesita que el árbol sea dinámico, también hay muchas formas de hacerlo. Por ejemplo, podría atravesar recursivamente el árbol, encontrar la ubicación que mejor se adapte (pasando por los nodos con la mayor superposición / distancia de Hamming más pequeña), actualizando las uniones (predicados delimitadores) a medida que avanza. Las eliminaciones son un poco más difíciles, tal vez; simplemente puede marcar los objetos que faltan y luego reconstruir los subárboles (o la estructura completa) cuando el número de objetos marcados alcanza un cierto umbral.

Si esto funciona bien para su aplicación podría ser difícil de decir a priori, pero debería ser fácil de verificar experimentalmente. Además, hay mucho espacio para ajustar.

Magnus Lie Hetland
fuente