===== Progetto di ASD, anno accademico 2012/13 =====

Questo progetto viene valutato in trentesimi e sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto. Può essere scelto il seguente tema oppure un argomento da concordare con il docente.

Progetto in C/C++ (o altro linguaggio da concordare con il docente) per estrarre alcune informazioni implicitamente contenute in una collezione di tweet reperita usando le "Streaming API" di Twitter disponibili pubblicamente https://dev.twitter.com/docs/streaming-apis (grazie a Luca Versari per la raccolta dei tweet). Il contenuto di tali tweet è stato filtrato in modo automatico e, pertanto, alcuni tweet potrebbero risultare poco appropriati (il docente non se ne assume responsabilità, ma il mittente del tweet).

Ciascun tweet è presentato come una riga di testo formattata, come mostrato nel seguente esempio:

''{'lang': 'it', 'text': '@pamela_pascucci @Christian_nofx @isle61 @TazzioliClaudia @liviav2501 @LadyCipria @eusai1965 adoro #Roma,ogni volta è #triste doverla lasciare', 'user': {'name': '☀Dany ®', 'screen_name': 'DiComeDaniela'}, 'entities': {'symbols': [], 'user_mentions': [{'indices': [0, 16], 'name': 'Pamela Pascucci', 'screen_name': 'pamela_pascucci'}, {'indices': [17, 32], 'name': 'Christian Cavina\uf8ff♑', 'screen_name': 'Christian_nofx'}, {'indices': [33, 40], 'name': 'Francesca Grosso ', 'screen_name': 'isle61'}, {'indices': [41, 57], 'name': 'La Terry', 'screen_name': 'TazzioliClaudia'}, {'indices': [58, 69], 'name': 'livia ', 'screen_name': 'liviav2501'}, {'indices': [70, 81], 'name': 'Lady Cipria', 'screen_name': 'LadyCipria'}, {'indices': [82, 92], 'name': 'Elena Usai', 'screen_name': 'eusai1965'}], 'hashtags': [], 'urls': []}}''

La sintassi è quella di ''attributo : valore''. Per esempio l'attributo ''lang'' è ''it'' a indicare che il testo del messaggio è in italiano (o per lo meno Twitter ritiene che lo sia). L'attributo ''text'' riporta il testo spedito con il tweet, precisamente ''@pamela_pascucci @Christian_nofx @isle61 @TazzioliClaudia @liviav2501 @LadyCipria @eusai1965 adoro #Roma,ogni volta è #triste doverla lasciare'', dove ogni occorrenza del simbolo ''@'' indica un destinatario e ogni occorrenza del simbolo ''#''indica una parola chiave che si vuole sottolineare (chiamata hashtag e nel nostro esempio ''#Roma'' e ''#triste''). Continuando l'esame del tweet, l'attributo ''user'' è praticamente uno struct (perché il suo valore è racchiuso tra parentesi graffe) contenente ''name'' e ''screen_name'' dell'utente (quest'ultimo è solitamente quello da indicare se si vuole utilizzare ''@'' per spedirgli un tweet). Segue quindi ''entities'', il cui significato è lasciato come esercizio, in modo da imparare a prendere confidenza con la struttura di un tweet.

Il file ZIP compresso (circa 58 MB) contenente tali tweet è scaricabile dalla [[http://www.di.unipi.it/~grossi/progetto_12.zip|pagina del docente]]. In particolare, il file ZIP contiene ''it.txt'' con 100k tweet con il formato sopra, scelti da ''id.json''. Per gli ardimentosi, ''id.json'' è il vero dump ottenuto da Twitter e da cui sono stati filtrati e semplificati i tweet in ''it.txt''.

Il progetto prevede la scrittura di codice che, preso in ingresso il file ''it.txt'', ne esamina i tweet in esso contenuti. Per ogni tweet, vengono identificati: il mittente, i destinatari e gli hashtag (vedi spiegazione sopra). Da questi occorre quindi creare un grafo, i cui vertici sono gli utenti (sia mittenti che destinatari e, in molti casi, questi coincidono), e c'è un arco tra il mittente e ciascun destinatario di ogni tweet. Poiché possono esserci multipli tweet tra due utenti, occorre evitare di creare archi multipli per la stessa coppia di vertici: la soluzione è associare a ogni arco una lista di etichette che rappresentano tutti i tweet scambiati tra i due utenti.

Utilizzando il grafo così costruito e le sue liste di etichette, il codice deve:
  - identificare gli hashtag espliciti
  - identificare gli hashtag impliciti
  - ricercare uno degli hashtag sopra
  - trovare i tweet che contengono un determinato hashtag (implicito o esplicito)

Mentre l'identificazione degli hashtag espliciti è facilitata dalla presenza del simbolo ''#'', quelli impliciti vanno dedotti perché non sono preceduti dal simbolo ''#'': il grafo dovrebbe aiutare a identificare questi ultimi mettendoli in relazione con quelli espliciti a poca distanza nel grafo e parte del compito, che non è solo mirato allo sviluppo ma anche alla progettazione algoritmica, è appunto l'individuazione di algoritmi adatti a tale scopo. Il progetto richiede appunto di trovare metodi efficienti, che utilizzino la struttura a grafo descritta sopra, per facilitare questo compito di identificazione degli hashtag impliciti. Saranno quindi valutate anche le idee proposte a tal fine oltre che la qualità di stesura del progetto. Per la ricerca, la query vuole sapere se per esempio ''Roma'' è un hashtag e, in tal caso, reperire tutti i tweet che la usano come hashtag (implicito o esplicito).

Consigli per l'implementazione:
  * Utilizzare una rappresentazione compatta per le liste di adiacenza del grafo: poiché il grafo è statico nel nostro caso, una lista di adiacenza può essere memorizzata utilizzando un array (evitando quindi i puntatori per il successore e il predecessore).
  * Per accedere al file ''it.txt'' (e, per chi vuole, al file ''id.json''), conviene evitare di usare le operazioni ''fread'' e ''fwrite'' della libreria standard C/C++. È meglio (= più veloce + più semplice) utilizzare la ''mmap'' disponibile nella stessa libreria. Per un esempio d'uso, scaricare il file C dalla [[http://www.di.unipi.it/~grossi/mm.c|pagina del docente]]