Camille prépare une suite fictive de cartes portant les noms A, B, C et D. Nora veut conserver un petit relevé de leurs nombres d'apparitions, sans inscrire les quatre fréquences sur ce relevé. Elle utilise deux rangées de deux cases ; chaque nom ajoute une unité dans une case de chaque rangée. Une consultation prend le plus petit des deux nombres rencontrés. Ce modèle classique de résumé de fréquences permettra de borner certains comptes, puis de vérifier ce qu'une fusion ou un retrait conserve réellement.
Les pages suivantes identifient des lecteurs. Aucun comptage, calcul ou règle de fusion ne vient de leurs textes.
Newland AIDC présente des lecteurs de codes-barres.
Unitech présente des lecteurs de codes-barres.
KOAMTAC présente des lecteurs de codes-barres.
Aucun de leurs appareils ou logiciels n'a été essayé. Les noms et leurs cases sont stipulés sur papier.
Les cases portent zéro et un dans chaque rangée. A va en zéro puis zéro ; B en zéro puis un ; C en un puis zéro ; D en un puis un. Les compteurs sont des entiers sans plafond dans le premier modèle. La suite initiale contient A trois fois, B deux fois, C quatre fois et D une fois, soit dix apparitions. Les noms ont des cases fixes : une consultation ultérieure ne choisira pas de nouveau leurs destinations.
Des collisions augmentent les comptes consultés
La première rangée reçoit cinq en zéro pour A et B réunis, et cinq en un pour C et D. La seconde reçoit sept en zéro pour A et C, puis trois en un pour B et D. Interroger A prend le minimum de cinq et sept, soit cinq, alors qu'A est apparu trois fois. B reçoit trois, C cinq et D trois ; leurs fréquences exactes sont deux, quatre et un. Nora conserve donc les réponses cinq, trois, cinq, trois comme bornes, sans les donner pour les dix apparitions effectivement distribuées entre les noms.
Chaque case consultée par A contient ses trois contributions et celles d'autres noms qui y tombent. Les contributions supplémentaires sont non négatives : chacune de ces cases vaut au moins trois, et leur minimum aussi. La même raison vaut pour les autres noms. Cette garantie est unilatérale dans le modèle d'ajouts positifs. Elle ne promet pas que l'une des deux cases sera débarrassée de toutes les collisions, ni que prendre le minimum ôtera exactement les contributions étrangères. La présence de deux rangées a réduit le choix de borne, sans reconstituer les cartes qu'avaient reçues les cases.
Camille additionne les quatre réponses et obtient seize, supérieur aux dix apparitions. Nora lui fait garder la somme de chaque rangée : cinq plus cinq, ou sept plus trois, vaut bien dix. Les réponses individuelles ont cependant pris leurs minima dans des cases partagées et peuvent compter plusieurs fois des contributions étrangères. Elle refuse donc de remplacer le total dix par seize dans le dossier. Le total d'une rangée décrit tous les ajouts une fois dans cette rangée ; la somme des consultations décrit quatre bornes dont les erreurs peuvent se recouper.
Plusieurs listes exactes peuvent produire le même relevé
Pour connaître ce qui reste ouvert depuis les seuls compteurs, Nora nomme t la fréquence d'A. La première case impose B égal à cinq moins t, la seconde case de la deuxième rangée C égal à sept moins t, puis D égal à t moins deux. Tous les comptes étant non négatifs, t appartient aux entiers deux, trois, quatre ou cinq. Les quatre listes possibles sont donc (2,3,5,0), (3,2,4,1), (4,1,3,2) et (5,0,2,3), dans l'ordre A,B,C,D. Chaque liste reproduit exactement les deux rangées cinq,cinq et sept,trois.
Nora ne peut annoncer A égal à cinq au seul motif que sa borne atteint cinq. Une liste compatible le donne deux ; une autre cinq. Elle ne peut pas non plus annoncer A strictement positif puis en déduire la présence de D : la première liste possède D nul. Camille reçoit le domaine deux à cinq pour A, et zéro à trois pour D, avec les quatre complétions nommées. La feuille n'avait perdu ni le total dix ni les sommes par groupes, mais elle avait perdu un degré de liberté que ces quatre réalisations rendent concret.
Camille réclame ensuite le nombre total d'A et B. Nora peut remettre cinq exactement : il est écrit dans la première case et aucun autre nom ne s'y ajoute sous la convention donnée. Additionner les consultations d'A et B aurait fourni cinq plus trois, soit huit, seulement une autre borne. Pour la demande de groupe, elle utilise donc une case dont l'ensemble de contributeurs correspond exactement au groupe voulu. Cette réponse n'a pas retrouvé séparément trois et deux ; elle garde une somme certaine même lorsque plusieurs partages internes restent compatibles avec tout le relevé.
Une rangée nouvelle peut fermer l'ambiguïté
Une nouvelle préparation ajoute une troisième rangée, regroupant A avec D dans une case et B avec C dans l'autre. Pour la suite exacte initiale, elle porte quatre puis six. Le premier nombre vaut t plus t moins deux, soit deux t moins deux. L'égalité à quatre impose t trois. Nora retrouve alors B deux, C quatre et D un. Elle remet les quatre fréquences avec les trois rangées, et non depuis les deux anciennes auxquelles on aurait seulement donné une légende plus précise.
Cette rangée ne rend pourtant pas la règle des minima exacte à elle seule. A consulte cinq, sept et quatre : le minimum devient quatre, encore supérieur à trois. Nora a retrouvé trois en résolvant ensemble les équations de groupes, pas en prenant trois minima. Camille ne peut donc donner quatre comme fréquence exacte dans la même remise qui vient d'établir trois. La donnée ajoutée et la méthode de consultation doivent être conservées séparément : une rangée peut contenir l'équation qui ferme une ambiguïté sans posséder une case isolant chaque nom demandé.
Fusionner des rangées peut augmenter une borne déjà connue
Nora prépare séparément X avec A trois fois et B deux fois, puis Y avec C quatre fois et D une fois. X donne les rangées (5,0) et (3,2) ; Y donne (0,5) et (4,1). Consulter A dans X donne trois, dans Y zéro. Additionner ces deux réponses donne donc trois. Réunir les relevés par addition de leurs cases produit au contraire (5,5) et (7,3), dont la consultation d'A donne cinq. Les cartes exactes sont pourtant les mêmes sous les deux remises, A trois fois et les autres sept apparitions.
L'addition case par case conserve le résumé ordinaire de la suite réunie, car chaque apparition avait ajouté une unité aux mêmes destinations. Prendre le minimum est une autre opération : la rangée qui donnait la borne la plus basse pour A dans X n'est pas celle qui la donnait dans Y. Dans X, la seconde fournit trois ; dans Y, la première zéro. La somme trois combine donc deux témoins provenant de rangées différentes, tandis que la consultation fusionnée compare seulement cinq et sept. Nora conserve l'ancienne borne trois avec les deux relevés séparés lorsqu'elle veut ce renseignement plus serré ; elle ne prétend pas pouvoir le retrouver depuis les seules cases fusionnées.
Si les noms utilisaient d'autres destinations dans Y, l'addition brute ne représenterait même plus les sommes de la convention initiale. Nora exige donc les mêmes destinations avant cette fusion. Ce contrôle reste bref : la nouvelle distinction remplie porte sur la perte des deux témoins de minimum après une addition pourtant compatible. La compatibilité des cases a garanti la fidélité du relevé fusionné, sans garantir que chaque consultation conserverait toute la précision de réponses obtenues auparavant séparément.
Un retrait légitime diffère d'une fréquence devenue négative
Camille retire les deux apparitions de B effectivement présentes dans la suite initiale. La première case passe de cinq à trois ; la dernière de trois à un. Les deux autres restent cinq et sept. Consulter A donne maintenant trois, qui est sa fréquence exacte. Consulter C donne cinq, toujours au moins quatre. Tous les comptes de noms restent non négatifs, même si l'opération de mise à jour vient de soustraire. Nora ne refuse donc pas tout retrait : celui-ci a conservé les contributions restantes auxquelles la preuve de borne supérieure s'appliquait.
Camille soustrait pourtant un B supplémentaire dans une autre proposition. La fréquence exacte de B deviendrait moins un ; les rangées afficheraient encore des nombres non négatifs, (2,5) et (7,0). Consulter A donnerait deux, au-dessous de ses trois apparitions. Nora refuse la garantie ancienne dans ce modèle de fréquences signées. Regarder seulement les quatre compteurs positifs ou nuls n'avait pas vérifié la non-négativité de chaque nom contribuant aux cases. Le manque d'un B crée une contribution négative qui peut compenser une partie d'A dans la case partagée, sans rendre cette case elle-même négative.
Nora garde donc un registre exact des retraits autorisés lorsqu'elle veut conserver la preuve donnée pour les nombres d'apparitions. Elle remet la première correction, avec B nul et A trois, et écarte la troisième soustraction. Une demande de sommes signées pourrait autoriser cette autre fiche, mais devrait renoncer à la promesse que tous les minima borneront chaque valeur par-dessus. Le défaut n'est pas un arrondi ou un dépassement de compteur : il provient d'une hypothèse sur les contributions individuelles, invisible depuis les seules sommes de groupes.
Modifier seulement les plus petites cases change l'historique
Pour réduire certaines collisions, Nora essaie une autre règle d'ajout : elle examine les deux cases du nom, puis augmente uniquement celles qui atteignent leur minimum actuel. Si elles sont égales, elle augmente les deux. Il s'agit d'une autre procédure classique, explicitement séparée des sommes ordinaires. Les quatre destinations des noms ne changent pas. Nora suit trois apparitions, A puis B puis C, et garde les cases à chaque étape afin de vérifier quelle information cette mise à jour conserve.
Après A, les rangées valent (1,0) et (1,0). B consulte un en première case et zéro en dernière ; Nora augmente seulement cette dernière. C consulte zéro dans la deuxième case de la première rangée et un dans la première case de la seconde ; elle augmente seulement le zéro. La fin vaut (1,1) et (1,1). A, B et C obtiennent chacun une borne un, égale à leur fréquence ; D obtient aussi un alors qu'il est absent. La somme d'une rangée vaut seulement deux, bien que trois cartes aient été ajoutées : cette règle ne conserve plus le certificat de total des sommes ordinaires.
Nora change ensuite uniquement l'ordre, B puis C puis A. B donne (1,0) et (0,1) ; C ajoute dans ses deux cases encore nulles, produisant (1,1) et (1,1). A rencontre maintenant deux un et augmente les deux : la fin vaut (2,1) et (2,1). Sa borne vaut deux, malgré une seule apparition. Camille ne peut fusionner ces deux sorties en prétendant que l'ordre serait sans effet puisque les fréquences finales sont les mêmes. La procédure a sélectionné les cases à augmenter d'après un état intermédiaire qui dépendait de l'ordre ; les additions ordinaires, elles, auraient compté toutes les contributions sans ce choix.
Pour vérifier que la borne reste supérieure dans cette variante à ajouts positifs, Nora considère une apparition d'un nom dont la vraie fréquence est f. Avant l'ajout, ses deux cases sont au moins f. Si leur minimum dépasse f, elles sont déjà au moins f plus un, même lorsqu'une seule augmente. Si le minimum vaut f, toutes les cases qui valent f sont justement augmentées ; les autres valent déjà davantage. Après l'ajout, chaque case consultée est donc au moins f plus un. Cette preuve ne conserve pas les totaux de rangée ni l'indépendance de l'ordre : elle conserve la seule propriété de borne individuelle sous les permissions d'ajout retenues.
Camille réunit enfin un relevé de cette variante pour A seul avec un relevé pour B puis C. Le premier vaut (1,0) et (1,0), le second (1,1) et (1,1). Leur addition donne (2,1) et (2,1), alors que traiter A,B,C ensemble avait donné quatre un. Nora accepte encore les sommes fusionnées comme bornes : chaque case provenant des deux relevés est au moins la fréquence de son nom dans chaque partie. Elle refuse cependant de les qualifier de sortie exacte de l'exécution A,B,C de la variante. Le résultat fusionné coïncide ici avec B,C,A, une histoire différente que les deux relevés séparés n'avaient pas exécutée ensemble.
Deux rangées indépendantes réduisent un bruit déclaré
Une comparaison probabiliste revient aux mises à jour ordinaires. A apparaît trois fois, les autres noms deux, quatre et une fois. Dans chaque rangée, les destinations sont tirées uniformément entre deux cases, indépendamment entre les noms ; les deux rangées sont indépendantes. Conditionnellement à la destination d'A, chacun des trois autres noms la partage avec une chance une moitié. Ce modèle de collisions est stipulé pour la comparaison. Il ne certifie aucune fonction de hachage d'un logiciel ni aucune distribution de noms observée.
Les contributions étrangères à la case d'A sont les sommes de sous-ensembles des poids deux, quatre et un. Les huit sous-ensembles équiprobables donnent une fois chacun zéro, un, deux, trois, quatre, cinq, six et sept. Le bruit d'une seule rangée a donc une moyenne sept demis. Avec deux rangées indépendantes, la borne d'A ajoute le minimum de deux bruits uniformes entre zéro et sept. Nora énumère leurs soixante-quatre couples. Quinze possèdent un minimum nul : A est alors compté exactement trois fois. Les quarante-neuf autres couples donnent une surestimation.
Pour un entier t de un à sept, ce minimum atteint au moins t exactement lorsque les deux bruits atteignent chacun t. La chance vaut ((8−t) sur huit) au carré. Additionner ces sept chances donne le bruit moyen : les carrés de un à sept totalisent cent quarante, donc cent quarante soixante-quatrièmes, soit trente-cinq seizièmes. La moyenne de la borne d'A vaut trois plus ce bruit, quatre-vingt-trois seizièmes. Nora remet ce nombre moyen séparément du trois réel et du quinze soixante-quatrièmes de réponses exactes. Aucun de ces résultats ne signifie que la borne de chaque réalisation serait une fraction.
Camille demande enfin la chance d'une surestimation d'au moins quatre dans ce petit modèle. Chaque bruit appartient à quatre,cinq,six,sept dans quatre de ses huit possibilités ; les deux doivent y appartenir. La chance vaut donc un quart, contre une moitié avec une seule rangée. Nora peut choisir deux rangées pour cette réduction précise. Elle ne transforme pas le quart en un plafond de quatre sur toute réalisation : le couple sept,sept donne encore une erreur sept. Le nombre de rangées et l'événement comparé restent inscrits dans la demande, au lieu de remplacer les soixante-quatre couples par une promesse universelle de petite erreur.
Nora remet les compteurs avec leur convention et leur procédé d'ajout. Les sommes ordinaires se fusionnent en restant des sommes, tandis que les minima peuvent perdre un témoin plus serré. La variante conserve des bornes sous ses propres permissions, avec un historique qui compte. Les cartes fictives servent à contrôler ces décisions ; elles ne constituent aucun essai de lecteur ou garantie pratique de comptage.