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 illustrer 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')\ \iff\ (T\leq T')\ \wedge\ (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'ensembles 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,3)\) et \((2,5)\) par exemple. Une autre construction 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 à 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'est pas des plus 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'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.
Formalisation
On rappelle que si \(\leq\) est une relation d'ordre, alors \(<\) désigne l'ordre strict associé à \(\leq\). On va définir une relation d'ordre sur la réunion de produits cartésiens finis d'ensembles totalement ordonnés.
La disjonction \((\ref{eq:condtl})\) exprime formellement que \(x\preceq y\) si et seulement s'il existe un rang \(k\) en deça duquel tous les termes de \(x\) et \(y\) sont égaux et tel que \(x_k < y_k\) ou que \(x\) est un préfixe de \(y\).
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éveloppements 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{\ab{1}{q}}\times{\ab{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\).
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 connaissance 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 :
Le Théorème-Définition 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~:
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: entier
DEBUT
i ← 1
TQ ((i ≤ |u|) ET (i ≤ |v|) ET (u[i] = v[i]) FAIRE
i ← i + 1
FTQ
SI ((i > |u|) ET (i > |v|)) ALORS
renvoyer 0 u = v
SINON SI ((i > |u|) OU ((i ≤ |v|) ET (u[i] < v[i]))) ALORS
renvoyer -1 u < v
SINON SI ((i > |v|) OU ((i ≤ |u|) ET (u[i] > v[i]))) ALORS
renvoyer +1 u > v
FSI
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)=\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\), 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 \(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 un 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é :
Puisque la complexité ne dépend que de la longueur du plus petit mot, on peut alors conclure
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^*\) des mots sur un alphabet fini \(A:=\{a_1,a_2,\ldots,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 \(\color{yellow}\bullet\) indique où va être rangé le prochain mot de la liste :
\begin{align*} &\ 0 & &\ 1 & &\ 2 & &\ 3 & &\ 4 \\ L&=[l{\color{yellow}e},as,os,ai] & L&=[a{\color{yellow}s},os,ai] & L&=[o{\color{yellow}s},ai] & L&=[a{\color{yellow}i}] & L&=[\;]\\ C_{\color{yellow}e} &= [{\color{yellow}\bullet}] & C_e&=[le] & C_e&=[le] & C_e&=[le] & C_e&=[le]\\ C_i &= [\;] & C_i&=[\;] & C_i&=[\;] & C_{\color{yellow}i}&=[{\color{yellow}\bullet}] & C_i&=[ai]\\ C_s &= [\;] & C_{\color{yellow}s}&=[{\color{yellow}\bullet}] & C_{\color{yellow}s}&=[as,{\color{yellow}\bullet}] & C_s&=[as,os] & C_s&=[as,os] \end{align*}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 :
\begin{align*} &\ 0 & &\ 1 & &\ 2 & &\ 3 & &\ 4 \\ L&=[{\color{#46F}l}e,ai,as,os] & L&=[{\color{#46F}a}i,as,os] & L&=[{\color{#46F}a}s,os] & L&=[{\color{#46F}o}s] & L&=[\;]\\ C_a&=[\;] & C_{\color{#46F}a}&=[{\color{#46F}\bullet}] & C_{\color{#46F}a}&=[ai,{\color{#46F}\bullet}] & C_a&=[ai,as] & C_a&=[ai,as] \\ C_{\color{#46F}l}&=[{\color{#46F}\bullet}] & C_l&=[le] & C_l&=[le] & C_l&=[le] & C_l&=[le]\\ C_o&=[\;] & C_o&=[\;] & C_o&=[\;] & C_{\color{#46F}o}&=[{\color{#46F}\bullet}] & C_o&=[os] \end{align*}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_1u_2\ldots 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_ku_{k+1}\ldots u_l\) si \(k\leq l\) et le mot vide \(\varepsilon\) si \(k > l\). On a donc en particulier \(u[1:\;]=u\).
La liste \(S_{1}\) contient uniquement la dernière lettre de chacun des mots de la liste \(L\) après le premier tri par répartition donc \(P(1)\) est vraie puisqu'il s'agit du tri alphabétique. Soit \(k < l\). À l'étape \(k+1\) l'algorithme TriRépartition trie les mots de la liste \(L_{k}\) suivant la prochaine lettre à la position \(-(k+1)\). Soit \(u\) et \(v\) deux mots de la liste \(L_k\). Notons \(a_i\) et \(a_j\) leurs \((-(k+1))\)-ème lettre respectivement. Puisque le \((k+1)\)-ème tri par répartition se fait sur cette lettre, trois situations se présentent :
À 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\).
TriLexico(@L):liste données L: liste de mots variables P: liste la partition en L_k k: entier debut P ← Partition(L) k ← #P #P = l TQ k > 0 FAIRE Concaténer(P[k],L) TriRépartition(L,(u,k) ↦ j) u_k = a_j k ← k - 1 FTQ finLa fonction d'adressage \((u,k)\mapsto{\color{yellow}j}\) utilisée à instruction #12 est celle qui renvoie le numéro \({\color{yellow}j}\) de la \(k\)-ème lettre \(u_k\) du mot \(u\), i.e. telle que \(u_k=a_{\color{yellow}j}\).
Complexité
On rappelle que \(q:=\#A\). On note \(n:=\#L\) la longueur de la liste à trier, \(n_i:=\#L_i\) la longueur de la liste des mots de longueur \(i\) et \(l\) la longueur du mot le plus long. On a \begin{equation}\label{eq:sumlongueurs} \sum_{i=1}^ln_i=n. \end{equation}L'algorithme Partition demande \(\Theta(n)\) opérations pour calculer la longueur maximale \(m\) (instruction #9) puis \(\Theta(m)\) opérations pour initialiser les \(m\) listes \(L_i\) (instructions #11 à #14). La répartition des \(n\) mots dans les \(l\) casiers a un coût en \(\Theta(n)\), on a donc \begin{equation} T_{\textsf{Partition}}\ \ (n,l)=\Theta(n) + \Theta(l) \end{equation}
L'algorithme TriRépartition a un coût de \(\Theta(q)\) pour initialiser les \(q\) casiers à la liste vide, un coût de \(\Theta(\nu)\) pour répartir les \(\nu\) éléments de la liste d'appel et un coût de \(\Theta(q)\) pour concaténer les \(q\) casiers, soit au total \begin{equation} T_{\textsf{Répartition}}\ \ (\nu,q)=\Theta(\nu) + \Theta(q) \end{equation} Pour évaluer la complexité de l'algorithme TriLexico, il nous reste à calculer le coût des \(l\) appels successifs à l'algorithme de tri par répartition (instruction #12) pour chacune des \(l\) 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 (\ref{eq:sumlongueurs}), soit \(O(n)\). On peut à présent conclure : \begin{align*} T_{\textsf{TriLexico}}\ \ (n,l,q) &=\Theta(n) + \Theta(l)\quad\text{(instruction #8)}\\ &\ +l\Theta(1)\quad\text{(instructions #10, #11 et #13)}\\ &\ +l(O(n)+\Theta(q))\quad\text{(instruction #12)}\\ &=O(ln) + \Theta(lq) \end{align*} Le cardinal de l'alphabet étant constant et la longueur maximale \(l\) des mots étant asymptotiquement négligeable devant la taille de la liste, on peut conclure que
Travaux pratiques
Écrivez une fonction Python PPL(u, v) qui renvoie 0 si \(u=v\), -1 si \(u < v\) et 1 si \(u > v\).
Écrivez les fonctions Python Partition(L), TriRepartition(L) et TriLexico(L). Écrivez une fonction GenListe(n,l) qui renvoie une liste de \(n\) mots de longueur \(\leq l\) choisis aléatoirement. Comparez le temps d'exécution pour trier une liste avec vos fonctions et la fonction de tri de Python.
[Solution en C]