Obiettivi di apprendimento

Introduzione agli indici testuali (strutture dati per i dati testuali di grandi dimensioni)

Prerequisiti e nozioni di base

Algoritmi e strutture dati

Programma

Dati testuali di dimensioni genomiche (cioé di varie giga- o terabyte) si trovano ovunque intorno a noi. In questa categoria cadono le sequenze biologiche (dati genomici, sequenze proteiche), libri digitali, web crawl data, le collezioni di email, dati musicali, e tanti altri. Oggi la vera sfida non è più di come memorizzare questi dati, ma di come memorizzarli tale che si possano elaborare e interrogare efficaciemente. Indici testuali sono strutture dati per gestire grandi moli di dati testuali. Negli ultimi anni sono stati fatti enormi progressi in questo campo, spinto da una parte dalle necessità della biologica computazionale, e dall'altra di quelle della ricerca web.
In questo corso, studieremo alcuni di questi indici testuali. Inizieremo con un'introduzione breve al suffix array, una struttura dati classica per stringhe, studieremo le sue proprietà, alcune delle sue applicazioni, e gli algoritmi per la sua costruzione efficiente. Dopodiché vedremo due array di supporto, l'LCP-array e la Burrows-Wheeler Transform (BWT). La proprietà della BWT chiamata "clustering property" fa sì che la BWT si presti per la costruzione degli indici testuali compressi. Chiudiamo con lo studio di alcuni tali indici: la FM-index, la RLFM-index, e la r-index.
A seconda delle conoscenze degli studenti, alcuni degli argomenti sopra possono essere sostituiti da altri, per es. da un trattamento più approfondito di wavelet trees (WT) o di extended BWT (eBWT). Il primo è una struttura dati molto potente che viene usato nell'FM-index e r-index, il secondo una variante della BWT per le collezioni di stringhe. Collezioni di stringhe sono di interesse fondamentale, essendo il tipo di dati primario che si trovano a giorno di oggi, ad esempio pangenomi, dati di version control, dati web crawl, etc.
Day 1: Introduction to problems on textual data, pattern matching, suffix arrays (SA)
Day 2: efficient SA construction, LCP-array
Day 3: BWT, backward search, wavelet trees
Day 4: FM-index, RLFM-index, r-index

Bibliografia

Modalità didattiche

lezioni frontali con slide e/o lavagna

Modalità di verifica dell'apprendimento

esercizi da risolvere a casa

Valutazione

capacità di applicare gli algoritmi e stutture dati studiati su esempi concreti; capacità di sviluppare nuovi algoritmi usando gli indici testuali

Criteri di composizione del voto finale

n.a.

Sustainable Development Goals - SDGs

Questa iniziativa contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.
Maggiori informazioni su www.univr.it/sostenibilita