Algorithmique ii - Ordre lexicographique

Présentation du problème

Nous avons déjà fait observer que trier des objets suppose implicitement que l'on dispose d'une relation d'ordre 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 \(\mathscr \preceq\) sur l'ensemble des couples \((T,P)\) par : \begin{equation} (T,P)\preceq(T',P')\Longleftrightarrow (T\leq T')\ \text{et}\ (P\leq P'). \end{equation} 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,\leq_i)\). Malheureusement cette relation d'ordre n'est que partielle, en effet on ne peut pas comparer les couples \((4,2017)\) et \((8,1789)\) par exemple. Une autre cons­truc­tion est nécessaire.

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,\leq_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 sur place suivant la seconde composante. On recommence le même procédé sur chacune de ces sous-listes pour la composante suivante, etc.

Considérons la liste \(L=((2,2,c),(3,2,b),(1,3,c),(3,2,a),(3,1,c),(1,2,a))\) dé­fi­nie sur le produit cartésien \(\bf N\times N\times{\mathscr A}\) où \(\bf N\) est muni de l'ordre naturel et \({\mathscr A}\) est l'al­pha­bet latin muni de l'ordre alphabétique. UnLe ré­sul­tat dépend de la mé­thode de tri choisie puis­qu'il ex­is­te plu­sieurs tri­plets de mê­me pre­miè­re valeur. premier tri suivant la première composante en­tiè­re pourrait fournir la liste \[\underbrace{(\textcolor{yellow}{1},3,c),(\textcolor{yellow}{1},2,a)}_{A_{\textcolor{yellow}{1}}},\underbrace{(\textcolor{yellow}{2},2,c)}_{B_{\textcolor{yellow}{2}}},\underbrace{(\textcolor{yellow}{3},2,b),(\textcolor{yellow}{3},2,a),(\textcolor{yellow}{3},1,c)}_{C_{\textcolor{yellow}{3}}}.\] Un second tri sur place de ces trois listes suivant la deuxième composante pourrait donner : \[\underbrace{\overbrace{(\textcolor{yellow}{1},\textcolor{orange}{2},a)}^{A_{\textcolor{yellow}{1},\textcolor{orange}{2}}},\overbrace{(\textcolor{yellow}{1},\textcolor{orange}{3},c)}^{A_{\textcolor{yellow}{1},\textcolor{orange}{3}}}}_{A_{\textcolor{yellow}{1}}\ \text{triée}},\underbrace{\overbrace{(\textcolor{yellow}{2},\textcolor{orange}{2},c)}^{B_{\textcolor{yellow}{2},\textcolor{orange}{2}}}}_{B_{\textcolor{yellow}{2}}\ \text{triée}},\underbrace{\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{1},c)}^{C_{\textcolor{yellow}{3},\textcolor{orange}{1}}},\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},b),(\textcolor{yellow}{3},\textcolor{orange}{2},a)}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2}}}}_{C_{\textcolor{yellow}{3}}\ \text{triée}}.\] Et un dernier tri sur la liste \(C_{\textcolor{yellow}{3},\textcolor{orange}{2}}\) suivant la dernière composante (les 4 premières listes ne contiennent plus qu'un élément) achèverait le processus : \[(\textcolor{yellow}{1},\textcolor{orange}{2},a),(\textcolor{yellow}{1},\textcolor{orange}{3},c),(\textcolor{yellow}{2},\textcolor{orange}{2},c),(\textcolor{yellow}{3},\textcolor{orange}{1},c),\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{a})}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{a}}},\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{b})}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{b}}}.\]

Notons dès à présent que la méthode de tri présentée dans l'exemple ci-dessus n'est pas des plus simple à cause des segmentations successives des listes manipulées. Nous verrons au chapitre suivant comment faire mieux. D'autre part, l'ordre lexicographique tel qu'il vient d'être présenté n'est pas aussi général que celui que nous connaissons de longue date, les mots d'un dictionnaire ou les développements décimaux des nombres réels ne sont pas nécessairement de même longueur. La généralisation à des séquences de longueurs différentes est un peu plus délicate à formaliser mais s'appuie sur le modèle de longueur fixe que nous allons décrire à présent.

Formalisation

Soit \(n\) un entier naturel non-nul et \((E_i,\leq_i)_{i\in[1,n]}\) une fa­mil­le d'en­sem­bles or­don­nés indexée par \([1,n]\). Soient \(x:=(x_1,x_2,\ldots,x_n)\) et \(y:=(y_1,y_2,\ldots,y_n)\) deux éléments du produit cartésien \(E:=E_1\times E_2\times\cdots\times E_n\). On définit une relation binaire \(\prec\) sur \(E\) par \begin{equation} x\prec_\times y\quad \Leftrightarrow\quad \exists j\in[1,n],\quad\forall i\in[1,j-1],\ x_i=y_i\quad \text {et}\quad x_j<_jy_j \end{equation} où \(<_j\) désigne l'ordre strict associé à la relation d'ordre \(\leq_i\) sur \(E_i\). Alors la relation binaire définie sur \(E\) par \begin{equation} x\preceq_\times y\quad \Leftrightarrow\quad x=y\ \ \text{ou}\ \ x\prec_\times y \end{equation} est une relation d'ordre appelée ordre le­xi­co­gra­phi­que et qui a la relation \(\prec\) pour ordre strict.

Démontrez que la relation \(\preceq\) ainsi définie est bien une relation d'ordre. Démontrez que si chacune des relations \(\leq_i\) est une relation d'ordre total, alors \(\preceq\) est également une relation d'ordre totale.

On peut à présent généraliser à des séquences de longueurs différentes. On part d'une famille infinie \((E_i,\leq_i)_{i\in{\bf N}}\) d'ensembles ordonnés. \begin{equation} \label{eq:defprodinf} E:=\bigcup_{k\in{\bf N}}\left(E_1\times E_2\times\cdots\times E_k\right). \end{equation}

Soient \(x=(x_1,x_2,\ldots,x_n)\) et \(y=(y_1,y_2,\ldots,y_m)\) deux éléments de \(E\) avec \((n,m)\in{\bf N}\times{\bf N}\) et \(p:=\min\{n,m\}\). On définit une relation binaire \(\prec\) sur \(E\) par \begin{equation} x \prec y \quad\Leftrightarrow \quad \begin{cases} (x_1,x_2,\ldots,x_p)\prec_\times (y_1,y_2,\ldots,y_p)&\\ \qquad\qquad\qquad\quad\text{ou}&\\ (x_1,x_2,\ldots,x_p) = (y_1,y_2,\ldots,y_p)\ \text{et}\ p < n.& \end{cases} \end{equation} Alors la relation binaire définie sur \(E\) par \begin{equation} x\preceq y\quad \Leftrightarrow\quad x=y\ \ \text{ou}\ \ x \prec y \end{equation} est une relation d'ordre appelée ordre le­xi­co­gra­phi­que et qui a la relation \(<\) pour ordre strict.

Reprenez les questions de l'exercice précédent pour ce dernier théorème.

On montre là aussi que l'ordre lexicographique est une relation d'ordre total si les relations d'ordre sur les \(E_i\) le sont. En pratique l'ordre lexicographique est utilisé sur des \(E_i\) tous identiques et munis de la même relation d'ordre, par exemple \(E_i=\{0,1,2,\ldots,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. 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,\ldots,a_{q}\}\) appelé alphabet à \(q\) éléments \(a_i\) appelés lettres (ou symboles). Par convention on suppose que cet alphabet est muni d'une relation d'ordre total \(\preceq\) héritée de l'ordre naturel via l'application bijective et croissante \(a\) : \[\forall (i,j)\in[1,q]\times[1,q],\quad i \leq j\ \Leftrightarrow a_i\preceq a_j.\] Toute suite finie (ou 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 \(\#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^*\) l'ensemble (infini) de tous les mots possibles (qui remplace \(E\) dans la définition \((\ref{eq:defprodinf})\)). On équipe \(A^*\) 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 \(\epsilon\) appelé mot vide font de \(A^*\) un monoïde. Il s'agit de la fermeture de Kleene de \(A\).

Si \(A = \{0,1\}\) alors \(A^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 100, ...\}\). Si \(A=\{a,b,\ldots,z\}\) est l'alphabet latin, la concaténation bon.jour des mots bon et jour est le mot bonjour (qui est différent de \(jourbon\), la loi n'est bien sûr pas commutative.)

