Tri lexicographique

L'ordre lexicographique

Introduction

Nous avons déjà observé que trier des objets suppose que l'on dispose d'une relation d'ordre définie sur ces objets et qui plus est totale. Nous avons majoritairement utilisé l'ordre naturel pour il­lus­trer les algorithmes de tri.

Il n'est pas rare que l'on ait à trier des listes d'objets disposants de plusieurs attributs. Considérons par exemple une liste de couples $(T,P)$ contenant une température $T$ (en degrés Celsius) et une pression $P$ (en Pascals). En limitant la précision des mesures à un entier, ces deux attributs sont munis de la relation d'ordre naturel. On peut trier une telle liste selon la température ou la pression, mais dans ce cas l'autre attribut est tout bonnement ignoré dans le tri et ce n'est pas ce que l'on souhaite.

Une première idée consiste à comparer les couples terme à terme, autrement dit on définit une relation $⪯$ sur l'ensemble des couples $(T,P)$ par : $$\begin{array}{}\text{(1)}& (T,P)⪯(T^{\prime },P^{\prime })\iff (T⩽T^{\prime })\wedge (P⩽P^{\prime }).\end{array}$$

On vérifie aisément que cette relation est réflexive, anti-symétrique et transitive, il s'agit de l'ordre produit. Cette relation se généralise à des $n$-uplets d'un produit cartésien $E_1\times E_2\times \cdots \times E_n$ d'en­sem­bles totalement ordonnés $(E_i,{⪯}_i)$. Malheureusement cette relation d'ordre n'est que partielle, en effet on ne peut pas comparer les couples $(4,3)$ et $(2,5)$ par exemple. Une autre cons­truc­tion est né­ces­sai­re.

Une réponse possible à ce problème est la relation d'ordre lexicographique. C'est celle que nous utilisons pour ranger les mots dans un dictionnaire ou pour classer les nombres réels quand ils sont représentés à l'aide de leurs développements décimaux. L'idée est naturelle, on part d'une liste $L$ de $n$-uplets d'un produit cartésien $E_1\times E_2\times \cdots \times E_n$ d'ensembles totalement ordonnés $(E_i,{⪯}_i)$ et on trie cette liste une première fois suivant la première composante. On partitionne alors la nouvelle liste $L$ en sous-listes contiguës selon la valeur de la première composante (leur concaténation est donc la liste $L$). On trie alors chacune de ces sous-listes à l'aide d'un algorithme de tri stable suivant la seconde composante. On recommence le même procédé sur chacune de ces sous-listes pour la composante suivante, etc.

Notons dès à présent que la méthode de tri présentée dans l'exemple ci-dessus n'a rien de simple à cause des segmentations successives des listes manipulées. Nous verrons à la section suivante comment faire mieux. D'autre part, l'ordre lexicographique tel qu'il vient d'être présenté n e permet de comparer que deux séquences de même longueur, alors que nous savons comparer des mots d'un dictionnaire ou des nombres réels*grâce à leurs développements décimaux illimités, sans que leurs longueurs soient égales.

Formalisation

On rappelle que si $⩽$ est une relation d'ordre, alors $<$ désigne l'ordre strict associé à $⩽$. On va définir une relation d'ordre sur la réunion de produits cartésiens finis d'ensembles totalement ordonnés. On rappelle que si $n$ est un entier naturel, on note $[n]:=⟦1,n⟧$.

La condition $(\text{3})$ exprime formellement que $x⪯y$ si et seulement $x$ est un préfixe de $y$ ou s'il existe un rang $k$ en deça duquel les termes de $x$ et $y$ sont égaux et tel que $x_k{\prec }_k{y}_k$.

En pratique, l'ordre lexicographique est souvent utilisé sur des $X_i$ tous identiques et munis de la même relation d'ordre, par exemple $X_i=\{0,1,2,\dots ,9\}$ muni de l'ordre naturel pour les dé­ve­lop­pe­ments décimaux illimités dans la représentation des nombres réels, ou encore $X_i=\{a,b,c,\dots ,z\}$ muni de l'ordre alphabétique. Dans la suite nous nous intéresserons plus particulièrement aux mots d'un langage. Le formalisme est légèrement différent de celui que nous venons de présenter.

