• compressione
• database testuali
• Huffman
• indici
• motori di ricerca
• rank
• select
• strutture dati

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.