ISN Structuration et organisation de l'information

Structuration et organisation de l'information

Savoirs :	On manipule de grandes quantités d'informations. Il est nécessaire de les organiser.
Capacités :	Classer des informations, notamment sous forme d'une arborescence.
Observation :	On peut ici étudier le système d'organisation de fichiers en dossiers. Un ensemble de documents unis par des liens hypertextes fournit un exemple de classement de type graphe.

Imaginez une encyclopédie de cinq mille pages, dont les articles ne seraient pas ordonnés, elle serait difficilement utilisable pour y retrouver un article en particulier.

Les dictionnaires et encyclopédies possèdent une organisation, le classement par ordre alphabétique du mot qui y est défini ou illustré. Cette organisation est cependant insuffisante pour de nombreux exemples de recherches. Comment feriez-vous par exemple, pour trouver rapidement tous les mots du dictionnaire qui s'écrivent en quatre lettres ?

Pour faciliter les recherches dans une encyclopédie, on utilise des index ; il peut exister plus d'un index pour la même encyclopédie, qu'on utilisera dans des circonstances différentes.

Systèmes de classifications efficaces

Quand on peut définir une relation d'ordre dans une collection d'articles, on peut trier les articles. S'il y a plus d'une relation d'ordre, c'est préférable de réaliser un index pour chacune des relations. Les index les plus efficaces ont une structure d'arbres binaires.

Exemple trivial de classement

Prenons comme « articles » les lettres de l'alphabet, et comme ordre, l'ordre alphabétique.

Un index séquentiel évident est :

 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

On peut préférer un index arborescent :

Supériorité de l'index organisé en arbre

Si on veut faire un traitement automatique des informations, on peut se préoccuper de la durée du traitement.

Comparons les durées de classement d'un lettre de l'alphabet tirée au hasard, en supposant que la durée augmente comme le nombre de comparaisons alphabétiques à faire :

pour l'index séquentiel, ça peut aller très vite (si on doit classer un A) ou 26 fois plus lentement (si on doit classer un Z). On peut supposer qu'en moyenne, on doit faire 13 comparaisons ;
pour l'index arborescent, on doit faire entre 4 et 5 comparaisons (moyenne 4,5).

L'avantage de l'index arborescent devient de plus en plus évident quand on dispose d'un grand nombre de données à classer :

pour un index séquentiel, la durée moyenne de classement double quand le nombre de données double. Par exemple pour un million de données, on fait en moyenne un demi-million de comparaisons pour classer un nouvel article.
pour un index arborescent, il suffit d'une comparaison de plus chaque fois que le nombre de données est doublé. Pour un million de données, une vingtaine de comparaisons est suffisante !

Organisations en arbre souvent utilisées

Systèmes de fichiers : répertoires et fichiers

Les disques durs utilisés en 2013 contiennent couramment des centaines de giga-octets, c'est à dire,

quelques centaines de films, ou
quelques millions de photos,
quelques milliards de pages imprimables,
etc.

Pour arriver à maintenir de telles collections de données, une simple liste séquentielle est tout à fait inappropriée.

Un système d'arbre est utilisé : les répertoires (ou dossiers) sont les nœuds de l'arbre, les fichiers sont les feuilles.

Dans les systèmes de fichiers Unix et Mac OS, un seul arbre permet de regrouper tous les fichiers. Pour Windows, il peut y avoir 26 arbres distincts, correspondant à autant de « lecteurs différents », nommés de A: à Z:.

Les index de bases de données

Les systèmes de gestion de base de données relationnelles (MySQL, PostgreSQL, Oracle, Access) permettent de définir des index pour permettre un accès plus rapide aux données. Créer un index est utile pour tous les champs qui peuvent faire l'objet d'une recherche : l'exemple trivial ci-dessus montre qu'un index semble « rentable » dès qu'on a plus de huit articles différents à gérer.

Exercices

Compter les fichiers de votre ordinateur

Documentez-vous sur la commande find, puis trouvez une façon de compter le nombre de fichiers existant sur le disque dur de votre ordinateur.

Astuces :

on peut renvoyer la sortie de find vers un fichier, puis compter les lignes de ce fichier à l'aide d'un éditeur de texte.
il est possible d'utiliser la commande wc.

Déterminez la profondeur maximale de l'arbre de votre système de fichiers

Cette profondeur peut être trouvée en retraitant le fichier contenant la sortie de la commande find précédente, en comptant le nombre de caractères « séparateurs » de chemin dans les noms de fichier : le slash pour Unix, l'antislash pour Windows ...

Voici une ligne de commande Unix qui permet d'afficher le nombre de répertoires/fichier le long d'un chemin, pour chaque ligne du fichier find.txt qu'on aura fabriqué à l'exercice précédent :

  cat find.txt | awk -F / '{print NF}'

La commande cat permet de dérouler le contenu d'un fichier ; la barre verticale | sert à « piper » (en mauvais franglais), c'est à dire à « tuyauter » le flux de sortie de la commande cat dans l'entrée standard de la commande awk.

Lisez la page de manuel de la commande awk, pour trouver la signification de l'option "-F /", et la signification de la variable NF.

Astuces :

Utilisez les commandes sort et uniq (après avoir consulté leurs pages de manuel) pour clarifier le résultat de la commande awk.