Chapitre 1 Tableaux
Les tableaux sont une des structures de base de l'informatique. Un
tableau représente selon ses dimensions, un vecteur ou une matrice
d'éléments d'un même type. Un tableau permet l'accès direct
à un élément, et nous allons nous servir grandement de cette
propriété dans les algorithmes de tri et de recherche en table que
nous allons considérer.
1.1 Le tri
Qu'est-ce qu'un tri? On suppose qu'on se donne une suite de N
nombres entiers á ai ñ, et on veut les ranger en ordre
croissant au sens large. Ainsi, pour N = 10, la suite
á 18, 3, 10, 25, 9, 3, 11, 13, 23, 8 ñ
devra devenir
á 3, 3, 8, 9, 10, 11, 13, 18, 23, 25 ñ
Ce problème est un classique de l'informatique. Il a été
étudié en détail, cf. la moitié du livre de Knuth [30].
En tant qu'algorithme pratique, on le rencontre souvent. Par exemple,
il faut établir le classement de certains élèves, mettre en ordre
un dictionnaire, trier l'index d'un livre, faire une sortie lisible
d'un correcteur d'orthographe, ... Il faudra bien faire la
distinction entre le tri d'un grand nombre d'éléments (plusieurs
centaines), et le tri de quelques éléments (un paquet de cartes).
Dans ce dernier cas, la méthode importe peu. Un algorithme amusant,
bogo-tri, consiste à regarder si le paquet de cartes est
déjà ordonné. Sinon, on le jette par terre. Et on recommence. Au
bout d'un certain temps, on risque d'avoir les cartes ordonnées. Bien
sûr, le bogo-tri peut ne pas se terminer. Une autre technique
fréquemment utilisée avec un jeu de cartes consiste à regarder s'il
n'y a pas une transposition à effectuer. Dès qu'on en voit une à
faire, on la fait et on recommence. Cette
méthode marche très bien sur une bonne distribution de cartes.
Plus sérieusement, il faudra toujours avoir à l'esprit que le nombre
d'objets à trier est important. Ce n'est pas la peine de trouver une
méthode sophistiquée pour trier 10 éléments. Pourtant, les
exemples traités dans un cours sont toujours de taille limitée, pour
des raisons pédagogiques il n'est pas possible de représenter un tri
sur plusieurs milliers d'éléments. Le tri, par ses multiples
facettes, est un très bon exemple d'école. En général, on exigera
que le tri se fasse in situ, c'est-à-dire que le résultat soit
au même endroit que la suite initiale. On peut bien sûr trier autre
chose que des entiers. Il suffit de disposer d'un domaine de valeurs
muni d'une relation d'ordre total. On peut donc trier des caractères,
des mots en ordre alphabétique, des enregistrements selon un certain
champ. On supposera, pour simplifier, qu'il existe une opération
d'échange ou plus simplement d'affectation sur les éléments de la
suite à trier. C'est pourquoi nous prendrons le cas de valeurs
entières.
1.1.1 Méthodes de tri élémentaires
Dans tout ce qui suit, on suppose que l'on trie des nombres entiers et
que ceux-ci se trouvent dans un tableau a. L'algorithme de tri le
plus simple est le tri par sélection. Il consiste à trouver
l'emplacement de l'élément le plus petit du tableau, c'est-à-dire
l'entier m tel que ai ³ am pour tout i. Une fois cet
emplacement m trouvé, on échange les éléments a1 et am.
Puis on recommence ces opérations sur la suite á a2, a3,
..., aN ñ, ainsi on recherche le plus petit élément de
cette nouvelle suite et on l'échange avec a2. Et ainsi de suite
... jusqu'au moment où on n'a plus qu'une suite composée d'un
seul élément á aN ñ.
La recherche du plus petit élément d'un tableau est un des premiers
exercices de programmation. La détermination de la position de cet
élément est très similaire, elle s'effectue à l'aide de la suite
d'instructions:
m = 0;
for (int j = 1; j < N; ++j)
if (a[j] < a[m])
m = i;
Figure 1.1 : Exemple de tri par sélection
L'échange de deux éléments nécessite une variable temporaire t
et s'effectue par:
t = a[m]; a[m] = a[1]; a[1] = t;
Il faut refaire cette suite d'opérations en remplacant 1 par 2,
puis par 3 et ainsi de suite jusqu'à N. Ceci se fait par
l'introduction d'une nouvelle variable i qui prend toutes les
valeurs entre 1 et N. Ces considérations donnent lieu au
programme présenté en détail ci-dessous. Pour une fois, nous l'
écrivons pour une fois en totalité; les procédures d'acquisition des
données et de restitution des résultats sont aussi fournies. Pour
les autres algorithmes, nous nous limiterons à la description de la
procédure effective de tri.
class TriSelection {
final static int N = 10;
static int[] a = new int[N]; // Le tableau à trier
static void initialisation() { // On tire au sort des nombres
// entre 0 et 127, en initialisant
// le tirage au sort sur l'heure
for (int i = 0; i < N; ++i)
a[i] = (int) (Math.random() * 128);
}
static void impression() {
for (int i = 0; i < N; ++i)
System.out.print (a[i] + " ");
System.out.println ("");
}
static void triSelection() {
int min, t;
for (int i = 0; i < N - 1; ++i) {
min = i;
for (int j = i+1; j < N; ++j)
if (a[j] < a[min])
min = j;
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
public static void main (String args[]) {
initialisation(); // On lit le tableau
impression(); // et on l'imprime
triSelection(); // On trie
impression(); // On imprime le résultat
}
}
Figure 1.2 : Exemple de tri bulle
Il est facile de compter le nombre d'opérations nécessaires. A
chaque itération, on démarre à l'élément ai et on le compare
successivement à ai+1, ai+2, ..., aN. On fait donc
N - i comparaisons. On commence avec i = 1 et on finit avec i
= N-1. Donc on fait (N-1) + (N-2) + ··· + 2 + 1 = N(N-1)/2
comparaisons, et N-1 échanges. Le tri par sélection fait donc de
l'ordre de N2 comparaisons. Si N = 100, il y a 5000
comparaisons, soit 5 ms si on arrive à faire une comparaison et
l'itération de la boucle for en 1µs, ce qui est tout à
fait possible sur une machine plutôt rapide actuellement. On écrira
que le tri par sélection est en O(N2). Son temps est quadratique par
rapport aux nombres d'éléments du tableau.
Une variante du tri par sélection est le tri bulle. Son
principe est de parcourir la suite á a1, a2, ..., aN
ñ en intervertissant toute paire d'éléments consécutifs
(aj-1, aj) non ordonnés. Ainsi après un parcours,
l'élément maximum se retrouve en aN. On recommence avec le
préfixe á a1, a1, ..., aN-1 ñ, ... Le nom
de tri bulle vient donc de ce que les plus grands nombres se
déplacent vers la droite en poussant des bulles successives de la
gauche vers la droite. L'exemple numérique précédent est donné
avec le tri bulle dans la figure 1.2.
La procédure correspondante utilise un indice i qui marque la
fin du préfixe à trier, et l'indice j qui permet de déplacer
la bulle qui monte vers la borne i. On peut compter aussi très
facilement le nombre d'opérations et se rendre compte qu'il s'agit
d'un tri en O(N2) comparaisons et éventuellement échanges (si par
exemple le tableau est donné en ordre strictement décroissant).
static void triBulle() {
int t;
for (int i = N-1; i >= 0; --i)
for (int j = 1; j <= i; ++j)
if (a[j-1] > a[j]) {
t = a[j-1]; a[j-1] = a[j]; a[j] = t;
}
}
1.1.2 Analyse en moyenne
Pour analyser un algorithme de tri, c'est à dire déterminer le
nombre moyen d'opérations qu'il effectue, on utilise le modèle des
permutations. On suppose dans ce modèle que la suite des nombres à
trier est la suite des entiers 1,2, ... n et l'on admet que
toutes les permutations de ces entiers sont équiprobables. On peut
noter que le nombre de comparaisons à effectuer pour un tri ne
dépend pas des éléments à trier mais de l'ordre dans lequel ils
apparaissent. Les supposer tous compris entre 1 et N n'est donc
pas une hypothèse restrictive si on ne s'intéresse qu'à l'analyse
et si l'on se place dans un modèle d'algorithme dont l'opération de
base est la comparaison.
Pour une permutation a de {1, 2 ... n } dans lui-même,
une inversion est un couple (ai, aj) tel que i < j et ai >
aj. Ainsi, la permutation
á 8,1,5,10,4,2,6,7,9,3 ñ
qui correspond à l'ordre des éléments de la figure
1.1, comporte 21 inversions. Chaque échange
d'éléments de la procédure TriBulle supprime une et une
seule inversion et, une fois le tri terminé, il n'y a plus aucune
inversion. Ainsi le nombre total d'échanges effectués est égal au
nombre d'inversions dans la permutation. Calculer le nombre moyen
d'échanges dans la procédure de tri bulle revient donc à compter le
nombre moyen d'inversions de l'ensemble des permutations sur N
éléments. Un moyen de faire ce calcul consiste à compter le nombre
d'inversions dans chaque permutation à faire la somme de tous ces
nombres et à diviser par N!. Ceci est plutôt fastidieux, une
remarque simple permet d'aller plus vite.
L'image miroir de toute permutation a = á a1, a2 ...
aN ñ est la permutation b = á aN, ..., a2, a1
ñ. Il est clair que (ai, aj) est une inversion de a
si et seulement si ce n'est pas une inversion de b. La somme du
nombre d'inversions de a et de celles de b est
N(N-1)/2. On regroupe alors deux par deux les termes de la somme des
nombres d'inversions des permutations sur N éléments et on obtient
que le nombre moyen d'inversions sur l'ensemble des permutations est
donné par:
ce qui est donc le nombre moyen d'échanges dans la
procédure TriBulle. On note toutefois que le nombre de comparaisons
effectuées par TriBulle est le même que celui de TriSelection
soit N(N-1)/2.
1.1.3 Le tri par insertion
Figure 1.3 : Exemple de tri par insertion
Une méthode complètement différente est le tri par insertion.
C'est
la méthode utilisée pour trier un paquet de cartes. On prend une
carte, puis 2 et on les met dans l'ordre si nécessaire, puis 3 et on
met la 3ème carte à sa place dans les 2
premières, ... De manière générale on suppose les i-1
premières cartes triées. On prend la i ème
carte, et on essaie de la mettre à sa place dans les i-1 cartes
déjà triées. Et on continue jusqu'à i = N. Ceci donne le
programme suivant
static void triInsertion() {
int j, v;
for (int i = 1; i < N; ++i) {
v = a[i]; j = i;
while (j > 0 && a[j-1] > v) {
a[j] = a[j-1];
--j;
}
a[j] = v;
}
}
Pour classer le i ème élément du
tableau a, on regarde successivement en marche arrière à
partir du i-1ième. On décale les éléments
visités vers la droite pour pouvoir mettre a[i] à sa juste
place. Le programme précédent contient une légère erreur, si
a[i] est le plus petit élément du tableau, car on va sortir
du tableau par la gauche. On peut toujours y remédier en supposant
qu'on rajoute un élément a[0] valant -maxint. On
dit alors que l'on a mis une sentinelle
à gauche du tableau a. Ceci n'est pas toujours possible, et il
faudra alors rajouter un test sur l'indice j dans la boucle
while. Ainsi, pour le tri par insertion, l'exemple numérique
précédent est dans la figure 1.3.
Le nombre de comparaisons pour insérer un élément dans la suite
triée de ceux qui le précédent est égal au nombre d'inversions
qu'il présente avec ceux-ci augmenté d'une unité. Soit ci ce
nombre de comparaisons. On a
ci = 1 + card {aj | aj > ai, j < i }
Pour la permutation a correspondant à la suite à
trier, dont le nombre d'inversions est inv(a), le nombre
total de comparaisons pour le tri par insertion est
D'où le nombre moyen de comparaisons
Bien que l'ordre de grandeur soit toujours N2, ce tri est plus
efficace que le tri par sélection. De plus, il a la bonne propriété
que le nombre d'opérations dépend fortement de l'ordre initial du
tableau. Dans le cas où le tableau est presque en ordre, il y a peu
d'inversions et très peu d'opérations sont nécessaires,
contrairement aux deux méthodes de tri précédentes. Le tri par
insertion est donc un bon tri si le tableau à trier a de bonnes
chances d'être presque ordonné.
Une variante du tri par insertion est un tri dû à D. L. Shell en
1959, c'est une méthode de tri que l'on peut sauter en première
lecture. Son principe est d'éviter d'avoir à faire de longues
chaînes de déplacements si l'élément à insérer est très petit.
Nous laissons le lecteur fanatique en comprendre le sens, et le
mentionnons à titre anecdotique. Au lieu de comparer les éléments
adjacents pour l'insertion, on les compare tous les ..., 1093, 364,
121, 40, 13, 4, et 1 éléments. (On utilise la suite un+1 = 3 un
+ 1). Quand on finit par comparer des éléments consécutifs, ils
ont de bonnes chances d'être déjà dans l'ordre. On peut montrer
que le tri Shell ne fait pas plus que O(N3/2) comparaisons, et se
comporte donc bien sur des fichiers de taille raisonnable (5000
éléments). La démonstration est compliquée, et nous la laissons en
exercice difficile. On peut prendre tout autre générateur que 3 pour
générer les séquences à explorer. Pratt a montré que pour des
séquences de la forme 2p 3q, le coût est O(n log2 n) dans le
pire cas (mais il est coûteux de mettre cette séquence des 2p 3q
dans l'ordre). Dans le cas général, le coût (dans le cas le pire)
du tri Shell est toujours un problème ouvert. Le tri Shell est très
facile à programmer et très efficace en pratique (c'est le tri
utilisé dans le noyau Maple).
static void triShell() {
int h = 1; do
h = 3*h + 1;
while ( h <= N );
do {
h = h / 3;
for (int i = h; i < N; ++i)
if (a[i] < a[i-h]) {
int v = a[i], j = i;
do {
a[j] = a[j-h];
j = j - h;
} while (j >= h && a[j-h] > v);
a[j] = v;
}
} while ( h > 1);
}
1.2 Recherche en table
Avec les tableaux, on peut aussi faire des tables. Une table contient
des informations sur certaines clés. Par exemple, la table peut être
un annuaire téléphonique. Les clés sont les noms des abonnés.
L'information à rechercher est le numéro de téléphone. Une table
est donc un ensemble de paires á nom, numéro
ñ. Il y a plusieurs manières d'organiser cette table: un
tableau d'enregistrement, une liste ou un arbre (comme nous le verrons
plus tard). Pour l'instant, nous supposons la table décrite par deux
tableaux nom et tel, indicés en parallèle, le numéro
de téléphone de nom[i] étant tel[i].
Figure 1.4 : Un exemple de table pour la recherche en table
1.2.1 La recherche séquentielle
La première méthode pour rechercher un numéro de téléphone
consiste à faire une recherche séquentielle (ou linéaire). On
examine successivement tous les éléments de la table et on regarde
si on trouve un abonné du nom voulu. Ainsi
static int recherche (String x) {
for (int i = 0; i < N; ++i)
if (x.equals(nom[i]))
return tel[i];
return -1;
}
qui peut aussi s'écrire
static int recherche (String x) {
int i = 0;
while (i < N && !x.equals(nom[i]))
++i;
if (i < N)
return tel[i];
else
return -1;
}
Si on a la place, une autre possibilité est de mettre une sentinelle au bout de la table.
static int recherche (String x) {
int i = 0;
nom[N] = x; tel[N] = -1;
while (! x.equals(nom[i]))
++i;
return tel[i];
}
L'écriture de la
procédure de recherche dans la table des noms est alors
plus efficace, car on peut remarquer
que l'on ne fait plus qu'un test là où on en faisait deux. La
recherche séquentielle est aussi appelée recherche linéaire, car il
est facile de montrer que l'on fait N/2 opérations en moyenne, et
N opérations dans le pire cas. Sur une table de 10000
éléments, la recherche prend 5000 opérations en moyenne, soit 5ms.
Voici un programme complet utilisant la recherche linéaire en table.
class Table {
final static int N = 6;
static String nom[] = new String[N+1];
static int tel[] = new int[N+1];
static void initialisation() {
nom[0] = "paul"; tel[0] = 2811;
nom[1] = "roger"; tel[1] = 4501;
nom[2] = "laure"; tel[2] = 2701;
nom[3] = "anne"; tel[3] = 2702;
nom[4] = "pierre"; tel[4] = 2805;
nom[5] = "yves"; tel[5] = 2806;
}
static int recherche (String x) {
for (int i = 0; i < N; ++i)
if (x.equals(nom[i]))
return tel[i];
return -1;
}
public static void main (String args[]) {
Initialisation();
if (args.length == 1)
System.out.println (Recherche(args[0]));
}
}
1.2.2 La recherche dichotomique
Une autre technique de recherche en
table est la recherche dichotomique. Supposons que la table des
noms soit triée en ordre alphabétique (comme l'annuaire des PTT). Au
lieu de rechercher séquentiellement, on compare la clé à chercher
au nom qui se trouve au milieu de la table des noms. Si c'est le
même, on retourne le numéro de téléphone du milieu, sinon on
recommence sur la première moitié (ou la deuxième) si le nom
recherché est plus petit (ou plus grand) que le nom rangé au milieu
de la table. Ainsi
static void initialisation() {
nom[0] = "anne"; tel[0] = 2702;
nom[1] = "laure"; tel[1] = 2701;
nom[2] = "paul"; tel[2] = 2811;
nom[3] = "pierre"; tel[3] = 2805;
nom[4] = "roger"; tel[4] = 4501;
nom[5] = "yves"; tel[5] = 2806;
}
static int rechercheDichotomique (String x) {
int i, g, d, cmp;
g = 0; d = N-1;
do {
i = (g + d) / 2;
cmp = x.compareTo(nom[i]);
if (cmp == 0)
return tel[i];
if (cmp < 0)
d = i - 1;
else
g = i + 1;
} while (g <= d);
return -1;
}
Le nombre CN de comparaisons pour une table de taille N est
tel que CN = 1 + Cë N/2 û et C0 = 1. Donc
CN » log2(N).
(Dorénavant, log2(N) sera simplement écrit log N.) Si la
table a 10000 éléments, on aura CN » 14. C'est donc un gain
sensible par rapport aux 5000 opérations nécessaires pour la
recherche linéaire. Bien sûr, la recherche linéaire est plus simple
à programmer, et sera donc utilisée pour les petites tables. Pour des
tables plus importantes, la recherche dichotomique est plus
intéressante.
On peut montrer qu'un temps sub-logarithmique est possible si on
connaît la distribution des objets. Par exemple, dans l'annuaire du
téléphone, ou dans un dictionnaire, on sait a priori qu'un nom
commençant par la lettre V se trouvera plutôt vers la fin. En
supposant la distribution uniforme, on peut faire une règle de trois
pour trouver l'indice de l'élément de référence pour la
comparaison, au lieu de choisir le milieu, et on suit le reste de
l'algorithme de la recherche dichotomique. Cette méthode est la recherche par interpolation.
Alors le temps de recherche est en
O(log log N), c'est-à-dire 4 opérations pour une table de 10000
éléments, et 5 opérations jusqu'à 109 entrées dans la table!
1.2.3 Insertion dans une table
Dans la recherche linéaire ou par dichotomie, on ne s'est pas
préoccupé de l'insertion dans la table d'éléments nouveaux. C'est
par exemple très peu souvent le cas pour un annuaire téléphonique.
Mais cela peut être fréquent dans d'autres utilisations, comme la
table des usagers d'un système informatique. Essayons de voir comment
organiser l'insertion d'éléments nouveaux dans une table, dans le
cas des recherches séquentielle et dichotomique.
Pour le cas séquentiel, il suffit de rajouter au bout de la table
l'élément nouveau, s'il y a la place. S'il n'y a pas de place, on
appelle une procédure erreur qui imprimera le message d'erreur
donné en paramètre et arrêtera le programme (cf. page
X). Ainsi
void insertion (String x, int val) {
++n;
if (n >= N) then
erreur ("De'bordement de la table");
nom[n] = x;
tel[n] = val;
}
L'insertion se fait donc en temps constant, en O(1). Dans
le cas de la recherche par dichotomie, il faut maintenir la table
ordonnée. Pour insérer un nouvel élément dans la table, il faut
d'abord trouver son emplacement par une recherche dichotomique (ou
séquentielle), puis pousser tous les éléments derrière lui pour
pouvoir insérer le nouvel élément au bon endroit. Cela peut donc
prendre log n + n opérations. L'insertion dans une table ordonnée
de n éléments prend donc un temps O(n).
1.2.4 Hachage
Une autre méthode de recherche en table est le hachage. On
utilise une fonction h de l'ensemble des clés (souvent des chaînes
de caractères) dans un intervalle d'entiers. Pour une clé x,
h(x) est l'endroit où l'on trouve x dans la table. Tout se passe
parfaitement bien si h est une application injective. Pratiquement,
on ne peut arriver à atteindre ce résultat. On tente alors de s'en
approcher et on cherche aussi à minimiser le temps de calcul de
h(x). Ainsi un exemple de fonction de hachage est
h(x) = (x[1] × Bl-1 + x[2] × Bl-2 + ··· + x[l]) mod N
On prend d'habitude B = 128 ou B = 256 et on suppose que la taille
de la table N est un nombre premier. Pourquoi? D'abord, il faut
connaître la structure des ordinateurs pour comprendre le choix de
B comme une puissance de 2. En effet, les multiplications par des
puissances de 2 peuvent se faire très facilement par des décalages,
puisque les nombres sont représentés en base 2. En général, dans
les machines ``modernes'', cette opération est nettement plus rapide
que la multiplication par un nombre arbitraire. Quant à prendre N
premier, c'est pour éviter toute interférence entre les
multiplications par B et la division par N. En effet, si par
exemple B=N=256, alors h(x) = x[l] et la fonction h ne
dépendrait que du dernier caractère de x. Le but est donc d'avoir
une fonction h de hachage simple à calculer et ayant une bonne
distribution sur l'intervalle [0,N-1]. (Attention: il sera
techniquement plus simple dans cette section sur le hachage de
supposer que les indices des tableaux varient sur [0, N-1] au lieu
de [1, N]). Le calcul de la fonction h se fait par la fonction
h(x, l), où l est la longueur de la chaîne x,
static int h (String x) {
int r = 0;
for (int i = 0; i < x.length(); ++i)
r = ((r * B) + x.charAt(i)) % N;
return r;
}
Donc la fonction h donne pour toute clé x une entrée possible
dans la table. On peut alors vérifier si x =
nom[h(x)]. Si oui, la recherche est terminée. Si non,
cela signifie que la table contient une autre clé x' telle que
h(x') = h(x). On dit alors qu'il y a une collision,
et la
table doit pouvoir gérer les collisions. Une méthode simple est de
lister les collisions dans une table col parallèle à la table
nom. La table des collisions donnera une autre
entrée i dans la table des noms où peut se trouver la clé
recherchée. Si on ne trouve pas la valeur x à cette nouvelle
entrée i, on continuera avec l'entrée i' donnée par i' =
col[i]. Et on continue tant que col[i]
¹ -1. La recherche est donnée par
static int recherche (String x) {
for (int i = h(x); i != -1; i = col[i])
if (x.equals(nom[i]))
return tel[i];
return -1;
}
Figure 1.5 : Hachage par collisions séparées
Ainsi la procédure de recherche prend un temps au plus
égal à la longueur moyenne des classes d'équivalence définies sur
la table par la valeur de h(x), c'est-à-dire à la longueur
moyenne des listes de collisions. Si la fonction de hachage est
parfaitement uniforme, il n'y aura pas de collision et on atteindra
tout élément en une comparaison. Ce cas est très peu probable. Il y
a des algorithmes compliqués pour trouver une fonction de hachage
parfaite sur une table donnée et fixe. Mais si le nombre moyen
d'éléments ayant même valeur de hachage est k = N / M, où M
est grosso modo le nombre de classes d'équivalences définies par
h, la recherche prendra un temps N / M. Le hachage ne fait donc
que réduire d'un facteur constant le temps pris par la recherche
séquentielle. L'intérêt du hachage est qu'il est souvent très
efficace, tout en étant simple à programmer.
L'insertion dans une table avec le hachage précédent est plus
délicate. En effet, on devrait rapidement fusionner des classes
d'équivalences de la fonction de hachage, car il faut bien mettre les
objets à insérer à une certaine entrée dans la table qui
correspond elle-même à une valeur possible de la fonction de
hachage. Une solution simple est de supposer la table de taille n
telle que N £ n £ Nmax. Pour insérer un nouvel
élément, on regarde si l'entrée calculée par la fonction h est
libre, sinon on met le nouvel élément au bout de la table, et on
chaîne les collisions entre elles par un nouveau tableau col.
(Les tableaux nom, tel et col sont maintenant de
taille Nmax). On peut choisir de mettre le nouvel élément en
tête ou à la fin de la liste des collisions; ici on le mettra en
tête. Remarque: à la page X, tous les
outils seront développés pour enchaîner les collisions par des
listes; comme nous ne connaissons actuellement que les tableaux comme
structure de donnée, nous utilisons le tableau col.
L'insertion d'un nouvel élément dans la table s'écrit
static void insertion (String x, int val) {
int i = h(x);
if (nom[i] == null) {
nom[i] = x;
tel[i] = val;
} else
if (n >= Nmax)
erreur ("Débordement de la table");
else {
nom[n] = x;
tel[n] = val;
col[n] = col[i]; // On met la nouvelle entrée en tête
col[i] = n; // de la liste des collisions de sa
++n; // classe d'équivalence.
}
}
Au début, on suppose n = N,
nom[i] = "" (chaîne vide) et col[i] = -1
pour 0 £ i < N . La procédure d'insertion est donc très
rapide et prend un temps constant O(1).
Une autre technique de hachage est de faire un hachage à
adressage ouvert. Le principe en est très simple. Au lieu de gérer
des collisions, si on voit une entrée occupée lors de l'insertion,
on range la clé à l'entrée suivante (modulo la taille de la table).
On suppose une valeur interdite dans les clés, par exemple la chaîne
vide '', pour désigner une entrée libre dans la table. Les
procédures d'insertion et de recherche s'écrivent très simplement
comme suit
Figure 1.6 : Hachage par adressage ouvert
static int recherche (String x) {
int i = h(x);
while (nom[i] != null) {
if (x.equals(nom[i]))
return tel[i];
i = (i+1) % N;
}
return -1;
}
static void insertion (String x, int val) {
int i;
if (n >= N)
erreur ("De'bordement de la table");
++n;
i = h(x);
while ((nom[i] != null) && ! x.equals(nom[i]))
i = (i+1) % N;
nom[i] = x;
tel[i] = val;
}
Dans le cas où la clé à insérer se trouverait déjà
dans la table, l'ancien numéro de téléphone est écrasé, ce qui
est ce que l'on veut dans le cas présent. Il est intéressant de
reprendre les méthodes de recherche en table déjà vues et de se
poser ce problème. Plus intéressant, on peut se demander si cette
méthode simple de hachage linéaire est très efficace, et si on ne
risque pas, en fait, d'aboutir à une recherche séquentielle
standard. Notre problème est donc de comprendre la contiguïté de la
fonction de hachage, et la chance que l'on peut avoir pour une valeur
donnée de h(x) d'avoir aussi les entrées h(x) + 1, h(x) + 2,
h(x) + 3 ... occupées. On peut démontrer que, si la fonction de
hachage est uniforme et si a =
n/Nmax est le taux d'occupation de la
table, le nombre d'opérations est:
- 1/2+1/(2(1-a)) pour une recherche avec succès,
- 1/2+1/(2(1-a)2) pour une recherche avec échec.
Donc si a=2/3, on fait 2 ou 5 opérations, si
a=90%, on en fait 5 ou 50. La conclusion est donc que, si on
est prêt à grossir la table de 50%, le temps de recherche est très
bon, avec une méthode de programmation très simple.
Une méthode plus subtile, que l'on peut ignorer en première lecture,
est d'optimiser le hachage à adressage ouvert précédent en
introduisant un deuxième niveau de hachage. Ainsi au lieu de
considérer l'élément suivant dans les procédures de recherche et
d'insertion, on changera les instructions
i := (i+1) mod Nmax;
en
i := (i+u) mod Nmax;
où u = h2 (x, l) est une deuxième
fonction de hachage. Pour éviter des phénomènes de périodicité,
il vaut mieux prendre u et Nmax
premiers entre eux. Une méthode simple, comme Nmax
est déjà supposé premier, est de faire u <
Nmax. Par exemple, h2(x, l) = 8 - (x[l] mod 8)
est une fonction rapide à calculer, et qui tient compte des trois
derniers bits de x. On peut se mettre toujours dans le cas de
distributions uniformes, et de fonctions h et h2
``indépendantes''. Alors on montre que le nombre d'opérations est en
moyenne:
- (1/a) × log(1 / (1 - a)) pour une recherche
avec succès,
- 1/(1 - a) pour une recherche avec échec,
en fonction du taux d'occupation a de la table.
Numériquement, pour a = 80%, on fait 3 ou 5 opérations, pour
a = 99%, on fait 7 ou 100. Ce qui est tout à fait
raisonnable.
Le hachage est très utilisé pour les correcteurs d'orthographe.
McIlroy1
a calculé que, dans un article scientifique typique, il
y a environ 20 erreurs d'orthographe (c'est-à-dire des mots
n'apparaissant pas dans un dictionnaire), et qu'une collision pour 100
papiers est acceptable. Il suffit donc de faire un correcteur
probabiliste qui ne risque de se tromper qu'un cas sur 2000. Au lieu
de garder tout le dictionnaire en mémoire, et donc consommer beaucoup
de place, il a utilisé un tableau de n bits. Il calcule k
fonctions hi de hachage indépendantes pour tout mot w, et
regarde si les k bits positionnés en hi(w) valent simultanément
1. On est alors sûr qu'un mot n'est pas dans le dictionnaire si la
réponse est négative, mais on pense qu'on a de bonnes chances qu'il
y soit si la réponse est oui. Un calcul simple montre que la
probabilité P pour qu'un mot d'un dictionnaire de d entrées ne
positionne pas un bit donné est P = e-dk/n. La probabilité pour
qu'une chaîne quelconque soit reconnue comme un mot du dictionnaire
est (1-P)k. Si on veut que cette dernière vaille 1/2000, il
suffit de prendre P = 1/2 et k = 11. On a alors n/d = k/ln 2 =
15,87. Pour un dictionnaire de 25000 mots, il faut donc 400000 bits
(50 kO), et, pour un de 200000 mots, if faut 3200000 bits (400 kO).
McIlroy avait un pdp11 et 50 kO était insupportable. Il a compressé
la table en ne stockant que les nombres de 0 entre deux 1, ce qui a
ramené la taille à 30 kO. Actuellement, la commande spell
du système Unix utilise k = 11 et une table de
400000 bits.2
1.3 Programmes en Caml
(* Tri par sélection, page X *)
#open "printf";;
let nMax = 10;;
let a = make_vect nMax 0;;
let initialisation () =
for i = 0 to nMax - 1 do
a.(i) <- random__int 100
done;;
let impression () =
for i = 0 to nMax - 1 do
printf "%3d " a.(i)
done;
printf "\n";;
let tri_sélection () =
let min = ref 0 in
for i = 0 to nMax - 2 do
min := i;
for j = i + 1 to nMax - 1 do
if a.(j) < a.(!min) then min := j
done;
let t = a.(!min) in
a.(!min) <- a.(i); a.(i) <- t
done;;
let main () =
(* On initialise le tableau *)
initialisation ();
(* On trie *)
tri_sélection* ();
(* On imprime le résultat *)
impression ();
exit 0;;
(* Style plus Caml *)
let initialisation a =
for i = 0 to vect_length a - 1 do
a.(i) <- random__int 100
done;;
let impression a =
for i = 0 to vect_length a - 1 do
print_int a.(i); print_string " ";
done;
print_newline();;
let main () =
let a = make_vect nMax 0 in
initialisation (a);
tri_sélection (a);
impression (a);
exit 0;;
(* Tri bulle, voir page X *)
let tri_bulle a =
let j = ref 0 in
let v = ref 0 in
for i = vect_length a - 1 downto 0 do
for j = 1 to i do
if a.(j-1) > a.(j) then let t = ref a.(j-1) in begin
a.(j-1) <- a.(j); a.(j) <- !t
end
done
done;;
(* Tri par insertion, voir page X *)
let tri_insertion a =
let j = ref 0 in
let v = ref 0 in
for i = 1 to vect_length a - 1 do
v := a.(i); j := i;
while !j > 0 && a.(!j - 1) > !v do
a.(!j) <- a.(!j - 1);
decr j
done;
a.(!j) <- !v;
done;;
(* Tri Shell, voir page X *)
let tri_shell a =
let h = ref 1 in
while !h <= vect_length a - 1 do
h := 3 * !h + 1
done;
while !h > 1 do
h := !h / 3;
for i = !h to vect_length a - 1 do
if a.(i) < a.(i - !h) then begin
let v = a.(i) in
let j = ref i in
while !j >= !h && a.(!j - !h) > v do
a.(!j) <- a.(!j - !h);
j := !j - !h
done;
a.(!j) <- v
end
done
done;;
(* Recherche 1, voir page X *)
exception Found of int;;
let recherche s bottin =
try
for i = 0 to vect_length bottin - 1 do
let nom, tel = bottin.(i) in
if nom = s then raise (Found tel)
done;
raise Not_found
with Found tel -> tel;;
(* Recherche 3, voir page X *)
let recherche s bottin =
nom.(vect_length nom - 1) <- (s, 0);
let i = ref 0 in
while fst (bottin.(!i)) <> s do
incr i
done;
if !i = vect_length bottin
then raise Not_found
else
let _, tel = bottin.(!i) in tel;;
exception Found of int;;
let bottin =
[| "paul", 2811;
"roger", 4501;
"laure", 2701;
"anne", 2702;
"pierre", 2805;
"yves", 2806
|];;
// Encore une autre manière d'écrire la fonction recherche
let recherche s bottin = begin
try
do_vect
(function nom, tel ->
if nom = s then raise (Found tel))
bottin;
raise Not_found
with Found t -> t
end;;
(* Lecture des données *)
while true do
printf "%d\n"
(recherche (input_line stdin) bottin)
done;;
(* Recherche dichotomique, voir page X *)
let nom =
[| "anne"; "laure"; "paul";
"pierre"; "roger"; "yves" |];;
let tel =
[| 2702; 2701; 2811;
2805; 4501; 2806 |];;
let recherche_dichotomique x =
let g = ref 0
and d = ref (vect_length nom - 1)
and i = ref 0 in
while x <> nom.(!i) && !g <= !d do
i := (!g + !d) / 2;
if x < nom.(!i) then d := !i - 1
else g := !i + 1;
done;
if x = nom.(!i) then tel.(!i) else (-1);;
(* Insertion 1, voir page X *)
let n = ref 0;;
let insertion x val =
if !n >= vect_length nom
then failwith "Débordement de la table";
nom.(n) <- x;
tel.(n) <- val;
incr n;;
(* Fonction de hachage, voir page X *)
let N = vect_length nom - 1
and B = 128;;
let h s =
let result = ref 0 in
for i = 0 to string_length s - 1 do
result :=
(!result * B + (int_of_char (s.[i]))) mod N
done;
!result;;
(* Recherche avec hachage, voir page X *)
let col = make_vect (vect_length nom) (-1);;
let recherche x =
let i = ref (h x) in
while nom.(!i) <> x &&
col.(!i) <> -1
do i := col.(!i) done;
if x = nom.(!i) then tel.(!i) else -1;;
(* Insertion avec hachage, voir page X *)
let nom = make_vect nMax "";;
let tel = make_vect nMax 0;;
let col = make_vect nMax (-1);;
let n = ref 0;;
let insertion x val =
let i = h x in
if nom.(i) = "" then begin
nom.(i) <- x;
tel.(i) <- val
end else begin
if !n >= nMax
then failwith "Débordement de la table"
else begin
nom.(!n) <- x;
tel.(!n) <- val;
col.(!n) <- col.(i); (* On met la nouvelle entrée en tête *)
col.(i) <- !n; (* de la liste des collisions *)
incr n (* de sa classe d'équivalence *)
end;
end;;
(* Hachage avec adressage ouvert, voir page X *)
let recherche x =
let i = ref (h x) in
while nom.(!i) <> x && nom.(!i) <> "" do
i := (!i + 1) mod N
done;
if nom.(!i) = x then tel.(!i) else -1;;
let insertion x val =
if !n > N
then failwith "Débordement de la table";
incr n;
let i = ref (h x) in
while nom.(!i) <> x && nom.(!i) <> "" do
i := (!i + 1) mod N
done;
nom.(!i) <- x;
tel.(!i) <- val;;
- 1
- Doug McIlroy était le chef de l'équipe
qui a fait le système Unix à Bell
laboratories.
- 2
- Paul Zimmermann a remarqué que les
dictionnaires français sont plus longs que les dictionnaires anglais
à cause des conjugaisons des verbes. Il a reprogrammé la commande
spell en français en utilisant des arbres digitaux qui
partagent les préfixes et suffixes des mots d'un dictionnaire
français de 200000 mots Le dictionnaire tient alors dans une mémoire
de 500 kO. Son algorithme est aussi rapide et exact (non probabiliste).
