Nora prépare une bande d'annonces fictives pour le service. Camille souhaite retrouver un nom à une position, compter ses apparitions dans une partie de la bande et choisir le quatrième nom de cette partie si ses noms étaient classés. Ces demandes portent sur une suite créée ; elles ne mesurent aucune commande réelle ni un travail d'impression. Une liste de fréquences globales ne suffira pas à toutes les réponses, car Camille conserve également les limites des parties qu'elle interroge.
SATO présente des imprimantes d'étiquettes.
cab présente des imprimantes d'étiquettes.
Printronix Auto ID présente une rubrique d'impression d'étiquettes.
Ces catégories situent seulement les annonces écrites. Aucun appareil, alphabet ou procédé de lecture réel n'est adapté ; les images ne sont pas examinées.
Les noms sont les nombres zéro, un, deux, trois. Leurs codes binaires fixes sont respectivement zéro-zéro, zéro-un, un-zéro, un-un. Nora reçoit la suite trois, zéro, deux, un, trois, deux, zéro, un, aux positions zéro à sept. Elle va conserver une ligne des premiers chiffres, puis deux lignes des seconds chiffres : une pour les noms dont le premier chiffre est zéro, l'autre pour ceux dont il est un. Chaque ligne conserve l'ordre relatif des occurrences reçues. C'est un petit arbre classique de partitions stables, dit arbre d'ondelettes ; aucun nouveau procédé matériel n'est revendiqué.
Une séparation conserve l'ordre relatif de chaque côté
La ligne principale donne un-zéro-un-zéro-un-un-zéro-zéro. Les noms partis à gauche sont zéro, un, zéro, un, dans cet ordre ; leurs seconds chiffres donnent zéro-un-zéro-un. Ceux partis à droite sont trois, deux, trois, deux ; leurs seconds chiffres donnent un-zéro-un-zéro. Camille garde ces trois lignes auprès de leurs emplacements dans l'arbre. Une ligne gauche n'est pas une seconde bande autonome de service : elle représente les seules occurrences de premier chiffre zéro, avec les positions nouvelles que leur extraction leur a données.
Camille propose de classer les noms à l'intérieur de chaque côté avant de garder leurs seconds chiffres. À gauche, elle obtiendrait zéro, zéro, un, un et la ligne zéro-zéro-un-un, au lieu de zéro-un-zéro-un. Le nombre de chaque nom serait préservé. Mais la seconde occurrence passée à gauche est celle qui occupait la position trois sur la bande initiale ; c'était un. La nouvelle ligne lui donnerait zéro. Nora retire donc cette permutation locale. Le simple partage par premier chiffre ne suffit pas : pour retrouver les anciennes positions, chaque côté doit préserver l'ordre dans lequel ses occurrences ont quitté la ligne principale.
Nora définit le rang d'un chiffre avant une borne i comme le nombre de ses apparitions aux positions strictement inférieures à i. La borne zéro donne donc zéro, et la borne huit lit toute la ligne principale. Le chiffre placé exactement à la borne n'est pas compté. Cette convention permet de transporter une position et les deux limites d'une plage avec le même compte de préfixe. Elle ne fournit aucun tri des noms, ni score de préférence ; rang signifie ici combien d'occurrences d'un chiffre ont été rencontrées avant la limite donnée.
Lire un nom transporte une position vers son côté
Camille demande le nom à la position cinq. La ligne principale porte un à cette position. Avant cinq, elle contient trois uns, aux positions zéro, deux et quatre. La position cinq devient donc la position trois, comptée à partir de zéro, dans la ligne droite. À cette place, le second chiffre est zéro. Camille réunit premier chiffre un et second chiffre zéro et remet deux. Le chiffre trois utilisé pour choisir la place droite n'était pas le nom recherché : il comptait les passages précédents vers ce côté. Nora garde les deux opérations successives, destination puis position locale, au lieu de remplacer l'une par l'autre.
Nora fait ensuite le contrôle de la position trois. Son premier chiffre est zéro. Avant trois, seul le zéro de la position un est passé à gauche ; la place locale vaut donc un. La ligne gauche porte un à cette place. Les deux chiffres zéro-un remettent le nom un, conforme à la bande. Lire directement la ligne gauche à la position trois aurait donné également un dans cette réalisation, mais sans suivre les occurrences reçues. Camille conserve la place locale un, dont le lien à la bande peut être justifié, et ne s'appuie pas sur une égalité fortuite de deux chiffres.
Chaque occurrence placée à gauche possède exactement autant de prédécesseurs à gauche que son rang de zéros avant sa place principale. La partition stable lui donne cette place locale, sans occurrence d'un autre côté intercalée. Le second chiffre peut donc être retrouvé dans la ligne correspondante. La même propriété vaut à droite. Nora peut reconstruire les huit noms par cette lecture, sans demander une liste exacte conservée ailleurs. Leur représentation garde toute la suite ; elle diffère ainsi d'une fiche où les collisions auraient détruit les noms et leurs positions.
Compter un nom dans un préfixe ne lit pas son dernier emplacement
Camille veut compter les deux dans les six premières annonces, aux positions zéro à cinq. Les six premiers chiffres contiennent quatre uns. Les quatre premières places de la ligne droite représentent donc exactement ces annonces passées à droite. Parmi leurs seconds chiffres un-zéro-un-zéro, deux sont zéro. Le compte recherché vaut deux. Nora ne prend ni quatre, le nombre de noms deux ou trois dans le préfixe, ni la dernière position trois de la ligne droite comme fréquence. Elle suit les deux conditions du nom : premier chiffre un, second zéro, en conservant la limite correspondante après chaque séparation.
Pour compter deux dans les seules positions un à six incluses, Camille utilise les bornes un et sept. Le rang d'uns avant un vaut un ; avant sept il vaut quatre. Dans la ligne droite, la plage devient donc les positions un, deux, trois, soit l'intervalle de bornes un et quatre. Ses seconds chiffres sont zéro, un, zéro ; deux noms correspondent à deux. Nora garde également la plage gauche de bornes zéro et trois, issue des rangs de zéros aux deux limites. Elle peut ainsi répondre sur une portion principale sans y traiter les autres noms comme s'ils avaient disparu partout.
Le transport des deux bornes conserve une portion contiguë dans chaque côté parce que les occurrences ont été extraites dans l'ordre. Toutes celles situées entre les deux limites se placent entre les deux rangs correspondants ; aucune située avant ou après ne s'y glisse. Si l'on avait classé les noms dans la ligne gauche, la différence de deux rangs de seconds chiffres ne porterait plus sur cette portion d'origine. Camille conserve donc la stabilité déjà choisie, et non seulement les totaux de zéros et d'uns de chaque ligne.
Revenir à une position principale demande des sélections successives
La commande change : Camille veut maintenant l'emplacement de la deuxième apparition du nom deux dans toute la bande. Elle prend la deuxième occurrence de zéro dans la ligne droite. Ses zéros sont aux places un et trois ; elle choisit trois. Cette place droite correspond à la quatrième occurrence d'un dans la ligne principale, puisqu'on commence à compter les places à zéro. Les uns principaux se trouvent à zéro, deux, quatre, cinq : la quatrième est à cinq. Nora remet cinq comme position de la deuxième annonce deux. La place trois rencontrée au niveau inférieur n'était pas directement une position sur la bande.
Cette remontée fait l'inverse de la lecture descendante. La position cinq avait trois uns avant elle, donc arrivait à la place droite trois ; sélectionner le quatrième un principal lui rend cinq. Camille vérifie ce va-et-vient sur l'occurrence effectivement demandée avant de remettre son emplacement. Elle ne sélectionne pas le deuxième un de la ligne principale simplement parce que la commande disait deuxième deux : le premier chiffre un regroupe également les trois. Il faut d'abord déterminer le rang local de l'occurrence recherchée parmi tout le côté droit, puis remonter avec ce rang élargi.
Camille conserve les deux dans la plage de bornes un et sept. Avant cette plage, la bande contient zéro apparition de deux ; la première et la seconde apparition demandées dans la plage sont donc aussi la première et la seconde dans toute la bande. Elles reviennent aux positions deux et cinq. Pour une plage commençant à trois, un deux est déjà passé à la position deux. Demander le premier deux de la nouvelle plage revient donc à sélectionner le deuxième deux global, toujours à cinq. Nora effectue cette conversion de rang depuis le préfixe exclu, plutôt que de relire une sélection globale portant un autre numéro d'occurrence.
Choisir un nom classé ne choisit pas sa position d'arrivée
Camille reprend les positions un à six incluses. Leurs noms sont zéro, deux, un, trois, deux, zéro. Elle demande le quatrième si ces six noms étaient classés numériquement, en conservant les répétitions. À gauche, le transport de bornes a conservé trois occurrences, zéro, un, zéro. Ces trois noms précèdent tous ceux de droite dans l'ordre zéro, un, deux, trois. Le quatrième ne peut donc être à gauche ; Camille retire trois de son rang demandé et cherche le premier nom classé dans la plage droite. Les bornes un et quatre de cette ligne portent zéro, un, zéro, donnant deux, trois, deux.
Il y a deux zéros dans cette portion droite, donc deux occurrences du nom deux avant le nom trois. Le premier demandé appartient à ce groupe zéro : Nora remet deux. Elle ne remet pas la place principale trois, qui venait du compte gauche, ni la première position d'arrivée du côté droit. Classer la portion complète aurait produit zéro, zéro, un, deux, deux, trois ; le quatrième est bien deux. La descente par les nombres d'occurrences a répondu sur la valeur ordonnée, tout en laissant la bande d'arrivée inchangée dans ses lignes.
La même commande exige de préciser si les répétitions sont conservées. Les noms distincts de cette plage sont zéro, un, deux, trois : leur quatrième est trois. La commande avec occurrences demandait deux. Nora ne peut donc garder le nombre trois de gauche lorsqu'elle veut seulement des identités : ce nombre comprenait deux occurrences de zéro. Elle choisit de conserver la commande avec répétitions pour l'arbre présent. Si Camille réclame la variante distincte, elle doit disposer d'un autre compte de diversité ; les rangs de chiffres utilisés ici ne l'ont pas produit par simple changement de libellé.
Camille demande également combien d'annonces de cette plage portent un nom au plus égal à un. Le premier chiffre zéro représente exactement cette condition dans l'alphabet retenu. Nora remet directement les trois occurrences de la plage gauche, sans aller lire ses deuxièmes chiffres. Pour la condition « au plus deux », elle ajoute les deux zéros de la plage droite et remet cinq. Le nom trois est le seul refusé. Elle garde cette décomposition de la condition numérique en un côté entier et une partie de l'autre, au lieu de tester seulement le premier chiffre de deux et d'inclure tous les trois avec lui.
Changer les codes peut garder la lecture et perdre l'ordre numérique
Une autre préparation attribue zéro au code un-un, un à zéro-zéro, deux à un-zéro et trois à zéro-un. Les quatre noms restent identifiables et les mêmes opérations de lecture et de compte sont possibles avec cette nouvelle table. Mais le côté zéro contient désormais un et trois, et le côté un deux et zéro. Prendre tout le premier côté comme les plus petits noms classés serait faux. Camille conserve la distinction entre une correspondance injective de lecture et une correspondance qui respecte l'ordre numérique ; la première n'impose pas la seconde.
Sur la bande entière, chacun des quatre noms apparaît deux fois. Avec cette nouvelle correspondance, l'ordre des codes est un, trois, deux, zéro. Une descente choisissant la quatrième occurrence selon cet ordre remet donc trois. La quatrième occurrence selon l'ordre numérique zéro, un, deux, trois devait remettre un. Nora retire trois de la commande numérique, tout en conservant la lecture exacte de chaque nom selon les codes nouveaux. Elle ne renomme pas trois en un à la fin : cela aurait donné un autre nom que celui effectivement sélectionné. Elle reprend les codes numériques initiaux pour la commande de quantile.
Une modification transporte une occurrence entre deux lignes
Camille remplace maintenant le nom zéro de la position un par trois. Le premier chiffre de cette position passe de zéro à un. Nora retire le premier second-chiffre zéro de la ligne gauche, qui devient un-zéro-un. À droite, le nouveau nom est placé après le trois de la position zéro et avant le deux de la position deux : ses seconds chiffres deviennent un-un-zéro-un-zéro. La ligne principale devient un-un-un-zéro-un-un-zéro-zéro. Camille conserve ces trois changements ensemble. Une occurrence a changé de côté, et les places locales des occurrences suivantes ne peuvent rester celles de la bande précédente.
Si Camille changeait seulement le premier chiffre principal, puis conservait les deux lignes anciennes, lire la position trois donnerait zéro au lieu d'un. Avant trois, la nouvelle ligne n'a aucun zéro ; la place locale gauche deviendrait zéro, où l'ancienne ligne portait zéro. Après la vraie suppression, cette place gauche zéro porte un et restitue bien le nom resté à la position trois. Nora refuse donc la modification d'une seule marque principale. Elle ne corrige pas le résultat lu après coup ; elle effectue la suppression et l'insertion nécessaires pour conserver le lien de toutes les occurrences à leurs places.
Une modification restant dans le même côté demande une autre action. Remplacer le trois de la position quatre par deux garde son premier chiffre un. Son rang d'uns avant quatre vaut deux : c'est la place droite deux dont le second chiffre doit passer de un à zéro. Les autres places locales restent les mêmes, et aucune occurrence n'est transférée à gauche. Camille traite cette branche depuis la bande initiale, séparément du remplacement en position un. Nora conserve l'adresse locale calculée dans cette branche, au lieu de reprendre la place droite créée par une autre modification déjà effectuée.
Deux morceaux peuvent être réunis à chaque nœud sans être triés ensemble
Nora partage la bande initiale après quatre noms. Le premier morceau trois, zéro, deux, un donne la ligne principale un-zéro-un-zéro, la gauche zéro-un, la droite un-zéro. Le second trois, deux, zéro, un donne un-un-zéro-zéro, la gauche zéro-un, la droite un-zéro. Pour reconstruire leur concaténation dans cet ordre, elle concatène les lignes principales, puis les deux lignes gauches entre elles et les deux lignes droites entre elles. Elle retrouve un-zéro-un-zéro-un-un-zéro-zéro, zéro-un-zéro-un et un-zéro-un-zéro. Aucun nom complet n'a besoin d'être deviné depuis une fréquence oubliée.
Camille ne concatène pas toutes les lignes du premier morceau avant toutes celles du second sur un ruban unique dépourvu de structure. La première ligne gauche du premier morceau serait alors suivie de sa ligne droite, et non de la gauche du second. Les adresses descendantes n'y auraient plus le même sens. Nora garde les nœuds et les longueurs associées aux morceaux. La réunion choisie exige également leur ordre : inverser les morceaux produit une autre bande principale et un autre dossier d'arrivée, même si les fréquences globales des quatre noms restent deux chacune.
Deux plages séparées ne deviennent pas leur intervalle englobant
Camille demande enfin la quatrième annonce classée dans les seules positions zéro, un, six, sept. Elle conserve les plages de bornes zéro-deux et six-huit, sans recevoir les positions intermédiaires. Les noms demandés sont trois, zéro, zéro, un : classés, ils donnent zéro, zéro, un, trois. Les deux plages envoient respectivement une et deux occurrences à gauche, soit trois au total. La quatrième doit donc aller à droite avec rang un. Seule la première plage y contient une occurrence, le trois initial ; la seconde n'en contient aucune. Nora remet trois depuis ces deux transports de bornes séparés.
Remplacer leurs quatre bornes par zéro et huit inclurait les quatre annonces qui ne faisaient pas partie de la commande. Le côté gauche aurait alors quatre occurrences et la quatrième descendrait à gauche, où elle donnerait un. Camille constate les deux réponses trois et un et conserve trois pour sa demande de deux plages. Les rangs ne portent pas une permission implicite de combler l'espace entre deux morceaux. Nora transmet deux couples de bornes à chaque côté et additionne seulement leurs tailles effectives lorsqu'elle choisit la branche du quantile.
Cette descente peut continuer sans classer les occurrences des deux plages ensemble. Au côté choisi, elle garde les couples de rangs produits par chaque plage ; au niveau suivant, elle additionne les nombres de zéros dans ces portions et compare la demande de rang au total. Toutes les occurrences de plus petit code passent avant celles de plus grand code, quel que soit leur morceau d'origine. Pour la dernière remise, le côté droit ne possédait qu'un trois, qui termine la sélection. Nora remet avec lui les plages réellement interrogées. L'arbre conserve la bande, mais la question conserve aussi les positions qu'elle autorise à compter.
Les catégories citées n'apportent ni code ni règle de rang à ces opérations sur papier.