programmation (suite)

La recherche séquentielle

L’ordonnancement le plus simple qui puisse être fait au cours de l’implémentation d’une table est séquentiel : on range les uns à la suite des autres les éléments constituant la table en ne tenant aucun compte de la structure d’ordre existant sur l’ensemble des clefs (façon de procéder qui, en particulier, est très intéressante dans le cas où il est fréquemment nécessaire d’adjoindre de nouveaux éléments à la table). Si l’on suppose la table ainsi implémentée, compte tenu de l’absence de toute information liée à la localisation précise d’un quelconque de ses éléments, le seul mode de recherche possible d’un élément particulier est, lui aussi, séquentiel : en procédant dans l’ordre du rangement, on examine successivement les clefs des éléments jusqu’à ce que l’élément cherché puisse être identifié.

Bien qu’a priori cette méthode puisse sembler peu élaborée, elle est quelquefois la meilleure, notamment si, au cours d’un même traitement, il est nécessaire de retrouver une part non négligeable des éléments de la table.

La recherche indexée

Si l’utilisation d’une certaine table n’implique, au cours du temps, que très peu d’adjonctions d’éléments, on peut implémenter cette table en rangeant ses éléments dans un tableau successivement dans l’ordre des clefs. Mais, dans cette hypothèse, toute insertion, dans une table déjà créée, de nouveaux éléments entraînera obligatoirement l’utilisation d’un programme de tri-fusion dont le coût peut, en général, être assez élevé.

Si, pour des raisons de « place perdue », cette méthode est inapplicable, on peut utiliser la variante de l’implémentation en structure de liste : dans ce cas, on range séquentiellement les informations associées aux clefs respectives de chaque élément de la table et, parallèlement, on range dans un tableau successivement dans l’ordre des clefs les couples (clef, pointeur vers l’information associée à la clef). Si l’on suppose la table ainsi créée, la recherche d’un de ses éléments est ramenée à celle de la clef correspondante dans le tableau, problème qui peut être résolu, par exemple, au moyen de la technique dichotomique : on partage le tableau en deux sous-tableaux jointifs et de même « taille », puis on compare la clef à identifier à la clef de l’élément frontière des deux parties du tableau.

Si ces deux clefs sont égales, l’élément recherché a été trouvé, sinon, puisque les clefs sont ordonnées, il est possible de localiser à quelle moitié du tableau appartient la clef à identifier. Dans ce dernier cas, on est donc amené à résoudre le même problème qu’initialement, la taille du tableau ayant diminué de moitié ; d’où le résultat par itération.

La recherche séquentielle indexée

On peut combiner les avantages des deux méthodes précédentes, relative rapidité d’accès à l’information et souplesse au niveau des adjonctions, en procédant de la manière suivante :
— on subdivise la table initiale en sous-tables, le contenu de chaque sous-table étant caractérisé par une propriété de la clef, l’ensemble de ces propriétés étant tel qu’une clef donnée a obligatoirement une et une seule telle propriété (par exemple, si la clef est alphabétique, on définit une sous-table comme étant formée de tous les éléments de la table dont la première lettre est une lettre donnée) ;
— à l’intérieur de chaque sous-table, on procède à un rangement séquentiel.

Si l’on suppose la table ainsi implémentée, la recherche d’un de ses éléments se ramène à la recherche de la sous-table à laquelle il appartient (recherche indexée sur la famille des propriétés qui a servi à faire le tri) et à l’exploration séquentielle de cette sous-table.

Cette méthode est à déconseiller si de trop nombreuses sous-tables sont insuffisamment remplies par rapport à d’autres sous-tables. Il est évidemment possible d’itérer ce schéma et de procéder à des recherches indexées à plusieurs niveaux d’indexation (un exemple type est le processus utilisé pour chercher un mot dans un dictionnaire). L’intérêt n’est réel que si les sous-tables définies lors de la première partition s’avèrent de dimensions trop importantes pour que la recherche séquentielle se fasse rapidement.

La recherche mêlée (hash coding)

Si la table à implémenter est de très grande dimension (banque de données par exemple) et s’il est nécessaire d’y faire de fréquentes retouches (adjonctions, suppressions), les méthodes précédentes sont en général inapplicables, car trop coûteuses : la méthode séquentielle à cause du temps de recherche de l’information, les méthodes indexées à cause de la perte de temps due aux tris-fusions (lors de la création et, plus généralement, de toute modification de la table) et, dans une moindre mesure, à cause de la perte de place due à l’existence du tableau des couples (clef, pointeur).

La solution idéale serait de pouvoir définir une « fonction d’adressage » f, algorithme qui ferait correspondre à chaque clef l’adresse à laquelle est rangé l’élément de la table qui lui est associé. Pour cela, on doit connaître a priori la taille de la zone mémoire réservée à cette table et, comme l’accès à une information ne peut être fait que de façon uniforme, il est également nécessaire de supposer que les éléments de la table peuvent être respectivement stockés dans une cellule (ensemble de mots-mémoires consécutifs) de taille fixe.

Ces a priori étant admis, il reste à construire la fonction d’adressage. Celle-ci doit « idéalement » avoir les propriétés suivantes :
— clef₁ ≠ clef₂ ⇒ f (clef₁) ≠ f (clef₂) ;
— la zone mémoire réservée à l’implantation de la table est utilisée au mieux, c’est-à-dire aussi remplie que possible.

En pratique, et sauf pour des exemples très académiques, on ne sait pas définir une fonction ayant ces propriétés et dont l’algorithme de construction soit simple, c’est-à-dire très nettement moins coûteux qu’un algorithme de tri-fusion. On se borne en général à ce que la fonction f satisfasse « raisonnablement » à la seconde condition et à ce que les cas de « synonymie » ou de « collision » de clefs [clef₁ ≠ clef₂ et f (clef₁) = f (clef₂)] soient aussi peu fréquents que possible.