Un mot de $k$ lettres, au sens usuel du terme, étant une suite de $k$ lettres, il n'y a pas de gros efforts à faire pour transposer le concept dans le langage mathématique. Pour cela, on se donne un ensemble fini $A=\{a_1,\dots ,a_q\}$ appelé alphabet à $q$ éléments $a_i$ qui sont les lettres ou les symboles de l'alphabet. Par convention on suppose que cet alphabet est muni d'une relation d'ordre total $⪯$ héritée de l'ordre naturel via l'application bijective et croissante $a$ : $$\mathrm{\forall }(i,j)\in {⟦1,q⟧}^{2}i⩽j\iff a_i⪯a_j.$$

Toute séquence $u$ de symboles de $A$ définit un mot et on appelle longueur du mot le nombre de ses symboles noté $|u|$ ou $\mathrm{\#}u$. Pour parfaire le modèle, on ne sépare pas les symboles de la suite et on écrira tout simplement $tranches$ pour la suite de symboles $t,r,a,n,c,h,e,s$.

On note $A^{\ast }$ l'ensemble (infini) de tous les mots possibles (qui remplace $X$ dans la définition $(\text{2})$). On équipe $A^{\ast }$ d'une loi de composition interne, la concaténation que l'on note comme un produit et qui associe à deux mots $u$ et $v$ le mot $u.v$ constitué des lettres de $u$ suivies par les lettres de $v$. Cette loi est associative et l'ajout d'un élément neutre $ϵ$ appelé mot vide font de $A^{\ast }$ un monoïde.

Nous ne fournissons pas d'exemples de comparaisons de deux mots selon l'ordre lexicographique*souvent confondu avec l'ordre alphabétique dans le langage courant, l'expérience du lecteur en la matière devrait suffire. L'objectif de cette section est de comprendre la formalisation à partir de la con­nais­san­ce pratique et non l'inverse.

Un algorithme

La relation d'ordre étant à présent total, on peut toujours comparer deux mots $u=u_1{u}_2\dots u_n$ et $v=v_1{v}_2\dots v_m$ de $A^{\ast },$ on aura donc $u⩽v$ ou $v<u,$ ce que l'on peut décomposer en 3 situations : $$(u=v)⊻(u<v)⊻(u>v).$$

La condition $(\text{3})$ suggère comment écrire l'algorithme. La première phase consiste à comparer terme-à-terme les symboles $u_i$ et $v_i$ de $u$ et $v$ en partant du premier symbole et avancer tant qu'ils sont identiques et qu'il reste des symboles à comparer. Plusieurs cas sont alors possibles en sortant de cette boucle :

1. On n'a atteint ni la fin de $u$ ni celle de $v$. Dans ce cas on peut décider si $u<v$ ou $v>u$ en comparant $u_i$ et $v_i$ suivant l'ordre alphabétique.
2. On a atteint la fin de l'un des deux mots, disons $u$ (le raisonnement est symétrique si c'est $v$). Dans ce cas, $u$ est préfixe de $v$ et on a $u⩽v$ et on peut décider si c'est $u<v$ ou $u=v$ selon qu'on a atteint ou non la fin de $v$ également.

