Configura rapidamente a estrutura de dados de indexação para recuperação de superconjunto

5

Eu recebo um conjunto de conjuntos:

{{a,b}, {a,b,c}, {a,c}, {a,c,f}}

Eu gostaria de ter uma estrutura de dados para indexar esses conjuntos de modo que a "pesquisa" a seguir seja executada rapidamente: encontre todos os superconjuntos de um determinado conjunto.

Por exemplo, dado o conjunto {a, c} a estrutura retornaria

{{a,b,c}, {a,c,f}, {a,c}}

mas não {a, b}.

Alguma sugestão? Isso poderia ser feito com uma estrutura de dados inteligente semelhante a um trio armazenando conjuntos após uma classificação adequada?

Essa estrutura de dados será muito questionada. Assim, estou procurando uma estrutura que possa ser cara na criação, mas rápida na consulta.

UPDATE: Eu finalmente usei um prefixo Trie como descrito no artigo "Um novo método para indexar e consultar conjuntos", por Jorg Hoffmann e Jana Koehler.

    
por Asterios 12.11.2012 / 11:40
fonte

2 respostas

4

Parece que você está procurando por um algoritmo padrão de recuperação de informações. Em vez de dar-lhe a resposta (que depende de fatores como frequência e cardinalidade dos termos e do número de documentos, o tipo de perguntas feitas), eu o encaminharei ao excelente tratado introdutório sobre o tema chamado: Introdução à Recuperação da Informação: < href="http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html"> link

Provavelmente, o capítulo 'Construção do índice' contém um algoritmo adequado às suas necessidades.

    
por 12.11.2012 / 14:45
fonte
0

Se os diferentes tipos de elementos forem limitados, você poderá criar uma tabela de sinalizadores. Cada conjunto é uma matriz de bools onde cada posição representa uma palavra. As palavras são mantidas em uma lista, onde seu índice é igual ao índice do bool que as representa. Para encontrar os supersets, você compara os valores dos flags; para ser um superconjunto, todas as posições com valor True no subconjunto devem conter True no conjunto de candidatos. Tudo isso pode ser feito em O (n), o que não é ruim na minha opinião.

Python:

WORDS = (
    'a',
    'b',
    'c',
    'f',
)

def values_to_words(s):
    return set(WORDS[i] for i, v in enumerate(s) if v)

def words_to_values(s):
    return tuple(True if w in s else False for i, w in enumerate(WORDS)) # Unoptimized

SETS = tuple(words_to_values(s) for s in (
    ('a','b',),
    ('a','b','c',),
    ('a','c',),
    ('a','c','f',),
))

def get_supersets(q):
    values = words_to_values(q)
    is_superset = lambda s: all(v1 or not v2 for v1, v2 in zip(s, values))
    return (values_to_words(s) for s in SETS if is_superset(s))

print list(get_supersets(('a','c',)))
# [set(['a', 'c', 'b']), set(['a', 'c']), set(['a', 'c', 'f'])]

Tenha cuidado para não criar seu próprio mecanismo SQL. Você poderia, de fato, usar um para esse padrão.

Além disso, você encontrará o link útil - acabei de encontrá-lo.

    
por 23.05.2017 / 14:40
fonte