Strumenti Utente

Strumenti Sito


matematica:asd:asd_21:progetto_21

Progetto di ASD 2021/2022

Il gioco delle K parole consiste nell'indovinare una parola W che si combina bene con le K parole fornite. Per esempio, con K=2, se le parole fornite sono Buffalo e Clinton, la parola che si combina bene con loro è W = Bill (ossia Buffalo Bill e Bill Clinton). Affinché le K parole siano valide in questo gioco, non devono dar luogo ad ambiguità nella scelta di W: quest'ultima deve risultare come l'unica scelta ragionevole. Un noto quiz televisivo utilizza questo gioco con K=5.

Il progetto richiede di individuare insiemi di K parole valide per questo gioco, utilizzando i testi di alcune pagine prese da Wikipedia e “ripulite” dalla formattazione. È richiesto di modellare tale problema utilizzando un grafo non orientato G = (V,E), dove V rappresenta le parole distinte che si trovano nelle varie pagine di Wikipedia e ciascun arco (u,v) in E indica che le due parole corrispondenti a u e v appaiono consecutivamente (in alternativa, sufficientemente vicine) in almeno una di tali pagine.

Riassumendo: l'input sono le pagine wikipedia e un intero K; l'output sono un certo numero di linee (per esempio una decina), dove ciascuna linea contiene K + 1 parole separate da uno spazio (le prime K parole sono scelte come indicato sopra, e la (K+1)-esima è la parola W univocamente associata a quest'ultime).

Sono lasciate allo studente delle scelte:

  • se ignorare le “stop word” come articoli, preposizioni, verbi ausiliari, ecc.;
  • se vedere G come grafo pesato o meno (per esempio in quante pagine occorrono le coppie di parole);
  • se annotare i nodi e gli archi di G con ulteriori informazioni (qualora fossero necessarie);
  • il criterio di rilevanza con cui scegliere le linee di output (infatti potrebbero esserci molte potenziali soluzioni da cui pescare).

Il progetto si basa su file presi dal mondo reale e prevede di effettuare un'analisi sperimentale dei dati per validare se le scelte di K parole fornite abbiano senso o meno:

  • qui c'è un piccolo campione per fare le prove wiki-small.zip;
  • qui c'è un campione di circa 21mila pagine per un totale di circa 100 milioni di caratteri wikipedia_20k.zip: più pagine si riescono a trattare, meglio è.

Nello svolgimento del progetto, conviene memorizzare G mediante liste di adiacenza (un array di |V| vector in C++, come visto in laboratorio). Potrebbero essere utili un paio di strumenti (facoltativi):

#include <iostream>
#include <string>
#include <filesystem>

using namespace std;
namespace fs = std::filesystem;

int main() {
  string home = ".";  // directory corrente, oppure mettere il path esteso della directory con i file
  for (const auto& entry : fs::directory_iterator(home))
        std::cout << entry.path() << std::endl;
  return 0;
}
matematica/asd/asd_21/progetto_21.txt · Ultima modifica: 13/06/2022 alle 13:50 (2 anni fa) da Roberto Grossi

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki