http://algoritmica.org

DizionariListe invertite e Trie

Lucidi tratti da Crescenzi • Gambosi • Grossi,

Strutture di dati e algoritmi Progettazione, analisi e visualizzazione

Addison-Wesley, 2006http://algoritmica.org

http://algoritmica.org

Dizionari

• Universo U delle chiavi• Insieme S di n elementi (n è la dimensione di S)• hp.: e 2 S ha il campo e.chiave 2 U e quello dei

dati satellite e.sat (che dipende dall’applicazione)

• Operazioni di base su S per una chiave k 2 U:– Ricerca(k) trova e t.c. e.chiave = k (null se non esiste)– Inserisci(e) esegue S = S [ {e} (hp. chiavi distinte in S)– Cancella(k) esegue S = S - {e}

(Appartiene(k) ::= Ricerca(k) != null)

http://algoritmica.org

Dizionario ordinato

• Per ogni coppia di chiavi k, k’ 2 U vale k � k’ o k’ � k

Estensione agli elementi dell’insieme S: e � e’ $ e.chiave � e’.chiave

• Operazioni supportate:

Predecessore(k) = e se e.chiave = maxe’ 2 S {e’.chiave � k}

Successore(k) = e se e.chiave = mine’ 2 S {e’.chiave � k}

Intervallo(k,k’) = {e 2 S t.c. k � e.chiave � k’}

Rango(k) = cardinalità di {e 2 S t.c. e.chiave � k}

http://algoritmica.org

Opus libri: liste invertite e trie

• Information retrieval: recupero di documenti (testi)• Molte query sugli stessi documenti: costruzione di un

indice (es. motori di ricerca)

• Liste invertite (file invertite, file dei posting, concordanze): organizzazione logica dei dati– termine = parola o sequenza alfanumerica massimale

– documento = testo partizionato in una sequenza di termini– vocabolario V = termini distinti che appaiono nei documenti– lista invertita per ogni termine P 2 V (posting)

LP = { h T, i i t.c. T=ID(documento) e T[i,i+|P|-1] = P } [alvie]

http://algoritmica.org

Un’implementazione delle liste invertite

• Dizionario per memorizzare il vocabolario V: per esempio, tabella hash o albero binario di ricerca

• Ricordiamo che ciascun P 2 V è memorizzato come un elemento e nel dizionario t.c.– e.chiave = P

– e.sat = LP

• Costruzione di liste invertite

http://algoritmica.org

costo: O(n) inserzioni nel dizionario [alvie]

http://algoritmica.org

Operazioni booleane

• P AND Q $ LP \ LQ

• P OR Q $ LP [ LQ

• NOT P $ complemento{LP}

• Conviene mantenere le liste ordinate ) O(m + n) tempo, analogamente alla fusione nel mergesort [hp |LP| · |LQ|: complessità ottima �(|LP| log (|LQ|/|LP|))]

• P NEAR Q: i termini P e Q devono occorrere vicini (entro maxPos posizioni)

[alvie]• Lo facciamo in O(|LP|+|LQ|+occ) tempo invece che

O(|LP| £ |LQ|), dove occ = numero di occorrenze

http://algoritmica.org

Igno

ran

do VerificaNear

, la

sca

nsio

ne d

elle

liste

è c

om

e qu

ella

del

la f

usio

ne n

el m

erge

sort

) O

(|L P

|+|L

Q|)

tem

po

stes

so t

esto

http://algoritmica.org

VerificaNear è output-sensitive

• ogni volta che avanza su una delle due liste, controlla che le posizioni differiscano di al più M

• fornisce un’occorrenza a ogni iterazione del corpo del while

• viene invocata O(|LP|+|LQ|) volte in tutto e il numero totale di iterazioni è occ.

) il contributo risultante è pari a O(|LP|+|LQ|+occ) tempo

http://algoritmica.org

TRIE: dizionario di stringhe

• Vocabolario V memorizzato usando un dizionario progettato appositamente per le stringhe

• Nuova query: più lungo prefisso che occorre

http://algoritmica.org

Definizione ricorsiva di TRIE per un insieme S di stringhe

TRIE(S) è un albero cardinale �-ario, dove � = numero di simboli dell’alfabeto � = {0, 1, ..., �} delle stringhe in S:

• S è vuoto ) TRIE(S) è NULL

S non è vuoto ) crea radice r e per ogni c 2 �– Sc = {stringhe in S che iniziano con il simbolo c}

– rimuovi il simbolo iniziale c dalle stringhe in Sc (se � vuoto)

– poni ricorsivamente r.figlio[c] = TRIE(Sc)

Ciascun nodo u in TRIE(S) contiene un campo u.dato per memorizzare un elemento del dizionario

Terminatore di fine stringa per ciascuna stringa in S (per avere corrispondenza biunivoca)

http://algoritmica.org

Ricerca per prefissi in un trie

• Stringa pattern P di ricerca con m simboli, in O(m) tempo indipendentemente da |S|

• Modificando il codice, il tempo di ricerca è O(p+1), dove p è la lunghezza p � m del prefisso trovato

http://algoritmica.org

Il costo di Recupera per trovare le occ stringhe in S che soddisfano la ricerca per prefissi può essere più di O(occ) ....

http://algoritmica.org

Trie compatto• Ha solo O(|S|) nodi• Non esistono nodi (eccetto la radice) con un solo figlio• Archi etichettati con descrittori di sottostringhe:

(stringa, inizio, fine)

http://algoritmica.org

Applicazioni:ordinamento di stringhe in tempo lineare

[alvie]

Idea simile a RADIXSORT

http://algoritmica.org

Applicazioni:albero dei suffissi (suffix tree)

• Più potente delle liste invertite: consente la ricerca anche in testi che non possono essere partizionati in termini (es. sequenze biologiche, testi cinesi, ecc.)

• Trie compatto dove S = { suffissi T[i,n] di T}

• Esempio: T = banana$

• Solo spazio O(n)!

http://algoritmica.org

Albero dei suffissi

• Proprietà utilizzata dalla ricerca:

P = T[i, i+|P|-1] sse P è prefisso di T[i,n]

1. Effettua una ricerca per prefissi di P

2. Se P appare interamente in un cammino che dalla radice termina in u, recupera i suffissi T[i,n] nel sottoalbero di u.

3. Per ogni suffisso T[i,n] così recuperato, restituisci la posizione i come occorrenza

Algoritmo output-sensitive: tempo O(|P| + occ)

http://algoritmica.org

FINE

Lucidi tratti da Crescenzi • Gambosi • Grossi,

Strutture di dati e algoritmi Progettazione, analisi e visualizzazione

Addison-Wesley, 2006http://algoritmica.org