Pour une feuille de son livre privé, Léa remplace cinq noms par des suites de zéros et de uns. Maud souhaite écrire ces suites bout à bout, puis retrouver les noms sans ajouter une séparation entre chaque paire. Elle veut aussi réduire le nombre de signes de son relevé. Nous composons les noms, les comptes et les règles sur papier ; aucun texte familial réel n’est transmis ni aucun outil de compression essayé. Ce codage ne promet ni secret ni récupération après une faute : la lecture suivante reçoit exactement les signes écrits.
Une notice du Met classe une œuvre parmi les dessins.
Une autre notice du Met classe une œuvre parmi les estampes.
Une troisième notice du Met classe une œuvre parmi les dessins.
Les notices attestent ces catégories seulement. Noms, fréquences et codes sont créés ; aucun procédé des œuvres ne les détermine.
Les cinq noms seront A, B, C, D et E. Léa stipule un relevé de seize mentions : huit A, quatre B, deux C, un D et un E. Ce n’est ni une fréquence mesurée dans des lettres ni une probabilité annoncée pour toutes les futures pages. Le nombre de signes demandé est la somme des longueurs des codes sur ces seize mentions. Maud accepte des longueurs différentes selon les noms. La première règle exige seulement qu’un nom puisse être annoncé dès que son dernier signe a été lu, sans attendre le commencement du nom suivant.
Annoncer un nom sans regarder au-delà de sa fin
Léa propose A=0, B=10, C=110, D=1110 et E=1111. Aucun de ces codes n’est le commencement d’un autre. Par exemple, 10 n’est le commencement ni de 110 ni des deux suites commençant par 111. Lorsqu’on a lu 0, A est complet ; lorsqu’on a lu 10, B l’est. Maud peut donc annoncer le nom et reprendre la lecture d’un nouveau code au signe suivant. La différence des longueurs n’a pas demandé un séparateur : c’est la disposition des commencements et des fins qui l’a remplacé.
Pour les mentions A, B, E puis C, la suite écrite vaut 0101111110. Maud commence par le premier 0 et annonce A. Les deux signes suivants, 10, annoncent B. Elle repart ensuite du premier 1 non utilisé ; 1 puis 11 puis 111 ne sont pas encore des codes complets, tandis que 1111 annonce E. Il reste 110, qui annonce C. Elle a utilisé un, deux, quatre puis trois signes, dix en tout, et retrouve les quatre noms dans l’ordre reçu. Elle n’a pas recherché toutes les occurrences de 0 ou de 10 dans la suite : celles qui seraient internes au code d’un autre nom ne sont pas de nouvelles mentions.
Léa donne aussi une preuve de cette manière de lire. Si deux découpages annonçaient des premiers noms différents, leurs codes commenceraient tous deux au premier signe de la suite. Le code le plus court serait alors le commencement du plus long, ou les deux seraient identiques. Le premier cas est interdit, le second donnerait le même nom. Le premier nom est donc déterminé. Une fois son code retiré, la même comparaison s’applique au reste de la suite. Pour tout relevé fini correctement encodé, Maud retrouve ainsi un seul découpage, avec la possibilité d’annoncer chaque nom sans consommer un signe de la mention suivante.
Le nombre de mentions donne un coût précis
Les longueurs choisies sont un pour A, deux pour B, trois pour C, quatre pour D et quatre pour E. Sur le relevé donné, les huit A demandent huit signes ; les quatre B huit ; les deux C six ; D et E quatre chacun. La somme vaut trente. La longueur moyenne sur ces seize mentions est trente divisés par seize, soit quinze huitièmes. Léa conserve en même temps quatre comme longueur du plus long code. La moyenne plus petite que deux ne signifie pas que chaque mention serait terminée après deux signes : D et E demandent précisément le double.
Maud compare une feuille utilisant trois signes pour chaque nom, cinq suites distinctes choisies parmi les huit disponibles. Cette feuille est immédiatement lisible, puisque tous les codes ont la même longueur ; elle demande quarante-huit signes pour les seize mentions. La première proposition en demande dix-huit de moins, sous le relevé exact de Léa. Maud ne transforme pas cette économie en une mesure de taille d’un livre réel. Elle choisit le catalogue de longueurs différentes pour ce relevé, puis demande une preuve de minimum plutôt qu’un simple avantage sur une proposition uniforme.
Un arbre représente les fins permises
Maud dessine une bifurcation à chaque signe lu : zéro vers une branche, un vers l’autre. Un nom figure seulement à une fin de branche, jamais à une bifurcation qui aurait encore des noms plus bas. Dans le catalogue proposé, la première branche zéro finit sur A ; la branche un continue, puis zéro finit sur B, puis une autre branche un poursuit vers C, D et E. La longueur d’un code est le nombre de bifurcations entre le départ et sa fin. Aucun nom ne remplit la racine : un code vide empêcherait de distinguer les autres mentions.
Léa remarque qu’une bifurcation ne possédant qu’une seule branche utilisée n’aiderait pas à distinguer les noms situés plus bas. On peut supprimer son signe commun et raccourcir tous ces codes d’une position, sans créer un commencement égal à un code extérieur à ce groupe. Le coût baisse, puisque chaque nom apparaît au moins une fois dans le relevé. Une réalisation minimale ne conserve donc pas de tels passages inutiles. Dans l’arbre retenu pour comparer les minima, chaque bifurcation possède deux branches utilisées. Avec cinq noms, la profondeur ne peut dépasser quatre : chaque bifurcation sur un trajet garde au moins un autre nom dans la branche quittée.
Cette réduction donne un domaine fini pour le contrôle. Les arbres à cinq fins et à deux branches utilisées par bifurcation ont quatorze formes orientées. On peut les construire en partageant les cinq fins en un et quatre, deux et trois, trois et deux, ou quatre et un, puis en répétant les mêmes partages dans les morceaux. Sur chacune, les cinq noms peuvent être répartis de cent vingt façons. Léa peut ainsi comparer mille six cent quatre-vingts affectations d’arbres complets, plutôt qu’essayer des codes arbitrairement longs. Son contrôle retrouve trente comme minimum. La preuve suivante explique aussi pourquoi les petites fréquences se regroupent dans le code remis.
Regrouper les deux plus petits comptes réduit le problème
Considérons deux places de profondeurs différentes dans un arbre. Si un nom plus fréquent est placé plus bas qu’un moins fréquent, les échanger ne fait pas monter le coût : on retire à la grande fréquence des signes et on les ajoute seulement à la petite. Plus précisément, avec comptes a au moins égal à b et profondeurs d au moins égale à e, l’ancien coût ad+be dépasse le nouveau ae+bd de (a−b)(d−e), positif ou nul. Léa peut donc choisir une réalisation minimale où les noms les moins fréquents occupent les places les plus profondes, sans changer la forme de l’arbre.
Parmi les fins les plus profondes, il existe deux sœurs, issues de la même dernière bifurcation. Sinon, la branche voisine de chacune devrait continuer et posséder une fin encore plus profonde. Les deux plus petits comptes, ceux de D et E, peuvent donc être installés ensemble à ces deux places, en conservant un minimum. Léa remplace cette paire par une seule fin provisoire de compte deux. Si sa profondeur est d, les deux noms avaient chacun la profondeur d+1. Leur coût commun dépassait celui de la fin provisoire d’exactement deux, leur somme de comptes. Le catalogue réduit possède désormais quatre fins au lieu de cinq.
La même réduction s’applique au catalogue restant. Le nouveau compte deux et celui de C, également deux, se regroupent en quatre, ajoutant quatre au coût réduit. Ce compte quatre rejoint celui de B, quatre, pour former huit et ajouter huit. Enfin ce huit rejoint celui de A, huit, donnant une racine de compte seize et un supplément seize. Les suppléments sont deux, quatre, huit et seize : total trente. Chaque réduction peut être faite dans une réalisation minimale, et chaque regroupement peut être développé en une bifurcation complète. La borne obtenue et le code A=0, B=10, C=110, D=1110, E=1111 se rejoignent donc réellement.
Les deux comptes égaux à un ne décident pas laquelle des dernières branches porte D. Léa peut échanger D et E entre 1110 et 1111 sans changer le coût. Elle retient D pour la branche zéro parce qu’elle veut cette convention sur la feuille, et laisse l’autre proposition comme alternative. Le minimum trente n’établit donc pas un code unique pour chacun des cinq noms. Maud garde le catalogue exact auprès de la suite encodée ; envoyer la même suite avec un catalogue où D et E auraient été échangés pourrait changer les noms lus, même si les deux catalogues avaient le même coût total.
Limiter chaque lecture à trois signes change le meilleur total
Une destinataire ajoute maintenant une condition : aucun nom ne doit demander plus de trois signes. Le code à trente n’y répond plus, car D et E en demandent quatre. Léa propose A=0, B=100, C=101, D=110 et E=111. Le premier code est seul dans la branche zéro ; les quatre autres utilisent les quatre fins de longueur trois de la branche un. La lecture reste immédiate. Sur le relevé reçu, A demande huit signes et les huit autres mentions trois chacune, soit vingt-quatre : total trente-deux. Maud accepte les deux signes supplémentaires pour remplir la limite individuelle.
Pour vérifier ce minimum, Léa compte les fins possibles d’un arbre complet limité à trois bifurcations. Appelons a, b et c les nombres de codes de longueurs un, deux et trois. Il y a cinq fins, donc a+b+c=5. Chacune de longueur un occupe quatre des huit prolongements possibles à trois signes ; chacune de longueur deux en occupe deux ; chacune de longueur trois un. L’arbre complet donne donc 4a+2b+c=8. En soustrayant, on obtient 3a+b=3. Les seules répartitions sont un code de longueur un et quatre de longueur trois, ou trois de longueur deux et deux de longueur trois.
Dans la première répartition, placer le compte huit sur la fin courte donne trente-deux, déjà réalisé. Tout autre choix du nom court augmente le coût. Dans la seconde, les trois plus grands comptes, huit, quatre et deux, peuvent bénéficier de longueur deux ; les deux comptes un prennent longueur trois. Le total minimal de cette forme vaut deux fois quatorze plus trois fois deux, soit trente-quatre. Léa choisit donc la première forme avec trente-deux. Elle n’a pas simplement coupé le dernier signe de D et E dans l’ancienne feuille : ils deviendraient tous deux 111, et l’unicité des noms serait perdue.
La condition trois pourrait être remplacée par deux, mais cinq noms ne tiendraient alors pas. Deux signes offrent au plus quatre fins distinctes lorsqu’on exige la lecture immédiate : un code plus court utilise lui-même plusieurs de ces prolongements et n’en ajoute pas. Maud refuse cette demande pour les cinq noms, au lieu de produire une cinquième suite qui répéterait l’une des quatre. Elle conserve trois comme limite réalisable et trente-deux comme meilleur total sous cette limite. Ce refus ne concerne pas la correction d’une faute dans un code : toutes les lectures restent ici exactes, et c’est leur nombre de fins disponibles qui manque.
Conserver l’ordre des noms impose d’autres regroupements
La destinataire exige ensuite un ordre de présentation précis, D, A, B, E, C. Elle lit les codes comme des suites ordonnées, avec zéro avant un, et veut retrouver les noms dans cet ordre quand les codes sont triés. Le catalogue libre à trente donnait A, B, C, D, E ; il ne suffit pas de changer les titres des colonnes en gardant les mêmes suites. Léa doit construire un arbre où les cinq fins suivent l’ordre reçu. Elle ne demande pas cet ordre parce que les lettres se classeraient ainsi dans un alphabet : c’est une décision éditoriale ajoutée au modèle.
Dans un tel arbre, chaque branche contient un morceau consécutif de cette liste. Les noms de la branche zéro viennent tous avant ceux de la branche un ; on ne peut pas mettre D et E seuls dans une même dernière bifurcation si A et B doivent se trouver entre eux. Le regroupement initial des deux comptes un, correct sans ordre imposé, n’est donc plus une réduction automatiquement autorisée. Maud conserve la somme deux dans l’ancien calcul, mais retire la paire D–E de sa nouvelle proposition. Le manque n’est ni une faute de lecture ni un score changé : la forme admise de l’arbre a réellement obtenu une autre contrainte.
Léa trouve D=00, A=01, B=10, E=110 et C=111. Le tri donne bien D, A, B, E, C, et aucun code n’est le commencement d’un autre. Les contributions au relevé sont deux pour D, seize pour A, huit pour B, trois pour E et six pour C : total trente-cinq. La profondeur maximale reste trois. Cette feuille satisfait donc aussi la limite individuelle précédente, sans avoir son minimum trente-deux. Maud garde trente-cinq avec l’ordre reçu ; trente-deux appartenait au choix libre des noms sur les fins courtes, pas à cette liste imposée.
Pour contrôler les quatorze formes sous cet ordre, Léa compare les endroits où couper la liste à la racine. Chaque signe ajouté en tête augmente le coût de toutes les mentions de la branche ; les deux branches ajoutent donc ensemble seize au coût de leurs arbres plus petits. Une liste ne contenant qu’un nom demande zéro signe supplémentaire à l’intérieur de ce morceau. Pour un morceau plus long, elle choisit la coupure qui réduit au plus les deux coûts intérieurs, puis ajoute la somme des comptes du morceau. Cette procédure conserve les noms comme fins ; elle ne place pas l’un d’eux à une bifurcation qui pourrait annoncer une réponse avant les autres.
Les quatre coupures initiales, après D, après A, après B ou après E, donnent respectivement quarante et un, trente-cinq, quarante et un et quarante-quatre. Le minimum trente-cinq coupe après A, donnant D, A à gauche et B, E, C à droite. Le morceau gauche nécessite une bifurcation, compte total neuf ; le morceau droit, comptes quatre, un, deux, a un coût intérieur dix. Seize plus neuf plus dix retrouve trente-cinq. À droite, B finit immédiatement dans la branche zéro du morceau ; E et C partagent sa branche un. Léa développe ainsi le code remis, plutôt que conserver un minimum calculé dont l’ordre des fins n’aurait jamais été écrit.
Un découpage unique n’est pas forcément une annonce immédiate
Maud examine enfin deux noms seulement, X et Y, codés par 0 et 01. Le code de X est bien le commencement de celui de Y, donc il ne respecte pas notre première permission de lecture immédiate. Pourtant les suites finies valides possèdent un découpage unique. Chaque un doit être précédé du zéro avec lequel il forme 01 ; aucune suite du catalogue ne commence par un et deux uns voisins ne sont pas valides. Les autres zéros représentent X. Ce contrôle force les paires 01 et laisse les zéros restants seuls, sans choisir arbitrairement une frontière.
Sur 001, le découpage est 0 puis 01, donc X puis Y. Sur 010, il est 01 puis 0, donc Y puis X. La suite 011 est refusée, puisque le dernier un n’a pas son zéro disponible pour un nouveau code. Maud ne lui donne pas Y puis un nom inventé pour le signe restant. Léa conserve ces résultats comme un autre catalogue lisible sous une procédure qui accepte d’attendre, sans prétendre que l’interdiction des commencements aurait été nécessaire à toute forme de décodage unique.
Après avoir reçu le premier zéro, Maud ne peut toutefois pas annoncer X immédiatement. Si le signe suivant est un, elle doit annoncer Y ; si le relevé se termine à ce zéro, elle doit annoncer X. Ces deux suites recevables possèdent le même début reçu et demandent deux premiers noms différents. La séparation unique de la suite complète n’a donc pas donné une réponse à cet instant. Léa conserve ses cinq codes sans commencement inclus dans un autre pour la commande d’annonce immédiate. Elle laisse 0 et 01 comme témoin où le découpage reste unique avec une attente effectivement nécessaire.
Remettre le catalogue correspondant au choix rempli
La première feuille du livre garde les cinq codes de coût trente sous les seize mentions stipulées. La feuille limitée à trois signes garde trente-deux ; celle dans l’ordre D, A, B, E, C garde trente-cinq et ses codes propres. Maud ne remet pas la suite construite avec un catalogue sous les noms d’un autre. Les fréquences ont fourni un coût total, les fins de branches une manière de lire, et les permissions supplémentaires deux autres constructions. Chacun de ces résultats reste lié à la demande qui l’a produit.
Aucune œuvre citée ne fournit ces fréquences, ces noms ou leurs codes. Les décisions composées gardent leurs règles propres, sans application d’un procédé des œuvres.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →