La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | profil-zyak-2012 |
Nombre de lectures | 80 |
Langue | Français |
Extrait
HACHAGE, ARBRES, CHEMINS & GRAPHES
PHILIPPE CHASSAING ET PHILIPPE FLAJOLET
Math´ematiques discr`etes et continues se rencontrent et se compl`etent volontiers
harmonieusement. C’est cette th`ese que nous voudrions illustrer en discutant un
probl`eme classique aux ramifications nombreuses—l’analyse du hachage avec essais
lin´eaires. L’exemple est issu de l’analyse d’algorithmes,domaine fond´e par Knuth
et qui se situe lui-mˆeme “`acheval”entrel’informatique,l’analysecombinatoire,et
la th´eorie des probabilit´es. Lors de son traitement se croisent au fil du temps des
approches tr`es diverses,et l’on rencontrera des questions pos´ees par Ramanujan a`
Hardy en 1913,un travail d’´et´e de Knuth datant de 1962 et qui est a` l’origine de
l’analysed’algorithmeseninformatique,desrecherchesenanalysecombinatoiredu
statisticienKreweras,diversesrencontresaveclesmod`eles de graphes al´eatoires au
sens d’Erd¨ os et R´enyi,un peu d’analyse complexe et d’analyse asymptotique,des
arbresqu’onpeutvoircommeissusdeprocessusdeGalton-Watsonparticuliers,et,
pour finir,un peu de processus,dont l’ineffable mouvement Brownien! Tout ceci
contribuant in fine a` une compr´ehension tr`es pr´ecise d’un mod`ele simple d’al´ea
discret.
1. Hachage
Nous ferons commencer l’histoire par Knuth en 1962; Knuth a alors 24 ans et
h´ esite entre une carri`ere en math´ematiques discr`etes et une passion pour l’infor-
matique tr`es concr`ete. L’un des tous premiers probl`emes quantitatifs de la nais-
sante science informatique consiste `a comprendre comment se comporte une certaine
m´ ethode d’acc`es `a des donn´ees qui apparaˆıt comme pr´esentant au vu des simula-
´tions de tr`es bonnes caract´eristiques de complexit´e. L’Ecole de Feller est aussi “sur
1le coup” (dixit Knuth). Knuth apportera tr`es vite une solution `a ces questions
(`a partir de 1962) et,comme il le dit lui-mˆeme,c’est ce succ`es scientifique initial
qui d´eterminera tr`es largement la suite de sa carri`ere. Pour les informaticiens,
cette ´etape marque les d´ebuts de l’analyse math´ematique d’algorithmes (compren-
dre l’analyse des performances et de la complexit´e des algorithmes “discrets” de
l’informatique).
Voici donc le probl`eme. Imaginez que vous voulez ranger dans un fichier les noms,
num´ eros de t´el´ephones,etc,de vos amis. Vous disposez de m tiroirs et de n amis
(n≤ m). Dans un monde id´eal,chaqueamiverraitsesdonn´es rang´ees directement
dans un tiroir qui lui est propre et dont le num´ero est calculable (ais´ement) `a partir
du nom au moyen d’une fonction dite “de hachage”. L’utilisation du fichier est
en ce cas simple et rapide: ´etant donn´e le nom x,on calcule la valeur num´erique
“hach´ee” h(x),puis,dans la case h(x),on trouve au premier coup les donn´ees√
d´ esir´ees. Si n est bien plus petit que m,le paradoxe des anniversaires (une salle
de 23 personnes a de bonnes chances de contenir deux personnes ayant le mˆeme
Date: Le 15 Octobre 2001.
1Le manuscrit est disponible en http://algo.inria.fr/AofA/Research/11-97.html.
1
5
6
3>
4
<5
7>1>
2 PHILIPPE CHASSAING ET PHILIPPE FLAJOLET
anniversaire) implique qu’avec bonne probabilit´e le rangement soit possible sans
collisions. Une telle solution fond´ee sur un rangement “id´eal” est cependant peu
satisfaisante car il faudrait en gros pr´evoir un nombre de tiroirs qui soit de l’ordre
du carr´e de votre nombre d’amis!
En termes informatiques,on dispose d’une table T[1..m] dont chaque entr´ee
peut contenir une donn´ee et des informations auxiliaires. Les donn´ees sont issues
d’un universU (par exemple les chaines alphab´etiques de longueur au plus 20). On
2dispose d’une fonction h dite “fonction de hachage”: celle-ci envoye le domaineU,
29en g´en´eral tr`es grand (ici de cardinalit´e2· 10 ),sur un intervale beaucoup plus
2 6petit [1..m] (le nombre de cases ou tiroirs en g´en´eral entre 10 et 10 ). On range
alors chaque donn´ee x `a l’addresse h(x) dans la table. Pour r´egler les collisions qui
sont statistiquement in´evitables,lorsque la case de h(x) est d´ej`a prise,on choisit
de ranger x `a la premi`ere case disponible parmi 1 +h(x),2+ h(x),etc .. De plus,
dans la variante circulaire du proc´ed´e,on recommencera `a partir de la premi`ere
case (de num´ero 1) suite `aun´echec sur la case m. Ci-dessous,un exemple o`u
(m,n) = (10,7).
Il est en pratique tr`es raisonnable de supposer que les valeurs hach´ees sont uni-
form´ement distribu´ees sur l’intervalle [1,m]. L’hypoth`ese est v´erifi´ee pour peu que
la fonction de hachage “m´elange bien” les bits des donn´ees (voir par ex. Lum et al.
pour des v´erifications effectives sur bases de donn´ees industrielles). Knuth d´ecrit
le probl`eme en ces termes:
“A certain one-way street has m parking spaces in a row numbered 1 to m. A man
and his dozing wife drive by, and suddenly, she wakes up and orders him to park
immediately. He dutifully parks at the first available space [...].”
La question est alors de d´eterminer la distance attendue entre l’endroit ou` l’on
parque et l’endroit ou` l’on souhaitait s’arrˆeter initialement. Naturellement,on
s’attend a` ce que parquer dans une rue quasi-d´eserte (n = o(m)) soit facile,mais
que la situation se d´egrade lorsque la rue se remplit (n ≈ m). Mais comment?
On aura reconnu la` une version discr`ete du probl`eme de parking [30] lanc´e par
le probabiliste Alfr´ed R´enyi en 1958. Notons que le probl`eme s’exprime aussi en
termes de placement de n boules dans m urnes,chacune de capacit´e b = 1,mais
avec la contrainte non classique de d´ebordement a` droite des urnes.
2. L’analyse en moyenne
Une configuration de hachage est donc d´etermin´ee par une suite d’´elements
de {1,...,m} ayant longueur n,et,d’apr` es la discussion pr´ec´edente,l’hypoth`ese
nd’´equiprobabilit´e des m suites est bien justifi´ee. Le param`etre fondamental d’une
configuration est le “d´eplacement total” D d´ efini comme la somme (sur x) desm,n
2 Par exemple,h(x) interpr`etex comme un nombre en base 26, puis le r´eduit modulom.
3
<4<6
7
2>
1
2
HACHAGE, ARBRES, CHEMINS & GRAPHES 3
distances (circulaires) entre l’endroit ou` x est plac´e et la valeur de h(x). Cette
quantit´e est donc une variable al´eatoire qui d´ecrit pr´ecis´ement le coutˆ cumulatif de
nconstruction de la table. Sa variation se situe entre 0 et 0 + 1 +···+(n− 1) = .
2
Le premier r´esultat de Knuth,obtenu il y a pr`es de quarante ans,est le calcul
de l’esp´erance du d´eplacement total sous forme exacte:
n n− 1 (n− 1)(n− 2)
(1) E [D ]=n + + +... .m,n 22 m m
On distingue classiquement le cas ´epars (n→ +∞, n/m = α, 0<α<1) et le cas
presque plein (n→ +∞,n= m−1). Ceux-ci donnent alors lieu aux asymptotiques
suivantes:
n 1 n πn
(2) E [D ]∼ 1+ ,E [D ]∼ .m,n n+1,n
2 1−α 2 2
En substance (penser a` D − D ),ceci nous dit qu’il suffit en moyenne dem,n m,n−1
O(1) essais pour trouver une case vide tant que le taux de remplissage α est bien
s´epar´ede1,α<1,tandis que la situation se d´egrade d`es α approche 1. Ce,au
point que,pour une table pleine,le coˆ ut total de construction devient surlin´eaire,
√
de l’ordre de n n.
L’analyse de Knuth pour (1) commence par un “lemme cyclique”: il y a (m−
n−1n)m suites de hachage qui laissent la derni`ere case vide (preuve: grouper les
suites par ´equivalence vis `a vis des rotations). Le probl`eme ainsi lin´earis´e fait jouer
un rˆole particulier aux “fonctions de parking” d´efinies par le fait que la derni`ere
case, m,restevide,ainsiqu’auxallocations“presquepleines”(fonctionsdeparking
satisfaisant de plus a` n = m− 1). Elle se poursuit par une r´ecurrence sur n,en
prenant en compte le dernier ´el´ement ajout´e. Il est curieux que la simplification
des formules donnant l’esp´erance (1) passe par une version du th´eor`eme binomial
duea`Abel,soit,
rr k−1 r−k(x +y) = x(x−k) (y +k) .
k
k
Quant au probl`eme asymptotique associ´e,la forme de l’esp´erance,
n n− 1 (n− 1)(n− 2)
E[D ]= (Q(n)− 1) ou` Q(n):=1+ + +···,n,n 22 n n
devait s’av´erer avoir une digne histoire. De fait,la quantit´e Q(n) qui y figure
apparaˆıt d´ej` a de mani`ere d´eguis´ee dans la premi`ere lettre de Ramanujan a` Hardy
en date du 16 janvier 1913,sous forme de l’assertion suivante:
2 n1 n n n n 1 4 4 2“ e =1+ + +···+ θ, with θ = + , where k lies between and .”
2 1 2! n! 3 135+k 45 21
(Il s’agit donc en substance d’estimer tr`es finement la probabilit´