Camille prépare des fiches fictives pour un service imaginé avec Nora. Quatre destinations portent les noms A, B, C et D, dans cet ordre. Elle veut remplacer chaque nom par des zéros et des uns, puis ranger les annonces sans retrouver d’abord tous leurs noms. Une préparation courte ne suffit donc pas : la comparaison des codes devra respecter l’ordre choisi pour les destinations. Une seconde commande lui demandera de ranger des messages entiers, dont certains commencent par le même nom.
Les codes préfixes alphabétiques sont classiques. Nos noms, messages et comparaisons sont donnés pour cet exercice ; aucun appareil, impression ou lecteur réel n’est testé. Nous n’annonçons ni une invention de codage ni une économie mesurée sur des fiches matérielles. Les pages consultées nomment seulement une catégorie d’objets.
MUNBYN présente des imprimantes d’étiquettes.
Phomemo présente des imprimantes d’étiquettes.
Rollo présente des imprimantes d’étiquettes.
Ces catégories ne donnent aucun code ni règle de rangement. Les catalogues ont été lus textuellement ; leurs images, performances et procédés ne sont pas utilisés.
Dans la comparaison choisie, zéro précède un. On regarde les marques de gauche à droite : la première différence décide. Si une suite est exactement le début d’une autre, la plus courte vient d’abord. Les noms doivent terminer des chemins : aucun code entier n’est le début d’un autre. Ces prémisses évitent de confondre notre commande avec une conversion des suites en nombres, ou avec une recherche de noms placés à l’intérieur d’un arbre.
Le code le plus court peut mettre B avant A
Camille doit écrire sept noms : A apparaît deux fois, B trois fois, C et D une fois chacun. Une marque coûte une unité dans le compte donné, sans distinguer zéro et un. Si elle peut placer librement les noms aux feuilles, elle retient B=0, A=10, C=110 et D=111. Les contributions sont trois pour B, quatre pour A et trois pour chacun des deux autres, soit treize. Aucun code entier n’est le début d’un autre. Le résultat remplit une commande de longueur totale, mais Nora lui demande encore ce qu’il fait au rangement.
Camille compare les fiches A et B en utilisant ces codes. Le premier signe de A vaut un, celui de B zéro : la fiche B vient avant A. Aucun examen des deuxième et troisième signes ne change cette première différence. Nora retire donc la feuille à treize de sa commande alphabétique. Elle garde la même liste de sept noms et la même convention de coût ; elle n’abaisse pas la fréquence de B pour rendre le premier résultat acceptable. Le défaut est une inversion des destinations, pas une erreur dans le total treize.
Camille essaie de sauver les longueurs en échangeant seulement les côtés de certaines bifurcations. B devrait rester à une marque, avec A devant lui, C et D derrière. Or une feuille placée immédiatement sous la racine occupe un côté entier. Si B porte zéro, tous les autres codes commencent par un et le suivent. Si B porte un, tous les autres commencent par zéro et le précèdent. Aucun échange plus profond ne place A sur un côté de B et C sur l’autre : les trois autres noms appartiennent déjà à la même moitié de l’arbre. Nora refuse de conserver simultanément ce B court et sa position intérieure dans l’ordre A, B, C, D.
Elle choisit plutôt A=0, B=10, C=110 et D=111. Le total vaut deux pour A, six pour B, puis trois et trois : quatorze. Cette fois A précède B à leur premier signe, B précède C au deuxième, et C précède D au troisième. Les quatre comparaisons ne reposent pas sur les fréquences des noms : celles-ci déterminent le coût, tandis que les signes remplissent l’ordre. Nora accepte cette feuille comme candidate conforme et laisse visibles les deux marques ajoutées aux annonces de B, compensées en partie par les deux retirées à A.
Une autre feuille atteint quatorze avec des chemins différents
Camille prépare également A=00, B=01, C=10 et D=11. Chaque nom demande deux marques ; les sept annonces en demandent quatorze. La comparaison conserve encore A, B, C, D. Nora reçoit donc deux feuilles conformes de même coût. Elle ne les fusionne pas en une correspondance où A aurait parfois zéro et parfois deux zéros : les deux préparations restent des dictionnaires différents, chacun connu avant de remplacer les noms de la série.
Pour vérifier le minimum alphabétique, Camille examine les cinq formes d’arbres pleins à quatre feuilles ordonnées. Le partage de la racine peut laisser un nom à gauche et trois à droite, deux de chaque côté, ou trois à gauche et un à droite. Dans les groupes de trois, deux formes sont possibles. Aucun nom ne peut ensuite passer de l’autre côté d’un nom intermédiaire. Les cinq listes de codes sont ainsi 0/10/110/111, 00/01/10/11, 0/100/101/11, 00/010/011/1 et 000/001/01/1, toujours attribuées dans l’ordre A, B, C, D.
Leurs coûts sont respectivement quatorze, quatorze, seize, dix-sept et dix-huit. Camille peut donc fermer la recherche à quatorze, plutôt que déclarer sa première candidate optimale parce qu’elle paraît courte. Les détours à une seule continuation utile ne donnent pas d’autres minima : les raccourcir retire des marques, sans changer l’ordre des feuilles. Nora conserve les deux réalisations à quatorze, puis choisit celle où les quatre noms ont deux marques lorsqu’elle veut aussi cette longueur uniforme. Ce choix supplémentaire ne transforme pas l’autre feuille en une erreur de rangement.
Les noms occupent ici seulement les feuilles. Dans un arbre de recherche ordonné, un nom peut au contraire être la première comparaison et avoir d’autres noms avant et après lui dans ses deux branches. B pourrait donc y être un premier nom intérieur. Camille ne transporte pas cette permission vers son dictionnaire de codes : rencontrer B doit terminer son code, pas ouvrir deux chemins vers A et C. Ce contrôle explique concrètement pourquoi le B d’une marque a été refusé, malgré sa fréquence élevée et malgré la possibilité de placer B à la racine d’un autre type d’index.
Ranger des messages conserve la première différence de noms
Nora revient à la feuille A=0, B=10, C=110, D=111 et compare deux messages : AD et BA. Leur ordre de noms place AD avant BA, puisque A précède B dès la première destination. Les suites codées sont 0111 et 100. À leur première marque, zéro précède un : l’ordre attendu est conservé. Camille remet les deux suites avec cette comparaison, au lieu de les ranger par leur nombre de marques. AD possède quatre marques et BA trois ; choisir systématiquement la plus courte aurait ici produit l’ordre contraire.
Une proposition transforme pourtant 0111 en le nombre binaire sept et 100 en quatre. Le tri numérique met alors BA avant AD. Nora retire cette proposition, dont le résultat contredit les mêmes deux messages sous la comparaison donnée. Camille conserve le zéro initial de 0111 : il porte le début du code de A, et sa disparition n’est pas une simplification autorisée d’un entier. Elle ne corrige donc pas le défaut en ajoutant des zéros devant 100. Elle reprend la comparaison signe par signe, qui avait directement placé AD avant BA avec les suites réellement produites.
Camille compare ensuite AC et AD. Les deux commencent par le même nom, donc par le même code zéro. La comparaison reprend à leurs noms suivants : C=110 et D=111 diffèrent au troisième signe, avec zéro avant un. Les messages codés 0110 et 0111 conservent AC avant AD. Nora n’a pas dû choisir arbitrairement une frontière au milieu de C. Aucun code entier n’étant le début d’un autre, la comparaison de deux noms différents trouve sa première différence avant que l’un ait été entièrement avalé comme une portion commune de l’autre.
Enfin A et AA donnent zéro et deux zéros. Le premier message est un début exact du second, donc il vient d’abord dans la convention choisie. Ce cas ne ressemble pas à AC contre AD : aucune différence de signes ne survient avant la fin de A. Camille applique la règle du début court, qu’elle avait annoncée au départ, plutôt que prolonger fictivement A par un autre nom pour obtenir une différence. Nora reçoit ainsi deux raisons précises de ranger : un premier nom différent, ou un message entier qui finit avant son prolongement.
Ces comparaisons se prolongent à toute suite finie de noms dans ce dictionnaire. Les premiers noms communs donnent des codes communs entiers. Au premier nom différent, l’ordre des codes décide dans le même sens que l’ordre des noms. Si aucun nom ne diffère avant la fin du message le plus court, sa suite codée est elle aussi un début exact. Ce raisonnement décrit la portée de la feuille choisie ; il ne certifie pas un rangement observé sur une machine ni une vitesse de consultation. Les remises AD/BA, AC/AD et A/AA demeurent les contrôles remplis de l’exercice.
Une marque de fin change le cas du message court
Camille veut maintenant écrire plusieurs messages l’un après l’autre et garder leur fin explicite. Nora introduit un cinquième symbole T, qui termine chaque message et ne désigne aucune destination. Elle essaie A=00, B=01, C=10, D=110 et T=111. Les destinations restent dans l’ordre et chaque code peut être arrêté sans séparateur supplémentaire. Pourtant cette propriété des quatre noms ne suffit plus à promettre le même ordre pour les messages terminés.
Le message A devient AT, codé 00111. Le message AA devient AAT, codé 0000111. Leur premier A est commun. La comparaison oppose ensuite le code de T, commençant par un, au deuxième A, commençant par zéro. Elle range donc AA avant A. Nora refuse cette feuille pour sa commande qui demande toujours le message court avant son prolongement. Camille ne peut pas répondre que les deux A ont été correctement reconnus : la reconnaissance des noms et l’ordre des messages sont deux propriétés effectivement séparées par cette remise.
Nora place T avant A, B, C et D dans le nouvel alphabet des symboles. Une fois le premier A commun franchi, la fin T d’un message court devra précéder le premier nom de la suite ajoutée au message long. Cette place n’ajoute aucun nom fictif à la commande de destinations. Camille compare AT et AAT comme deux instructions de fin, puis rejoint la lecture suivante seulement après avoir rencontré T. Une feuille où T serait placé entre B et C échouerait encore sur un message prolongé par A ou B ; les extensions peuvent commencer par n’importe lequel des quatre noms reçus.
La position de T règle exactement le cas qui avait changé. Si deux messages diffèrent déjà par un nom avant leur fin, leurs deux codes de noms décident encore. Si l’un finit pendant que l’autre poursuit les noms communs, la comparaison est maintenant T contre le premier nom ajouté. T placé devant tous les noms conserve alors le court en premier. Camille n’annonce pas que n’importe quelle ponctuation de fin aurait cet effet : le cinquième code possède une place dans le même ordre que les quatre codes de destinations, et cette place vient de la permission de rangement choisie par Nora.
Le premier symbole dans l’ordre n’a pas besoin du code le plus court
Camille propose T=0, A=10, B=110, C=1110 et D=1111. T est bien devant tous les noms et chaque message finit explicitement. La commande contient deux messages, ABB et ABCD. Les noms totalisent toujours A deux fois, B trois fois, C une fois et D une fois ; T apparaît deux fois, une par message. Les fins demandent deux marques, A quatre, B neuf, C quatre et D quatre. Le total devient vingt-trois. Nora ne retrouve pas quatorze en comptant seulement les noms et en donnant gratuitement leurs deux terminaisons.
Une autre feuille conserve le même ordre T, A, B, C, D avec T=00, A=01, B=10, C=110 et D=111. Les deux fins demandent quatre marques, A quatre, B six, C trois et D trois : vingt au total. T s’est allongé d’une marque par occurrence, mais B s’est raccourci de trois marques sur ses trois occurrences et C comme D d’une. Camille reçoit donc un gain net de trois. Nora choisit cette préparation pour le total, sans déplacer T derrière un nom ni lui retirer son rôle de fin.
Camille écrit effectivement ABB puis T : 01, 10, 10, 00, soit 01101000, huit marques. Elle écrit ensuite ABCD puis T : 01, 10, 110, 111, 00, soit 011011011100, douze marques. Les deux remises totalisent vingt. Nora garde les deux occurrences de T à leur place de clôture, après les trois noms de la première et les quatre de la seconde. Aucun code de nom ne vaut 00, et chaque retour au commencement du dictionnaire suit une fin de code entière ; rencontrer T termine le message au lieu de l’allonger d’une destination inconnue.
Sous cette feuille, A seul suivi de sa fin donne 0100. AA suivi de sa fin donne 010100. Les signes 01 du premier A coïncident ; le signe suivant vaut zéro dans la fin T, un dans le deuxième A. Le message court demeure donc premier. Camille remet également AD suivi de T, 0111100, et BA suivi de T, 100100 : le premier signe conserve encore AD avant BA. Nora vérifie ainsi la feuille choisie sur les deux types de comparaison qui comptent, sans remplacer son total de vingt par la seule affirmation que T arrive en tête de l’alphabet.
Vérifier le coût avec la fréquence des fins réellement écrites
Pour cinq feuilles dans un ordre fixé, quatorze formes pleines sont possibles. Camille les contrôle avec les poids deux, deux, trois, un et un, attribués respectivement à T, A, B, C et D. Leurs coûts triés sont vingt, vingt-deux deux fois, vingt-trois trois fois, vingt-cinq deux fois, vingt-six, vingt-sept deux fois, vingt-huit deux fois et vingt-neuf. La feuille T=00, A=01, B=10, C=110, D=111 est la seule à vingt dans ces formes ordonnées. Nora peut donc la remettre comme minimum de la nouvelle commande à deux messages terminés.
La comparaison à vingt-trois ne suffit pas à elle seule à établir ce minimum. Elle avait seulement montré qu’un T forcé à une marque coûte plus cher sur la commande donnée. L’énumération garde T au premier rang, mais autorise ses longueurs possibles dans chaque forme. Les détours inutiles ne produisent pas une meilleure feuille, puisque chaque symbole a ici un poids strictement positif. Camille ne choisit donc pas les vingt après avoir écarté gratuitement toutes les feuilles où T est plus long : la candidate retenue est justement l’une de celles-là.
Nora refuse une préparation qui omettrait T dans le total au motif qu’il ne nomme pas une destination. Cette omission donnerait seize pour la feuille à vingt, mais les deux messages remis contiennent toujours leurs quatre marques de terminaison. Le critère reçu porte sur toutes les marques effectivement écrites. À l’inverse, une seule fin après ABBABCD fabriquerait un seul message de sept noms, alors que Nora en avait reçu deux. Camille conserve donc ABBT et ABCDT séparément, avec leurs huit et douze marques, au lieu de gagner une fin en changeant silencieusement le nombre de messages.
Les deux messages et leurs fréquences sont entièrement donnés. Ce choix de longueur ne prédit pas une série future, et T ne vient d’aucune règle d’impression propre aux pages consultées. Les comptes incluent sa présence réelle dans notre composition. Aucun fait sur les appareils ni aucune image de catalogue n’a servi à changer l’ordre des codes ou la liste des destinations.
Nora conserve enfin la feuille sans terminaison lorsqu’elle veut seulement ranger des annonces isolées, et la feuille à cinq symboles lorsqu’elle veut des messages dont la fin est indiquée. La seconde garde T au premier rang, sans lui réserver automatiquement une marque unique. Les messages AD et BA restent rangés par signes, non comme les entiers sept et quatre. Chaque préparation joint ses correspondances aux messages effectivement remis, afin que le coût, l’ordre des noms et l’ordre des fins restent trois propriétés vérifiables de la même feuille.
Une autre commande range les messages courts avant tous les longs
Nora change expressément de rangement dans une branche séparée. Elle demande d’abord le nombre de destinations, puis l’ordre des noms entre messages de même longueur. AAA doit donc suivre B, même si A précède B. Cette commande ne modifie pas les noms des destinations ; elle ajoute un premier critère portant sur les messages. Camille reprend la feuille à quatre codes A=0, B=10, C=110, D=111, sans marque T dans cette branche.
Les codes ordinaires donnent AAA=000 et B=10, donc mettent encore AAA avant B. Même la fin T devant les noms ne répare pas cette opposition : les premiers noms A et B ont déjà décidé avant que la fin soit rencontrée. Camille retire la promesse de ranger d’abord par longueur au moyen de la seule feuille précédente. Elle ne retire pas AAA de la liste et ne renomme pas B en un nom antérieur à A. Il lui faut porter une information qui précède la comparaison des destinations. La taille de 000 en marques ne pourrait pas la remplacer : trois destinations courtes y occupent trois marques, alors que le nombre de destinations de B vaut un, indépendamment des deux marques de son code.
Camille écrit devant chaque message autant de uns qu’il contient de noms, puis un zéro qui termine ce compte. Pour B, l’en-tête est 10 ; pour AAA, il est 1110. Elle ajoute ensuite les codes des noms, donnant respectivement 1010 et 1110000. Après leur premier un commun, le zéro de l’en-tête de B précède le deuxième un de celui d’AAA. Nora reçoit donc B avant AAA, cette fois sous le critère qu’elle vient de choisir. Le zéro qui ferme le compte ne désigne pas A : la lecture commence par l’en-tête, puis change de rôle pour lire exactement le nombre de noms annoncé. Après les trois codes de AAA, elle sait que ce message est terminé sans ajouter T.
Pour AD et BA, chacun à deux noms, les en-têtes identiques sont 110. Les remises deviennent 1100111 et 110100. Leur compte initial ne les départage pas ; les codes suivants redonnent AD avant BA, au premier nom différent. Camille remet également ABB avec l’en-tête 1110 et ses cinq marques de noms, soit 111001010, neuf marques. ABCD reçoit 11110 devant ses neuf marques de noms, soit 11110010110111, quatorze marques. Nora compte vingt-trois pour ces deux nouveaux messages. Les vingt de la feuille à T restent le résultat d’un autre rangement : elle ne leur attribue pas gratuitement les deux en-têtes ni la priorité donnée à la longueur.