L'algorithme ci-dessous renvoie l'une des trois valeurs $-1,$ $0$ ou $1$ selon que $u<v,$ $u=v$ ou que $u>v,$ respectivement.

      

          1
          ALGORITHME ComparaisonLexico(u,v):{-1,0,+1}
      
  
      

          2
          DONNEES
      
  
      

          3
             u, v: listes de caractères
      
  
      

          4
          VARIABLES
      
  
      

          5
             i: entier
      
  
      

          6
          DEBUT
      
  
      

          7
             i ← 1
      
  
      

          8
             TQ ((i ≤ |u|) ET (i ≤ |v|) ET (u[i] = v[i]) FAIRE
      
  
      

          9
                i ← i + 1
      
  
      

          10
             FTQ   
      
  
      

          11
             SI ((i > |u|) ET (i > |v|)) ALORS
      
  
      

          12
                RENVOYER  0 u = v
      
  
      

          13
             SINON SI ((i > |u|) OU ((i ≤ |v|) ET (u[i] < v[i]))) ALORS
      
  
      

          14
                RENVOYER -1 u < v
      
  
      

          15
             SINON SI ((i > |v|) OU ((i ≤ |u|) ET (u[i] > v[i]))) ALORS
      
  
      

          16
                RENVOYER +1  u > v
      
  
      

          17
             FSI
      
  
      

          18
          FIN
      
  

NB. Il faut noter que la justesse de l'algorithme dépend de l'hypothèse (toujours discutable) que l'interprétation d'une formule conjonctive (resp. disjonctive) s'arrête dès qu'une condition n'est pas satisfaite (resp. satisfaite).

Complexité

Nous allons évaluer la complexité de l'algorithme en fonction du nombre de comparaisons entre les lettres des deux mots. Notons $n:=|u|$ et $m:=|v|$. Dans le meilleur des cas, la première lettre suffit pour conclure, ainsi $\check{T}(n,m)=\mathrm{\Theta }(1)$ et dans le pire des cas il faut parcourir toutes les lettres du mot le plus court donc $\hat{T}(n,m)=\mathrm{\Theta }(min\{n,m\})$.

Le cas moyen, comme toujours, est plus délicat à obtenir. On suppose que $n⩽m$ et on partitionne l'ensemble $X$ des instances de tailles $n,m$ en fonction du nombre de lettres à comparer pour décider, ce nombre variant entre $1$ et $n+1,$ en effet, on tient compte de la situation où $u$ est un préfixe strict de $v$ auquel cas il faut une comparaison supplémentaire pour conclure, même s'il n'y a pas à proprement parler de lettre dans le mot le plus court. Notons $X_k$ la partie de $X$ contenant toutes les instances qui nécessitent $k$ comparaisons, $1⩽k⩽n+1.$ On a $$\begin{array}{}\text{(4)}& \overline{T}(n,m)=\frac{1}{|X|}\sum _{k=1}^{n+1}k|X_k|.\end{array}$$

Si l'alphabet est de taille $q$ alors $|X|=q^{n+m}$ puisqu'il s'agit du nombre de couples de mots de tailles $n$ et $m$ possibles. Dénombrons les ensembles $X_k$ pour $1⩽k⩽n,$ le cas particulier de la partie $X_{n+1}$ où $u$ est un préfixe de $v$ sera traité à part. Si la décision est prise en comparant $u_k$ et $v_k$ pour $1⩽k⩽n,$ cela signifie que les mots $u$ et $v$ ont un préfixe commun de $k-1$ lettres et que $u_k\ne v_k$. Le mot $u$ est arbitraire, on a donc $q^n$ possibilités pour $u$. Les $k-1$ premières lettres de $v$ sont fixées par celles de $u,$ la $k$-ème lettre $v_k$ doit être distincte de $u_k$ et les $m-k$ restantes sont quelconques, soit $(q-1)q^{m-k}$ possibilités pour constituer $v,$ finalement: $$\begin{array}{}\text{(5)}& \mathrm{\forall }k\in ⟦1,n⟧|X_k|=q^{n+m-k}(q-1).\end{array}$$ Il reste à calculer $|X{|}_{n+1}$. Dans ce cas $u$ est préfixe de $v$ et il y a $q^m$ possibilités pour constituer $v$ (mais une seule pour $u$), donc $$\begin{array}{}\text{(6)}& |X_{n+1}|=q^m.\end{array}$$

Notons, en guise de vérification, que la somme des cardinaux des $X_k$ est bien le cardinal de $X$: $$\begin{array}{rl}|X_{n+1}|+\sum _{k=1}^{n+1}|X_k|& =q^m+\sum _{k=1}^n{q}^{n+m-k}(q-1)\\ & =q^m+q^m(q-1)\sum _{k=1}^n{q}^{n-k}\\ & =q^m+q^m(q-1)\frac{q^n-1}{q-1}\\ & =q^{n+m}\\ & =|X|\end{array}$$

On peut remplacer les valeurs $|X{|}_k$ déterminées en ($\text{5}$) et ($\text{6}$) dans l'expression ($\text{4}$) pour obtenir $$\begin{array}{}\text{(7)}& \overline{T}(n,m)=\frac{(n+1)}{q^n}+(q-1)\underset{S(q^{-1})}{\underbrace{\sum _{k=1}^{n}k{q}^{-k}}}\end{array}$$

Et comme on devait s'y attendre, l'expression montre que la complexité ne dépend que de la plus petite des deux longueurs, ici $n$ par hypothèse. Il reste à évaluer la somme $S(q^{-1})$ et on applique la même preuve que celle du Lemme prouvé au chapitre Fonctions de complexité  :

Puisque la complexité ne dépend que de la longueur du plus petit mot, on peut alors conclure

NB. Il faut déduire de l'équation $(\text{8})$ que la moyenne du nombre de comparaisons entre lettres est asymp­to­ti­que­ment égale à $\frac{q}{q-1}$.

Algorithme du tri lexicographique

Présentation

On reprend les notations du chapitre Ordre lexicographique dans lequel nous avons défini une relation d'ordre totale sur l'ensemble $A^{\ast }$ des mots sur un alphabet fini $A:=\{a_1,a_2,\dots ,a_q\}$. Le tri par dénombrement n'est pas adapté à la situation, entre autres. Nous sommes en mesure d'appliquer les algorithmes de tri que nous avons déjà étudiés en remplaçant une liste de nombres par une liste de mots et l'ordre naturel par l'ordre lexicographique. Cependant, la nature particulière des objets à trier va nous permettre de développer une méthode plus adaptée, sous-entendu, plus rapide.

Supposons pour le moment que la liste de mots à trier contienne uniquement des mots de même longueur $l$ (nous verrons plus loin comment généraliser le processus à des listes de mots de longueurs différentes). Nous allons appliquer l'algorithme du tri par répartition TriRépartition $l$ fois sur la liste $L$ en triant successivement les mots de la liste selon leur $k$-ème lettre pour $k$ variant de $l$ à $1$ (voir l'exemple). Commençons par étudier un exemple élémentaire avec la liste de quatre mots $$L=[le,as,os,ai]$$ de longueur $l=2$.

