Struttura dei dati di indicizzazione rapida per il recupero del superset

Question

Struttura dei dati di indicizzazione rapida per il recupero del superset

#1 da (4 voti)
#2 da (0 voti)

5

Mi viene fornito un set di set:

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

Mi piacerebbe avere una struttura dati per indicizzare quei set in modo tale che la seguente "ricerca" sia eseguita velocemente: trova tutti i superset di un determinato set.

Ad esempio, dato l'insieme {a, c} la struttura restituirebbe

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

ma non {a, b}.

Qualche suggerimento? Questo può essere fatto con una struttura dati intelligente simile a un trie che memorizza i set dopo un corretto ordinamento?

Questa struttura di dati verrà interrogata molto. Quindi, sto cercando una struttura che potrebbe essere costosa in costruzione ma piuttosto veloce da interrogare.

AGGIORNAMENTO: Ho finalmente usato un prefisso Trie come descritto nel documento "Un nuovo metodo per indicizzare e set di query", di Jorg Hoffmann e Jana Koehler.

data-structures indexing trie

posta Asterios 12.11.2012 - 11:40

fonte

2 risposte

Leggi altre domande sui tag data-structures indexing trie

Progettazione del livello di servizio La distribuzione di asset non GPLd con un'applicazione GPL viola la licenza?

score 4 · Answer 1

Sembra che tu stia cercando un algoritmo di recupero informazioni standard. Invece di darti la risposta (che dipende da fattori quali frequenza e cardinalità dei termini e numero di documenti, il tipo di domande richieste), ti inoltro all'eccellente trattato introduttivo sull'argomento chiamato: Introduzione al recupero delle informazioni: < a href="http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html"> link

Probabilmente il capitolo "Costruzione indice" contiene un algoritmo adatto alle tue esigenze.

score 0 · Answer 2

Se i diversi tipi di elementi sono limitati, potresti costruire una tabella di bandiere. Ogni set è una matrice di bool in cui ogni posizione rappresenta una parola. Le parole sono mantenute in una lista, dove il loro indice è uguale all'indice del bool che le rappresenta. Per trovare i superset, si confrontano i valori delle bandiere; per essere un superset, ogni posizione con valore True nel sottoinsieme deve contenere True nel set candidato. Tutto questo può essere fatto in O (n), il che non è male secondo me.

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'])]

Sii ovviamente attento a non costruire il tuo motore SQL. In effetti potresti usarne uno per questo modello.

Inoltre, troverai utile link - l'ho appena trovato.