Sujet
On se propose d’implémenter un algorithme de compression de graphe adapté au graphe du Web.
Le graphe du Web
L’ensemble des documents HTML peut être vu comme un graphe dans lequel les noeuds sont les documents eux-mêmes et les arcs les hyper-liens reliant les documents entre eux. On notera rapidement que ce graphe est naturellement orienté; en effet les hyper-liens le sont.
Le «véritable» graphe du Web est assez compliqué compte-tenu de l’existence possible, par exemple, de liens de différentes natures (hyper-texte, hyper-média, liens logiques), ou encore de la possibilité de désigner des points particuliers dans un document (points d’ancrage). Le type de graphe qui nous intéresse est le «plus simple»: deux noeuds sont reliés par une flèche si il existe au moins un hyper-lien (quel que soit son type) reliant les deux documents correspondant.
La constitution d’un tel graphe est une véritable problématique mais sa conservation un tour de force compte-tenu du volume de donnée que cela représente. C’est ainsi que plusieurs techniques de compression de graphes ont vu le jour. Celle que nous présentons ici est inspirée de celle employée par le LAW Laboratoire d’Algorithmique pour le Web.
Des exemples de graphes du Web
La collecte d’un sous-graphe représentatif du graphe dans son ensemble est un problème assez compliqué (la collecte elle-même est aussi bien plus compliquée qu’il n’y paraît). Vous sont donc donnés deux morceaux du Web sous la forme de listes d’adjacence:
- eu.int a été obtenu par «aspiration» de plus de 800.000 pages Web du domaine Internet
eu.int(domaine appartenant à la communauté européenne). Le fichier donné ne contient qu’un extrait du résultat obtenu (15000 noeuds conservés). Le fichier est au format ASCII et est constitué de lignes, chacune représentant un noeud du graphe. Le premier nombre est le numéro du noeud et les suivants (triés numériquement) constituent la liste des successeurs de ce noeud. - nd.edu (.zip de 3,6Mo) est une collecte de 325.728 pages du domaine
nd.edu(domaine de l’Université de Notre-Dame dans l’Indiana, États-Unis). Le fichier est au format ASCII et est constitué de lignes, chacune représentant un arc du graphe. Le premier nombre est l’origine de l’arc et le second sa destination. On prendra garde au fait que le fichier n’est pas intégralement trié.
La compression du graphe du Web
La compression décrite ici utilise des propriétés supposées du graphe du Web (qui est un graphe particulier), et notamment:
- la localité: la plupart des liens sortant d’une page donnée sont dirigés vers le même ensemble de documents,
- la similarité: deux pages voisines (disons deux pages dont les URLs sont proches au sens naturel du terme) ont de nombreux arcs sortants vers les mêmes pages.
La représentation de base, sur laquelle la suite repose, est la suivante: à chaque noeud est associé son nombre de successeurs (degré sortant) et pour chacun d’eux son numéro. Ex:
| Noeud | Degré | Successeurs |
|---|---|---|
| 15 | 11 | 13, 15, 16, 17, 18, 19, 23, 24, 203, 315, 1034 |
| 16 | 10 | 15, 16, 17, 22, 23, 24, 315, 316, 317, 3041 |
Une première transformation que l’on peut appliquer consiste à remplacer la liste des successeurs (…, Si, …) par la liste (…, Si-Si-1-1, …). Le premier élément sera remplacé par la valeur S0-N (où N est le numéro du noeud courant). On notera que les nombres générés sont tous positifs ou nuls sauf le premier auquel on appliquera donc la transformation suivante: si le nombre (x) est positif on le remplace 2*x et s’il est négatif par 2*|x|-1. Ainsi l’on obtient:
| Noeud | Degré | Successeurs |
|---|---|---|
| 15 | 11 | 3, 1, 0, 0, 0, 0, 3, 0, 178, 111, 718 |
| 16 | 10 | 1, 0, 0, 4, 0, 0, 290, 0, 0, 2723 |
1. Dans le langage de votre choix (mais un choix raisonnable!), implémentez cette première transformation de façon à coder les deux graphes donnés en exemple.
2. Écrire un programme permettant d’obtenir à partir d’un numéro de noeud la liste de ses successeurs en lisant le fichier compressé.
3. La suite de valeurs obtenue peut alors être compressée en utilisant un code de Golomb par exemple. Implémentez-le.
Une seconde transformation applicable consiste à utiliser les propriétés supposées des graphes que l’on considère de sorte que l’on code la liste des successeurs d’un noeud (N) par «différentiation» avec la liste des successeurs d’un noeud voisin (M). La représentation du noeud M par rapport au noeud N, dit noeud de référence, (M-N est appelé la distance de référence), est alors constitué de deux parties:
- la première est appelée liste de similarité et est constituée d’autant de bits que le noeud N a de successeurs. Un bit est à 1 si le successeur correspondant de N est aussi successeur de M et à 0 sinon.
- la seconde est appelée liste complémentaire et est constituée des successeurs de M qui ne sont pas successeurs de N.
On obtient ainsi les valeurs suivantes:
| Noeud | Degré | Distance | Similarité | Complémentaire |
|---|---|---|---|---|
| N=15 | 11 | 0 | 13, 15, 16, 17, 18, 19, 23, 24, 203, 315, 1034 | |
| M=16 | 10 | 1 | 01110011010 | 22, 316, 317, 3041 |
Lorsque la distance est 0, seule la liste complémentaire est utilisée.
Un premier problème est qu’il faut maintenant trouver pour tout noeud M un noeud de référence N permettant d’obtenir une bonne compression pour M. Dès que le graphe contient quelques milliers de noeuds on comprend aisément qu’une recherche exhaustive parmi l’ensemble de noeuds est impraticable. Une façon de procéder est de rechercher le noeud de référence parmi les W noeuds précédents ou les W suivants (fenêtre de recherche de taille W).
4. Écrire un programme (dans le langage de votre choix) permettant de (dé)coder les graphes, correspondants aux fichiers donnés en exemple, en utilisation cette technique. Ce programme devra permettre de choisir la largeur de la fenêtre (W).
4 bis. Comment peut-on compresser les différentes listes ? Implémentez-le.
Le TP devra être rédigé (sous la forme de documents HTML) et rendu avec les codes sources des programmes; ce au plus une semaine après la séance. On oubliera pas d’y adjoindre quelques commentaires, tests et conclusions.
