indicizzazione: termini ordine lessicografico Flashcards
(30 cards)
Che informazioni devo indicizzare?
tripletta : termine, documento, posizione
cosa sono le liste di affissioni
liste di coppie di documenti, posizioni associate ognuna ad un termine
quali informazioni salvo nei segmenti?
liste di affissioni codificate (vedi lezione prima) per ogni token, (ordine lessicografico), puntatori che indicano l’inizio di ogni lista di affissione (per ogni termine)
cosa serve indicizzazione?
definisco ordine liste affissioni, inoltre fondamentale avere lo stesso ordine nei vari segmenti per fare la fusione
come ottengo indicizzazione?
creando una funzione di hash minimale, che mantenga l’ordine e perfetta (no collisioni). Data una lista ritorna l’indice di ogni elemento nella lista senza memorizzarla
Qual’è il vantaggio rispetto ad un semplice dizionario?
occupo solo lo spazio necessario per memorizzare l’output e non quello per memorizzzare le chiavi
come esprimo formalmente la funzione che voglio trovare?
dato X insieme delle chiavi e U insieme universo con X subset U, la funzione mappa X -> 2^b con b ~ log_2(|X|)
quali sono gli elementi necesari per la costruzione di questa funzione?
array di m varaibili lunghe b bit, con m = c|X| dove c è una costante che vedremo essere non troppo alta,
due funzioni di Hash g,h che mappano da U -> m
come ricavo f una volta costruti l’array di bit?
f(x) = B[g(x)] xor B[h(x)]
come costruisco B ?
rappresento le celle del vettore in un grafo: cella -> nodo e per ogni elemento di X mi calcolo gli archi del grafo. procedo poi a definire una foglia con l’arco creatori da un determinato valore w come foglia = f(w) xor nodo a cui la foglia è collegata. rimuovo poi la foglia e procedo così iterativamente. arrivati all’ultima foglia posso risolvere ricorsivamente tutte quelle precedenti e stabile i valori di B
quando l’algoritmo per generare la funzione di indicizzazione non funziona? come evito il problema?
non funziona quando ad un certo punto non trova più foglie, ergo c’è un ciclo. per evitare cicli l’idea è di sfruttare il teorema della teoria dei grafi per cui con n che tende ad infinito (asintotico buono) se i nodi (m) sono almeno 2.09 gli archi è praticamente impossibile avere cicli. scelgo quindi il valore di c come 2.09 e m = c*|X|
come posso diminuire il valore di c?
considerando un maggior numero di funzioni di hash (xor tra 3 celle per determinare f(x) e generazione di ipergrafo c=1,23) o cambiando la modalità in cui viene generato il grafo (facebook con roxyDB = 1.01)
come posso capire se l’elemento appartiene all’elenco?
salvare ulteriore vettore S, contente una firma sugli elementi, mettendo in posizione f(x) la firma di x. Per la verifica di appartenenza di un elemento controllo, dato x se in f(x) c’è s(x). questo permette falsi positivi ma non falsi negativi
come può la generazione di funzioni di questo tipo funzionare, in un contesto statico, meglio di un filtro di Bloom?
Considero sempre una funzione S che mappa da U -> 2^r. considero ora la stessa funzione, restringendo il dominio alle chiavi delle insieme X -> 2^r. genero ora la corrispondente funzione utilizzando la struttura vista, andando ad occupare, usando l’algoritmo di facebook, 1.01 rispetto all numero di chiavi. dato un elemento verifico se S(x) è uguale a fun_creata(x). se falso -> elemento non appartente, se vero non ne sono sicuro, possibile collisione, supponendo hash ideale probabilità 2^-r
quali sono gli elementi necessari per fare information retrivial ( e quindi soddisfare query di un sisop)?
un insieme di documenti validi, un insieme di query e una mappa che ritorna un punteggio associato ai documenti che soddisfano quella query
Come funziona il processo che va dalla query data dall’utente al risultato?
l’utente la formula, vengono fatte una serie di trasformazioni sulla query, per esempio stamming questa viene poi passata al motore che ritorna i punteggi dei documenti e infine vengono ritornati all’utente questi documenti
cose’è lo stemming? cosa distingue stemming prima o dopo?
sono in generali due trasformazioni; stemming prima significa indicizzare + parole con il loro prefisso, cani e cane -> can, meno liste affissioni; stemming dopo significa che se l’utente scrive cane il motore ritorna risultati per cane o cani
come funzionano le query boolean?
prendono in input una stringa e ritornano un punteggio booleano associato ai documenti
che approccio viene utilizzato nelle operazioni per risolvere interrogazioni ?
un approccio lazy; di base creiamo iteratori in cui il next ci ritorna il prossimo elemento, e calcoliamo solo i primi tot elementi, cercando di leggere il meno possibile
qual’è la semantica dell’operazione di unione? come viene realizzata?
l’operazione di unione prende come input k query, onguna delle quali ha associata una lista di documenti e voglio ritornare tutti i documenti che compaioni in almeno una delle liste. per far cio viene fatta una fusione multi-via dei documenti associati ad ogni query. si utilizza un min heap; è possibile inoltre associare ai documenti quali query hanno contribuito per il suo output, guardando per quanti passi quel documento rimane il minino dell’heap e associando ad esso la lista delle query in cui compare
qual’è la semantica dell’operazoine di intersezione? come viene realizzata?
date k query con associate le loro liste di documenti voglio tornare tutti i documenti che sono presenti in tutte le liste. per far ciò sono presenti diversi approcci, uno non lazy e poi un approccio lazy
come funziona l’approccio non lazy per effettuare l’intersezione?
se ho due liste di elementi e la prima è moolto più corta della seconda procedo con una ricerca dicotomica o esponenziale degli elementi della prima all’interno della seconda. complessita: lista + corta * log lista + lunga
come funziona la ricerca esponenziale?
dato un array ordinato procedo effettuando un primo salto di un elemento, e guardo se quello è quello cercato, poi efffettuo un salto di 2 elementi, poi di 4, poi di 16 e così via. ad ogni passo verifico se ho superato l’elemento che cerco; nel caso prendo l’intervallo dato dall’ultimo salto e riparto da lì
che approcci lazy posso adottare per effettuare l’intersezione?
premesso di avere un operatore skip to, che consenta di saltare direttamente ad un elemento (o al primo successivo nel caso non sia presente) è possibile o utilizzare un min heap, in cui effettuo next to sempre sull’elemento con posizione minore andando all’elemento maggiore (che memorizzo in una variabile) e che ritorna l’elemento solo se il min e il max sono uguali oppure un approccio greeedy, che praticamente si dimostra funzionare meglio. qui cerco di accoppiare le prime due liste in maniera greedy, quando trovo elemento in comune faccio skip to della terza fino a questo elemento e vedo se è presente anche qui. appena ottengo un disallineamento in una lista x riparto dalla prima , facendo lo skip to all’elemento tornato in x.
questo diventa + efficiente se lavoro nella prima parte con liste + corte (termini meno frequenti), perchè essendo meno probabile il match permetto avanzamenti lunghi su liste con + alta frequenza (penso a romeo e giulietta)