Dans un premier temps nous trions les mots de la liste $L$ en fonction de leur deuxième lettre. En lisant la table suivante de la gauche vers la droite, on peut suivre l'évolution du contenu de cette liste et des différents casiers $C_{\alpha }$ (ceux qui ne sont pas utilisés sont omis), au fur et à mesure de l'avancement du tri par répartition. Le symbole $\bullet$ indique où va être rangé le prochain mot de la liste :

La concaténation des casiers $C_{\alpha }$ (y compris les casiers vides qui ne sont pas montrés) fournit une nouvelle liste $L=[le,ai,as,os]$. On recommence de la même façon, mais la comparaison se fait cette fois sur la première lettre :

Maintenant que toutes les lettres ont été comparées, la concaténation des casiers fournit la liste triée $$L=[ai,as,le,os].$$ Il peut sembler paradoxal de commencer par la dernière lettre plutôt que la première, mais la preuve du lemme suivant fournit l'explication. Pour faciliter la compréhension, quand nous ferons référence à la $(-k)$-ème lettre d'un mot $u=u_1{u}_2\dots u_l\in A^l,$ il s'agira de la $k$-ème lettre en partant de la fin du mot, ainsi $u[-1]=u[l]$ et plus généralement $u[-k]=u[l-k+1]$. D'autre part, on désigne par $u[k:]$ le suffixe $u_k{u}_{k+1}\dots u_l$ si $k⩽l$ et le mot vide $\epsilon$ si $k>l$. On a donc en particulier $u[1:]=u$.

À ce stade, nous ne sommes en mesure de trier que des mots de même longueur. Notons $l$ la longueur maximale des mots de la liste $L$. Pour généraliser l'algorithme à une liste de mots de longueurs différentes, on commence par répartir les mots de la liste $L$ dans $l$ listes $L_k,k\in [1,l]$ suivant leurs longueurs, les mots de longueur $k$ étant rangés dans la liste $L_k$. Cette opération est réalisée encore une fois par l'algorithme TriRépartition selon la longueur des mots. À l'issue de ce partitionnement la liste $L$ est vide.

Le tri consiste toujours à effectuer $l$ tris par répartition des mots de $L$ selon les symboles d'indice $l$ à $1$. La seule différence avec le tri lexicographique de mots de même longueur consiste, avant d'effectuer le prochain tri par répartition à l'indice $k,$ à insérer les mots de la liste $L_k$ au début de la liste $L$. Ainsi avant le premier tri par répartition sur les symboles à la position $k=l,$ on insère la liste $L_l$ à gauche de la liste $L,$ autrement dit la nouvelle liste $L$ est obtenue par concaténation de la liste $L_k$ et de l'ancienne liste $L$.

