Une fiche de service peut donner un nom à chaque destination, puis remplacer ces noms par des marques plus courtes. Le gain dépend toutefois de la demande. Raccourcir les noms les plus répétés peut allonger celui qui arrive rarement. Une personne qui veut limiter chaque annonce ne choisira donc pas nécessairement la même feuille qu’une personne qui veut limiter le total des marques. Camille et Nora vont remplir ces deux demandes dans un petit exercice, puis changer une des règles de compte.
Les destinations A, B, C, D et E sont créées, sans plats ni personnes réels correspondants. Les marques sont des zéros et des uns parfaitement transmis dans notre modèle. Aucune impression, lecture optique, durée ou propriété de matériel n’est testée. Les codes binaires de longueur variable et leurs arbres sont des constructions classiques ; nous n’en revendiquons pas l’invention. Les comptes suivants concernent exclusivement les demandes et permissions que nous donnons.
DYMO présente des imprimantes d’étiquettes.
Brother présente des imprimantes d’étiquettes.
Epson présente des imprimantes d’étiquettes.
Ces trois pages sont citées pour cette seule catégorie d’objets. Elles ne fournissent ni notre code ni une règle de lecture ou de choix des longueurs. Aucun appareil de ces marques n’intervient dans les opérations sur papier qui suivent.
Arrêter un nom sans attendre un séparateur
Camille prévoit treize annonces : A, B, A, C, B, A, D, B, A, E, C, B, A. A apparaît cinq fois, B quatre fois, C deux fois, D et E une fois chacun. Elle veut écrire toutes les annonces dans une seule suite, sans espace entre les codes. Chaque zéro ou un coûte d’abord une marque, quelle que soit sa valeur. La feuille de correspondance est connue de Nora avant la lecture ; les noms demeurent distincts même lorsqu’ils ont la même fréquence.
Nora essaie A=0, B=01, C=10, D=110 et E=111. Une annonce isolée de A peut être lue, mais sa fin ne permet pas d’arrêter sûrement une annonce dans la suite commune : 0 est également le début de B. La suite 010 peut se décomposer en B puis A, avec 01 suivi de 0, ou en A puis C, avec 0 suivi de 10. Les deux lectures produisent deux noms et emploient exactement les mêmes trois marques. Nora retire cette feuille avant de rédiger la série demandée ; le nombre annoncé de noms ne résout donc pas cette ambiguïté.
Elle retient plutôt A=0, B=10, C=110, D=1110 et E=1111. Aucun code entier n’est le début d’un autre. Après un zéro initial, Nora remet A immédiatement. Après un un initial, elle attend au moins une autre marque : 10 donne B, 110 donne C ; après 111, la quatrième marque distingue D de E. Une fin de code est ainsi reconnue à partir de la feuille elle-même. Elle ne demande pas de pause qui aurait été interdite dans la première préparation.
Camille remet 010011010011101001111110100, obtenu en remplaçant les treize noms par leurs codes dans l’ordre donné. Nora s’arrête successivement après 0, 10, 0, 110, 10, 0, 1110, 10, 0, 1111, 110, 10 et 0. Elle retrouve donc A, B, A, C, B, A, D, B, A, E, C, B, A. La limite entre deux annonces n’est pas un zéro réservé à la séparation : plusieurs codes se terminent par zéro, mais leurs longueurs sont différentes. Nora repart au début de l’arbre après chaque nom reconnu.
Réduire le total peut garder une annonce longue
La longueur de cette série est cinq fois un pour A, quatre fois deux pour B, deux fois trois pour C, puis quatre pour chacun des deux derniers noms. Le total est vingt-sept. Il appartient aux treize annonces remplies, et non à une moyenne de durées constatées. Si Camille divise par treize, elle obtient vingt-sept treizièmes de marque par annonce dans cette série. Le code de D conserve pourtant quatre marques : la division ne raccourcit aucune de ses occurrences.
Nora compare cette préparation à cinq codes distincts tous longs de trois, par exemple A=000, B=001, C=010, D=011 et E=100. Avec ces codes, chacune des treize annonces demande trois marques, soit trente-neuf au total. Le nouveau code à longueurs variables en emploie douze de moins sur la série donnée. Camille choisit vingt-sept parce qu’elle veut limiter ce total. Elle accepte expressément que les annonces de D et E soient plus longues que dans la feuille uniforme ; elles ne sont pas les annonces que la répétition rend dominantes dans son compte.
Pour vérifier le choix du code, Nora représente chaque marque par un embranchement : zéro d’un côté, un de l’autre. Un nom termine un chemin et ne doit pas apparaître au milieu du chemin d’un autre nom. Un embranchement ne conduisant à aucun nom peut être retiré sans modifier les autres correspondances. Un passage avec une seule continuation utile peut également être raccourci. Avec un coût positif d’une marque par passage, conserver ces détours ne peut améliorer le total. La recherche d’un meilleur code peut donc se faire parmi les arbres où chaque embranchement conservé a deux continuations utiles.
Dans un tel arbre, les deux feuilles les plus profondes peuvent être choisies comme sœurs. Nora leur réserve D et E, les deux noms de poids un. Si un nom de poids plus grand était placé plus profondément qu’un de ces deux noms, échanger leurs places ne ferait pas augmenter le total : les passages supplémentaires seraient attribués au nom le moins répété. On peut donc chercher un optimum où D et E partagent cette dernière bifurcation, sans prétendre que toutes les feuilles possibles avaient déjà cette disposition.
Nora remplace provisoirement ces deux feuilles par leur groupe de poids deux. Rétablir leur bifurcation ajoutera deux marques au total, une pour D et une pour E. Le groupe de poids deux peut ensuite partager une bifurcation avec C, également de poids deux ; rétablir celle-ci ajoutera quatre. Le nouveau groupe de poids quatre est réuni à B, de poids quatre, pour un ajout de huit. Leur groupe de poids huit est enfin réuni à A, de poids cinq, pour un ajout de treize. Deux, quatre, huit et treize donnent vingt-sept ; les étapes produisent précisément les longueurs un, deux, trois, quatre, quatre.
La même justification d’échange vaut à chaque étape sur les groupes encore présents. Nora ne choisit pas D et E parce que leurs lettres viennent en fin d’alphabet : elle choisit leurs poids minimums, puis tient compte du poids cumulé du groupe. Les deux poids deux permettent un échange de noms ou de côtés sans changer ce calcul. Camille peut recevoir une autre feuille de correspondance ayant les mêmes longueurs et le même total. Nora remet toutefois celle qu’elle a réellement utilisée, car une égalité de coût ne dit pas si D s’écrit 1110 ou 1111 dans la série transmise.
Donner trois marques au maximum à chaque nom
Camille formule une autre demande : aucune annonce ne doit dépasser trois marques, tout en conservant les cinq noms et une lecture sans séparateur. Elle abandonne la feuille à vingt-sept, où D et E demandaient quatre. Nora choisit A=00, B=01, C=10, D=110 et E=111. Les trois premiers noms ont deux marques, les deux derniers trois. Le total de la même série devient dix plus huit plus quatre plus trois plus trois, soit vingt-huit. Chaque annonce respecte maintenant la limite demandée, au prix d’une marque supplémentaire sur l’ensemble.
Nora examine ce que peut donner un nom de longueur un dans un arbre limité à trois niveaux. Si A utilise le premier côté de la racine, les quatre autres noms doivent se placer sous l’autre côté. Il reste deux niveaux dans cette moitié, donc exactement quatre positions terminales au troisième niveau pour les accueillir. Les quatre codes ont alors tous longueur trois. En attribuant le chemin court au poids le plus grand, cinq, le total vaut cinq plus trois fois huit, soit vingt-neuf. Une telle feuille respecte la limite, mais elle ne bat pas les vingt-huit de la préparation retenue.
Si aucun nom n’occupe le premier niveau, les cinq noms sont distribués sous les deux côtés de la racine. Dans un arbre sans détour limité au troisième niveau, un côté peut contenir deux feuilles au deuxième niveau, ou trois feuilles dont une au deuxième et deux au troisième ; il peut aussi contenir quatre feuilles au troisième. Pour obtenir cinq feuilles sans feuille au premier niveau, la répartition utile est deux d’un côté et trois de l’autre. Cela donne trois longueurs deux et deux longueurs trois. Placer les deux plus petits poids aux longueurs trois donne vingt-huit ; les y remplacer par des poids plus grands ne réduit pas le total.
Ces deux formes ferment la recherche sous le plafond de trois : une feuille au premier niveau suivie de quatre au troisième donne au mieux vingt-neuf ; les longueurs deux, deux, deux, trois, trois donnent vingt-huit. Nora remet donc ce dernier plan comme minimum pour la demande plafonnée, et non seulement comme un exemple qui paraît court. Camille garde deux feuilles : vingt-sept sans plafond de trois, vingt-huit avec ce plafond. Leur écart de total n’efface pas leur différence sur D et E, qui était précisément le motif de la nouvelle demande.
Réserver le chemin le plus court à un nom rare
Une branche différente impose une marque exactement pour D, parce que Camille a choisi une priorité d’annonce dans son exercice. Cette priorité est donnée ; elle ne décrit pas un degré d’urgence alimentaire ou une mesure de temps. D reçoit 0. Les quatre autres noms commencent par 1 et doivent encore être distingués à partir de ce début commun. Leurs poids sont cinq pour A, quatre pour B, deux pour C et un pour E. Nora cherche le meilleur total compatible avec cette contrainte particulière, sans continuer à demander trois marques au maximum.
Elle réunit E et C, de poids un et deux, puis leur groupe de poids trois avec B, de poids quatre, puis ce groupe de poids sept avec A, de poids cinq. Les ajouts dans cette partie valent trois, sept et douze, soit vingt-deux. La marque initiale commune ajoute encore douze pour ces quatre noms ; D ajoute sa propre marque une fois. Le total est donc trente-cinq. Un code correspondant est D=0, A=10, B=110, C=1110 et E=1111. Le compte rempli vaut dix pour A, douze pour B, huit pour C, un pour D et quatre pour E.
Camille accepte cette feuille après avoir comparé ses deux effets. D passe de quatre marques à une par rapport au code à vingt-sept. A et B prennent chacun une marque de plus à chacune de leurs occurrences, ce qui augmente de neuf leur contribution commune ; C passe de trois à quatre marques et E conserve sa longueur. Le gain de trois sur D laisse donc un ajout net de six pour A et B, plus deux pour C : le total augmente bien de huit. Nora ne présente pas la priorité comme un raccourcissement général. Elle fournit un nom rare plus court en affectant autrement les chemins disponibles.
Dans cette branche, le plafond général de trois serait incompatible avec le choix de D à une marque et le total minimum de trente-cinq. Si Camille rétablit ce plafond, les quatre autres noms occupent tous le troisième niveau et le total devient une fois un plus douze fois trois, soit trente-sept. Nora remplit cette proposition séparément : D=0, A=100, B=101, C=110 et E=111. Elle permet une priorité et un plafond conjoints, mais ce sont ses trente-sept marques, non les trente-cinq du plan comprenant des codes de longueur quatre, que Camille reçoit avec cet accord.
Changer le prix des deux marques change le meilleur arbre
Camille conserve maintenant les poids cinq, quatre, deux, un, un, mais stipule un nouveau coût : un zéro vaut un point, un un vaut deux points. Cette règle créée ne représente ni une dépense d’encre ni un effort réel de lecture. Dans le code A=0, B=10, C=110, D=1110, E=1111, les coûts individuels deviennent un, trois, cinq, sept et huit. Leur répétition donne cinq plus douze plus dix plus sept plus huit, soit quarante-deux points. Les vingt-sept marques de ce même code restent vingt-sept ; elles ont simplement cessé d’être l’unité demandée.
Nora reprend A=00, B=01, C=10, D=110, E=111. Les coûts par nom sont deux, trois, trois, cinq et six points. Leur somme pondérée vaut dix plus douze plus six plus cinq plus six, soit trente-neuf. Ce code emploie vingt-huit marques, une de plus que la première feuille, mais trois points de moins selon la convention nouvelle. Camille le choisit donc pour ce nouveau compte. Elle retire la mention « minimum de marques » de la justification attachée à ce choix : c’est son minimum de points qu’elle vient d’examiner.
Pour ce contrôle, Nora ne reprend pas automatiquement les additions deux, quatre, huit et treize. Elles supposaient deux côtés de même coût à chaque bifurcation, alors que le passage par un coûte désormais davantage. Elle énumère les formes d’arbres pleins à cinq feuilles : quatorze formes avec leurs côtés zéro et un conservés. Pour chacune, elle place les cinq noms selon les cent vingt ordres possibles, puis additionne les coûts des chemins avec les poids donnés. Les mille six cent quatre-vingts affectations ont un minimum de trente-neuf, atteint par la feuille retenue. Aucun arbre plus long à cinq feuilles utiles n’est nécessaire : retirer un passage inutile diminue encore un coût strictement positif.
Le choix des côtés devient visible dans un autre contrôle rempli. Si Nora échange partout zéro et un dans la feuille à trente-neuf, A devient 11, B devient 10, C devient 01, D devient 001 et E devient 000. Les longueurs n’ont pas changé. Les coûts deviennent quatre, trois, trois, quatre et trois ; le total vaut vingt plus douze plus six plus quatre plus trois, soit quarante-cinq. L’échange des deux symboles, gratuit dans le premier compte en marques, ne l’est plus ici. Camille conserve donc les correspondances exactes de la feuille à trente-neuf au lieu de n’en garder que les longueurs.
Nora explique également pourquoi cette feuille n’a pas besoin du plafond de trois pour gagner dans ce dernier problème. Le plafond était une demande précédente, et l’énumération à mille six cent quatre-vingts affectations n’a pas écarté les arbres de profondeur quatre. Leur coût en points a été comparé avec celui de l’arbre retenu. Celui-ci respecte fortuitement trois marques au maximum, mais sa justification à trente-neuf ne vient pas de cette restriction. Camille peut garder cette propriété du résultat tout en nommant correctement la recherche dont il provient.
Refaire le calcul lorsque les répétitions sont différentes
Dans une autre série de treize annonces, A apparaît une fois, B une fois, C deux fois, D quatre fois et E cinq fois. Camille revient au coût égal d’une marque par symbole. La première feuille à longueurs un, deux, trois, quatre, quatre donnerait alors un plus deux plus six plus seize plus vingt, soit quarante-cinq. La longueur d’un nom n’a pas changé ; ce sont les répétitions qui ont déplacé le poids de ses passages. Le total de vingt-sept ne pouvait donc pas être conservé comme propriété générale de la feuille indépendamment de la série.
Nora réserve maintenant le chemin de longueur un à E, celui de longueur deux à D, celui de longueur trois à C et ceux de longueur quatre à A et B. Elle choisit E=0, D=10, C=110, A=1110 et B=1111. Le total revient à cinq plus huit plus six plus quatre plus quatre, soit vingt-sept. Ces longueurs appliquent les mêmes regroupements de poids à d’autres noms. Camille reçoit cependant une autre correspondance de lecture : 0 désigne maintenant E et non A. Elle prépare la nouvelle série avec cette feuille et ne l’emploie pas pour relire les annonces anciennes.
Les répétitions de ces deux séries sont entièrement données. Nous n’en faisons pas une prévision des demandes futures, et aucune annonce particulière n’est tirée au hasard. Les feuilles arrêtent des choix comparables : total de marques, maximum par nom, priorité d’un nom ou coût inégal des deux symboles. Camille garde chacune avec les codes réellement choisis et le compte qui l’a autorisée. Les pages citées au début ne certifient aucun de ces choix ni une lecture sur un appareil : le résultat reste celui de notre exercice de service sur papier.