| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| matematica:asd:asd_12:progetto_12 [19/06/2013 alle 10:15 (12 anni fa)] – Roberto Grossi | matematica:asd:asd_12:progetto_12 [02/07/2013 alle 08:34 (12 anni fa)] (versione attuale) – Roberto Grossi |
|---|
| ==== Progetto di ASD, anno accademico 2012/13 ==== | ===== 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. | 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 l'autore del tweet). | 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: | 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': []}}'' | ''{'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 di un simbolo ''@'' indica un destinatario e di ''#''indica una parola chiave che si vuole sottolineare (chiamata hashtag e nel nostro esempio ''#Roma''). 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 per imparare a esplorare la struttura di un tweet. | 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 tweets 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 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 (devi 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. | 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: | Utilizzando il grafo così costruito e le sue liste di etichette, il codice deve: |
| - trovare i tweet che contengono un determinato hashtag (implicito o esplicito) | - 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. Il progetto richiede appunto di trovare metodi efficienti, che utilizzino la struttura a grafo descritta sopra, per facilitare questo compito. Saranno quindi valutate anche le idee proposte a tal fine. | 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: | Consigli per l'implementazione: |
