DidaWiki

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 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:

1. identificare gli hashtag espliciti
2. identificare gli hashtag impliciti
3. ricercare uno degli hashtag sopra
4. 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 pagina del docente