Localizando um subconjunto de um conjunto em uma coleção de conjuntos

Quais estruturas de dados você recomendaria que representam uma coleção de subconjuntos de e suportam as seguintes operações? $\{1, \dots, n\}$

: inserções na colecção. $insert(S)$ $S$
: retorna true se existir na coleção, de modo que , caso contrário, false. $query(S)$ $S'$ $S' \subset S$

Meu critério principal seria a eficiência prática do tempo.

ds.data-structures Caleb Poucher
fonte

A recomendação requer critérios. Quais são os seus critérios? Por exemplo, simplicidade, espaço ou tempo? Quanto mais específico você for, maior será a probabilidade de obter respostas úteis.

Tsuyoshi Ito 21/07

Você está certo, obrigado por apontar. Meu critério principal seria a eficiência prática do tempo.

Caleb Poucher

Você sabe quantas inserções você fará em relação ao número de consultas que fará? É possível construir uma enorme estrutura de dados (tamanho exponencial em

) que permitirá consultar um conjunto

. Por outro lado, se

for o número total de subconjuntos inseridos, você poderá fazer uma pesquisa ingênua sem armazenamento adicional em

. Tudo no meio, eu acho, será uma troca.

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$

Respostas:

Seu problema me parece muito com Recuperação de Informação (RI). Lá você tem uma coleção de conjuntos de palavras (também conhecidos como documentos) e deseja encontrar não apenas a existência, mas todos os conjuntos / documentos que atendem à condição de consulta.

Como os elementos do conjunto são números, você pode tirar proveito da estrutura aparente, portanto, um índice de assinatura seria muito útil.

Eu recomendaria dar uma olhada nos documentos de RI, especialmente relacionados a estruturas de dicionário, como árvores, mas observe que o espaço geralmente é um problema para esses sistemas, embora possa não ser um problema para o seu caso.

chazisop
fonte

Bom, isso é realmente muito semelhante à pesquisa de termos em documentos, e a maneira mais comum de resolver isso é usar o chamado arquivo invertido , que funciona como o índice de um livro. Você consulta cada termo em sua consulta no arquivo invertido e obtém uma lista / conjunto de documentos que contêm esse termo. Em seguida, você cruza essas listas para obter o resultado. (Você poderia, por exemplo, usar um item de tabela de mapeamento de hash IDs de listas ordenadas de IDs definidos; a ordenação contribui com o cruzamento.)

Magnus Lie Hetland

Você pode usar uma árvore de pesquisa. Não é um "padrão", como é usado para universos ordenados (números reais, seqüências de caracteres ...), mas um tipo mais geral, como os sugeridos pelo projeto GiST . Existem árvores de pesquisa para consultas espaciais, bem como aquelas baseadas nos axiomas da métrica , para indexação de espaços métricos (distância). A idéia geral (da qual a abordagem orientada a intervalos "menor que / maior que", das árvores de pesquisa ordinárias e ordinárias é uma especialização) é decompor o conjunto de dados em subconjuntos, geralmente hierarquicamente. Essa hierarquia de subconjuntos é (obviamente) representada por uma árvore, na qual os filhos de cada nó representam subconjuntos e cada nó tem alguma forma de predicado, que permite verificar se há uma sobreposição entre o conjunto (conceitual) de objetos relevantes para sua consulta e os encontrados nessa subárvore (ou seja, subconjunto).

Por exemplo, para uma árvore espacial no plano euclidiano, cada objeto pode ser um ponto e os predicados podem ser retângulos delimitadores , contendo todos os pontos encontrados nesse nó ou abaixo dele. Se uma consulta for um retângulo (e você desejar encontrar todos os pontos nesse retângulo), poderá eliminar recursivamente subárvores cujos retângulos delimitadores não se sobrepõem à sua consulta.

No seu caso, você pode criar uma árvore em que cada nó contenha alguma estrutura definida que permita detectar se sua consulta é um subconjunto. Caso contrário, essa subárvore inteira poderá ser eliminada, pois sua consulta nunca poderá ser um subconjunto de nenhum dos nós filhos (e certamente não as folhas, o que provavelmente representaria os dados verdadeiros).

Ao contrário das árvores de pesquisa comuns, geralmente não há garantia de tempo de pesquisa aqui - você provavelmente visitará vários ramos, portanto, mesmo que tenha uma árvore perfeitamente equilibrada, provavelmente terá um tempo de execução superlogarítmico. Essa é uma abordagem mais heurística, mas pode ser eficaz mesmo assim.

O que você precisa, para construir essa árvore, seria alguma forma de método hierárquico de cluster que se ajustasse aos seus dados. O projeto GiST, na verdade, tem uma árvore muito parecida com o que você precisa, com uma implementação C (embora verifique se a consulta se sobrepõe, não se é um subconjunto; deve ser fácil de modificar). Porém, a árvore balanceada do GiST, baseada em disco e no estilo de árvore B, pode ser um exagero. Você provavelmente só deseja agrupar conjuntos semelhantes, hierarquicamente, e pode fazer isso usando qualquer algoritmo de cluster disponível no mercado, usando algo como distância de Hamming (ou algo mais sofisticado). Quanto mais nós irmãos semelhantes, mais "apertado" será o predicado delimitador do pai (ou seja, o conjunto que representa sua união) - e, portanto, mais eficiente será sua pesquisa.

Para resumir, minha sugestão é:

Represente seus conjuntos para que você possa verificar a sobreposição com a consulta (vetores de bits, tabelas de hash).
Agrupe seus conjuntos hierarquicamente, usando uma distância adequada (por exemplo, Hamming) e um algoritmo de prateleira.
Em cada nó interno, armazene a união dos conjuntos de nós filhos.
Durante a pesquisa, percorra recursivamente, podando / ignorando subárvores cujas raízes têm conjuntos que não se sobrepõem à sua consulta.

Se você precisa que a árvore seja dinâmica, há várias maneiras de fazer isso também. Por exemplo, você pode percorrer recursivamente a árvore, encontrando o local que melhor se encaixa (passando por nós com a maior sobreposição / menor distância de Hamming), atualizando as uniões (predicados delimitadores) à medida que avança. As exclusões são um pouco mais complicadas, talvez; basta marcar os objetos como ausentes e reconstruir subárvores (ou toda a estrutura) quando o número de objetos marcados atingir um determinado limite.

Se isso funciona bem para o seu aplicativo, pode ser difícil dizer a priori, mas deve ser fácil verificar experimentalmente. Além disso, há muito espaço para ajustes.

Magnus Lie Hetland
fonte