Nous ne fournissons pas d'exemples de comparaisons de deux mots selon l'ordre lexicographique (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_1u_2\ldots u_n\) et \(v=v_1v_2\ldots v_m\) de \(A^*\), on aura donc \(u\leq v\) ou \(v < u\), ce qui se traduit par 3 situations :

  1. \(u = v\),
  2. \(u < v\),
  3. \(u > v\).

Commençons par le cas le plus simple. Si les deux mots \(u\) et \(v\) sont de même longueur, le premier théorème suggère une simple boucle pour décider quelle est la situation rencontrée. On compare terme-à-terme les symboles \(u_i\) et \(v_i\) de \(u\) et \(v\) en partant du premier symbole d'index \(i=1\). Tant que \(u_i=v_i\), on avance (\(i\leftarrow i +1\)) ; sinon \(u_i < v_i\) ou \(v_i < u_i\) soit respectivement \(u < v\) ou \(v < u\).

Si les longueurs sont différentes, l'algorithme est sensiblement le même et l'adaptation est fournie par le second théorème. Le processus diffère uniquement si l'un des deux mots est un préfixe de l'autre. Dans ce cas la boucle qui permet de comparer les symboles \(u_i\) et \(v_i\) atteint le dernier symbole du mot le plus court ce qui permet d'affirmer qu'il est le plus petit des deux mots (au sens de l'ordre le­xi­co­gra­phi­que).

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.

ComparaisonLexico(u,v):{-1,0,+1}
données
   u,v: listes de caractères
variables
   i,p: entiers
debut
   p ← min(#u,#v)
   i ← 1
   TQ (i ≤ p) ET (u[i] = v[i]) FAIRE
      i ← i + 1
   FTQ
   SI (i < p) ALORS
      SI (u[i] < v[i]) ALORS
          renvoyer -1 u < v
      SINON
          renvoyer +1 u > v
      FSI
   SINON
      SI (#u = #v) ALORS
         renvoyer 0; u = v
      SINON
         SI (#u < #v) ALORS 
            renvoyer -1  u < v 
         SINON 
            renvoyer +1  u > v
         FSI
      FSI
   FSI
FIN
Faites une preuve d'arrêt de cet algorithme. Démontrez que l'algorithme est valide.

Complexité

Nous allons évaluer la complexité en fonction du nombre de comparaisons sur les lettres. Notons \(n:=\#u\) et \(m:=\#v\). Dans le meilleur des cas la première lettre permet de conclure, donc \(\check T(n,m)=\Theta(1)\) et dans le pire des cas il faut parcourir toutes les lettres du mot le plus court donc \(\hat T(n,m)=\Theta(\min\{n,m\})\).

Le cas moyen, comme toujours, est plus délicat à obtenir. On suppose que \(n\leq m\) et on partitionne l'ensemble \(E\) des instances de tailles \(n,m\) en fonction du nombre de lettres à comparer pour décider, ce nombre variant entre \(1\) et \(n+1\) (on tient compte de la situation où \(u\) est un préfixe de \(v\) auquel cas il faut une comparaison de plus pour conclure même s'il n'y a pas à proprement parler de lettre). Notons \(E_k\) la partie de \(E\) contenant toutes les instances qui nécessitent \(k\) comparaisons, \(1\leq k\leq n+1.\) On a \begin{equation}\label{eq:compmoyenne} \bar T(n,m)=\frac{1}{\#E}\sum_{k=1}^{n+1}k.\#E_k \end{equation} Si l'alphabet est de taille \(q\) alors \(\#E=q^{n+m}\) puisqu'il s'agit du nombre de couples de mots de tailles \(n\) et \(m\) possibles. Dénombrons les ensembles \(E_k\) pour \(1\leq k\leq n\), le cas particulier de la partie \(E_{n+1}\) où \(u\) est préfixe de \(v\) sera traité à part. Si la décision est prise en comparant \(u_k\) et \(v_k\) pour \(1\leq k\leq n\), cela signifie que les mots \(u\) et \(v\) ont un préfixe commun de \(k-1\) lettres et que \(u_k\not=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{equation}\label{eq:Ek} \forall k,\ 1\leq k\leq n,\quad \#E_k = q^{n+m-k}(q-1). \end{equation} Il reste à calculer \(\#E_{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{equation}\label{eq:En} \#E_{n+1} = q^m \end{equation} Notons en guise de vérification que la somme des cardinaux des \(E_k\) est bien le cardinal de \(E\): \begin{align*} \#E_{n+1}+\sum_{k=1}^{n+1}\#E_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}\\ &=\#E \end{align*} On peut remplacer les valeurs \(\#E_k\) déterminées en (\ref{eq:Ek}) et (\ref{eq:En}) dans l'expression (\ref{eq:compmoyenne}) pour obtenir \begin{equation}\label{eq:compfinale} \bar T(n,m) = \frac{(n+1)}{q^n} + (q-1)\underbrace{\color{yellow}\sum_{k=1}^{n}kq^{-k}}_{\color{yellow}S(q^{-1})} \end{equation} 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 \(\color{yellow}S(q^{-1})\) et on applique la même preuve que celle du Lemme prouvé au chapitre Fonctions de complexité  :

\(S(q^{-1})= \displaystyle\frac{q^{n+1}-q(n+1)+n}{q^n(q-1)^2}\)

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

La complexité moyenne de la comparaison lexicographique entre deux mots de longueurs \(n\) et \(m\) est \begin{equation*} \bar T(n,m) = \frac{q}{q-1}-\frac{1}{q^{\min\{n,m\}}(q-1)} \end{equation*}
Il faut noter que le résultat est remarquable puisqu'en moyenne le nombre de comparaisons est asymptotiquement égal à \(q/(q-1)\).

Travaux pratiques

Écrivez une fonction Python PPL(u, v) qui renvoie 0 si \(u=v\), -1 si \(u < v\) et 1 si \(u > v\).

[Solution en C]
[Solution en Python]