ETD system

Electronic theses and dissertations repository

 

Tesi etd-11192007-195543


Thesis type
Tesi di laurea specialistica
Author
BARILARI, ALESSANDRO
URN
etd-11192007-195543
Title
Strutture dati compresse e loro applicazione a DB testuali
Struttura
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
TECNOLOGIE INFORMATICHE
Commissione
Relatore Ferragina, Paolo
Parole chiave
  • Huffman
  • database testuali
  • motori di ricerca
  • compressione
  • rank
  • select
  • indici
  • strutture dati
Data inizio appello
14/12/2007;
Consultabilità
completa
Riassunto analitico
Il lavoro svolto indaga le soluzioni proposte in letteratura per la realizzazione di strutture dati compresse per l'esecuzione di primitive Rank/Select. Vengono analizzate a fondo le strutture dati ritenute migliori e vengono proposte delle loro varianti che riescono ad ottenere un ottimo rapporto tra qualità di compressione e prestazioni e che permettono una personalizzazione da parte dell'utente. Queste varianti vengono realizzate ed incluse in una libreria Java rilasciata sotto licenza LGPL,a sua volta inclusa nel progetto SmallText, sviluppato in collaborazione con Yahoo!, che prevede la realizzazione di strumenti per la compressione e l'accesso veloce a database testuali di grandi dimensioni. L'utilizzo delle strutture dati per Rank/Select ha permesso di realizzare varianti dell'algoritmo Huffman che riescono a migliorarne le prestazioni in tempo di accesso, mantenendo l'ottima qualità di compressione.
File