Il ne reste plus à présent qu'à articuler les deux opérations. L'algorithme opère donc en deux phases. La première phase partitionne la liste initiale $L$ en $l$ listes $L_k$ contenant tous les mots de longueur $k\in [1:l]$. La seconde phase applique $l$ fois l'algorithme du tri par répartition selon la $(k)$-ème lettre des mots, en partant de $k=l$ jusqu'à $k=1$.

      

          1
          ALGORITHME TriLexico(@L):liste
      
  
      

          2
          DONNEES
      
  
      

          3
             L: liste de mots
      
  
      

          4
          VARIABLES
      
  
      

          5
             P: liste   la partition en L_k
      
  
      

          6
             k: entier
      
  
      

          7
          DEBUT
      
  
      

          8
             P ← Partition(L)
      
  
      

          9
             k ← #P    #P = l
      
  
      

          10
             TQ k > 0 FAIRE
      
  
      

          11
                Concaténer(P[k],L)
      
  
      

          12
                TriRépartition(L,(u,k) ↦ j)  u_k = a_j
      
  
      

          13
                k ← k - 1
      
  
      

          14
             FTQ
      
  
      

          15
          FIN
      
  

La fonction d'adressage $(u,k)\mapsto j$ utilisée à instruction #12 est celle qui renvoie le numéro $j$ de la $k$-ème lettre $u_k$ du mot $u,$ i.e. telle que $u_k=a_j$.

Complexité

On rappelle que $q:=\mathrm{\#}A$. On note $n:=\mathrm{\#}L$ la longueur de la liste à trier, $n_i:=\mathrm{\#}{L}_i$ la longueur de la liste des mots de longueur $i$ et $\ell$ la longueur du mot le plus long. On a $$\begin{array}{}\text{(9)}& \sum _{i=1}^{\ell }{n}_i=n.\end{array}$$

L'algorithme Partition demande $\mathrm{\Theta }(n)$ opérations pour calculer la longueur maximale $m$ (instruction #9) puis $\mathrm{\Theta }(m)$ opérations pour initialiser les $m$ listes $L_i$ (instructions #11 à #14). La répartition des $n$ mots dans les $\ell$ casiers a un coût en $\mathrm{\Theta }(n),$ on a donc $$\begin{array}{}\text{(10)}& T_{\mathsf{\text{Partition}}}(n,\ell )=\mathrm{\Theta }(n)+\mathrm{\Theta }(\ell )\end{array}$$

L'algorithme TriRépartition a un coût de $\mathrm{\Theta }(q)$ pour initialiser les $q$ casiers à la liste vide, un coût de $\mathrm{\Theta }(\nu )$ pour répartir les $\nu$ éléments de la liste d'appel et un coût de $\mathrm{\Theta }(q)$ pour concaténer les $q$ casiers, soit au total $$\begin{array}{}\text{(11)}& T_{\mathsf{\text{Répartition}}}(\nu ,q)=\mathrm{\Theta }(\nu )+\mathrm{\Theta }(q)\end{array}$$

Pour évaluer la complexité de l'algorithme TriLexico, il nous reste à calculer le coût des $\ell$ appels successifs à l'algorithme de tri par répartition (instruction #12) pour chacune des $\ell$ listes $L_k$. Le $k$-ème appel se fait sur une liste dont la longueur $\nu$ est égale à $$n_m+n_{m-1}+\cdots +n_{m-k+1}$$ et donc majorée par la longueur $n$ de la liste initiale d'après ($\text{9}$), soit $O(n)$. On peut à présent conclure : $$\begin{array}{rl}{T}_{\mathsf{\text{TriLexico}}}(n,l,q)& =\mathrm{\Theta }(n)+\mathrm{\Theta }(l)\text{(instruction \#8)}\\ & +l\mathrm{\Theta }(1)\text{(instructions \#10, \#11 et \#13)}\\ & +l(O(n)+\mathrm{\Theta }(q))\text{(instruction \#12)}\\ & =O(ln)+\mathrm{\Theta }(lq)\end{array}$$ Le cardinal de l'alphabet étant constant et la longueur maximale $\ell$ des mots étant asymptotiquement négligeable devant la taille de la liste, on peut conclure que