20160418:TP:Go:WebCrawling
Introduction
Notre objectif cette semaine est d'implémenter un petit crawler web en go.
En amont du TP, je vous conseille de regarder la documentation des packages suivantes:
Extraire les liens d'une page HTML
- package: src/tutorial20160418/links
Dans un premier temps vous allez écrire un package exposant une fonction qui à partir d'une page HTML (sous la forme d'un io.Reader récupérer via le package http) construit la liste des liens contenu dans la page.
La page HTML va être traversée comme un arbre (et oui, le HTML décrit un arbre) via un parcours profondeur. L'arbre en question est représenté sous la forme premier-fils/frère-droit avec les champs FirstChild (guess what) et NextSibling.
On va construire le code de la manière suivante: on commence par construire l'arbre via html.Parse(page), on construit ensuite la partie récursive sous forme de fonction du premier ordre (une lambda quoi), la structure globale du code ressemble à ça:
func GetLinks(page io.Reader) (links []string, err error) { doc, err := html.Parse(page) if err != nil { return } // the recursive DFS function var f func(n *html.Node) f = func(n *html.Node) { // match the node (see later) // if it's a link, get the content of the href attribute // append it to links // loop over children and do the recursive call } // do the job ! f(doc) return }
Afin d'identifier un lien, nous devons tester si le nœud courant est un ElementNode (dans le champ Type du nœud) et après nous devons tester si c'est un élément avec la balise a (dans le champ Data.)
Enfin, pour obtenir le lien, il faut trouver l'attribut "href" dans le nœud: les attributs sont stockés dans une slice (champs Attr) de structures avec deux champs: Key contenant le nom de l'attribut et Value contenant le contenu de l'attribut (notre lien).
Crawling
- répertoire: src/tutorial20160418/webcrawler, package main
Nous allons limiter notre crawler aux pages internes du site pour éviter de crawl tout Internet.
Nous avons besoin des actions suivantes:
- récupérer une page à partir d'une url (puis les liens dedans),
- éliminer les url qui ne sont pas internes au site.
- stocker les url de manière unique et marquer celles déjà visitées,
Les deux premiers points se font assez simplement via les packages net/http et net/url pour le dernier point, nous voulons un ensemble (au sens algo du terme) et un marquage intelligent. En Go, la stratégie usuelle pour implémenter un ensemble est d'utiliser une map dont les clefs sont les éléments (nos url) et les valeurs des booléens. On va s'écarter légèrement des implementations décrites dans la documentation et utiliser le booléen associé pour indiquer si la page a été visitée. En gros, si l'url est présent dans la map c'est qu'elle a déjà été rencontrée et si en plus le booléen associé est à vrai c'est qu'elle a déjà été visitée, ce qui nous permettra d'éviter d'ajouter plusieurs fois la même url et surtout de la visiter plusieurs fois (boucle tout ça … )
Rappel: lorsque vous accéder à un élément d'une map, vous pouvez récupérer un booléen indiquant sa présence (si l'élément n'est pas présent, vous récupérez la valeur construite par défaut, dans notre cas false.)
// visited [string]bool v, present := visited[my_url] // present is true if my_url is in the map // if present is true, v indicates if the url have been visited
Il nous faut également une « file » d'url à visiter, une simple slice suffira, par contre on mettra dans cette slice des éléments du type *url.URL pour les utiliser plus simplement.
Pour ne conserver que les urls qui nous intéresse, on va utiliser une url de référence fournissant le domaine qui permet de reconstruire une url exploitable (donc complète, même si le lien ne l'était pas) et surtout nous permettra de vérifier que cette url à le même domaine que l'url de référence.
- Compléter le code de la fonction suivante:
func add_url(u string, set *[]*url.URL, visited map[string]bool, domain *url.URL) { parsed, err := domain.Parse(u) if err != nil { log.Fatal(err) } if parsed.Host == domain.Host && parsed.Path != "" { // parsed is an url from the site (and not the root) // we can now use parsed.Path for set and visited } }
Charger une page est relativement simple, voici un extrait de code:
// page *url.URL res, err := http.Get(page.String()) if err != nil { log.Fatal(err) } // use res.Body as a reader for the links extraction res.Body.Close() // MANDATORY
- Compléter le programme pour qu'il prenne une url en argument, crawl tous les liens et affiches toutes les urls correspondante
Voici un exemple de sortie:
shell> ./webcrawler http://cri.epita.net/ http://cri.epita.net/ http://cri.epita.net/passwords/ http://cri.epita.net/news/ http://cri.epita.net/netsoul/ http://cri.epita.net/change_password/ http://cri.epita.net/redump/ http://cri.epita.net/contact/ 7
