Brevet FR2911716A1 — publié le 20080725

-1- La présente invention concerne des procédés d'écriture, stockage et lecture de données ou identifiants à segments multiples, le nombre et la taille de ces segments étant fixes ou variables, sous forme d'enregistrements de taille fixe sur disques durs, enregistrements de base de données, puces RFID, ou impressions de type codes barres, ceci sans contrainte sur le nombre et la taille de chaque segment, la seule contrainte portant sur la somme des tailles des segments ainsi q'un nombre maximal de segments, à travers l'utilisation d'algorithmes de codage et décodage utilisant une numérotation de toutes les structures de segments possible des identifiants. Le domaine d'application correspond à tous les contextes où les identifiants utilisés sont des listes d'entiers (ou de numéros alphanumériques), comme par exemple dans le domaine des codes barres ou codes GS1, numérotation des livres avec la numérotation ISBN, des revues avec les ISSN, et tous les identifiants de numéros de commandes, de clients, de contrats, de comptes bancaires, de normes, documents, de codes produits, de routes ou pays, utilisés par divers organismes publiques ou privés, nationaux ou internationaux. Ces procédés peuvent également, comme pour les autres, être appliqués à des identifiants informatiques, par exemple pour mettre en place un système de fichier à inodes purement administratifs, ou pour tout autre objets ou symboles informatiques et codes associés. On peut décrire le domaine de manière générale comme étant celui ou les identifiants utilisés ont la forme n1.n2 n . les ni étant des entiers (ou numéros) pouvant éventuellement utiliser des lettres dans leurs représentations, c'est-à-dire de codes formés par une liste de p segments, p étant variable ou pas, et où ces identifiants doivent dans certains contextes techniques être enregistrés sur une taille fixe. Les méthodes actuelles utilisées dans ce domaine pour écrire ces identifiants dans un mot de taille fixe reposent en général : - Soit sur l'utilisation de tailles fixes pour délimiter les segments, comme dans le contexte des codes GS1 (ex FAN et UCC), voir par exemple page 6 section 1 du document GS1 General Specifications v.7.0 disponible à travers le lien ci dessous : http://www.gs1uk.org/EANUCC/WORD.Files/GSSection_1_V7.doc - Soit sur l'utilisation de règles, et maintenance associée de plages , définissant comment séparer un segment en deux à partir des premiers caractères, voir par exemple les documents ci-dessous dans le domaine de l'ISBN : http:/ /www.isbn.org/standards/home/isbn/international/html/usm4.htm http://www.isbn-international.org/converter/ranges.htm -2- Des identifiants de la forme indiquée sont aussi bien sûr souvent utilisés sans contrainte de taille sur leurs écritures, ceci à l'aide d'une séparation syntaxique des différents segments par des caractères . , / , ou autre. Cela est tout à fait approprié dans de nombreux cas, et ne pose absolument aucun problème. Cependant la contrainte de taille fixe existe aussi souvent, pour une forte automatisation du traitement de ces identifiants, ou pour des contraintes d'implémentations ou de traitements informatiques et/ou réseaux. Les procédés d'écriture décrits pourraient donc aussi être utilisés sur ces espaces d'identifiants quand les contraintes de taille existent. La mise en oeuvre de ces procédés permettrait certainement une meilleure dynamique ou percolation de ces identifiants, ainsi qu'une gestion grandement simplifiée de leurs distributions, permettant en retour une utilisation plus extensive, et donc une plus grande cohérence et évolutivité des systèmes les utilisant. 1) Description détaillée L'énoncé du problème est donc le suivant : on considère un espace d'identifiants de la forme n,.n2 n1, à ms ou moins segments 9?1 et ms) que l'on veut représenter dans un mot machine de p bits, ou p octets. Les segments nk sont considérés comme des entiers, qu'ils apparaissent comme tels dans le code considéré ou à travers des règles de transformation/représentation. Nous considérerons dorénavant que l'espace de représentation cible est basé sur des octets, mais les principes et algorithmes énoncés peuvent s'appliquer à l'identique sur des bits, voir la partie Applications industrielles pour plus de détails à ce sujet. Il s'agit donc de définir, pour des identifiants de type n,.n2 n1, , des fonctions Cod et Decod prenant respectivement, un identifiant et le transformant en un mot machine, un mot machine et le transformant en un identifiant, et telles que la composition de Decod et Cod soit égale à l'identité sur l'espace d'identifiants de départ. Ce que l'on peut noter de la manière suivante : Cod(ms,P) :NUN2 U...UNms ù> / 1 fo,1}s)P S (fo, d'Y' Decod(ms P) : ({0,118 )P --> N U N2 U... U Nms U 0 SE({o,i}')P Decod(,,,s,P) o Cod(ms,P) = Id~ur~Zu...uN . -3- Le principe de base est de permettre à chaque segment d'avoir une taille variable dans la chaîne cible. Nous appellerons ici une liste de tailles de segments dans la chaîne cible une structure . Une structure est donc une liste de la forme (t,, avec j ms. L'idée est de numéroter toutes les structures possibles pour un couple (ms,p) donné. Ceci permet de définir la fonction Cod comme étant la fonction qui à une liste (n1.n2 n)), va d'abord déterminer la structure optimale pour les ni, va ensuite calculer le numéro de structure correspondant, et enfin bâtir la chaîne S par concaténation de ce numéro de structure et des représentations binaires ou hexadécimales des n;. Pour la fonction Decod , on déduira d'abord de S la structure utilisée à partir du numéro de structure, puis on utilisera cette structure comme masque pour déterminer la liste (n1.n2 n~) correspondante. Le problème se ramène donc à définir, pour un couple (ms,p) donné, des fonctions NStruct 15 et DNStruct ayant la forme suivante. Nous utilisons ici pour simplifier la notation : N(ns) =0U N UN2 U...0 Nms NStruct : N(ms) N (1',,12,...,t_), ms H nstruct O, ou 0 H 0 DNStruct : N N(" nstruct H (t, OH0 Et telles que : DNStruct(,,,5 p) 0 NStruct(m$ p) = IdN( ) La fonction NStruct prend une liste de tailles de segments et retourne un numéro de structure, la fonction DNStruct retourne une liste de taille de segments à partir d'un numéro de structure. L'ensemble vide ou liste vide est aussi considéré, avec comme numéro de structure 0 pour des raisons de régularité des algorithmes. La composition de ces fonctions doit être égale à 25 l'identité. Méthode 1 : Dans cette solution, on considère toutes les structures possibles, y compris celles qui ne remplissent pas tous les octets. Cependant, on gaspille les octets d'un côté et on tasse les 20 -4-identifiants de l'autre, c'est-à-dire que l'on compte par exemple une seule structure à 1 segment de 1 octet dans 3 octets. Commençons par calculer le nombre total de structures à exactement ms segments noté ici Sms(p) pour un couple (ms,p) donné, nous avons : S0(p) = 1 : le nombre de structure vide dans p octets est 1, ceci pour régularité des algorithmes S1(p)=1 : il y a une seule structure à 1 segment dans p octets S2(p)=p-1 : il y a p-1 structures à 2 segments dans p octets, la limite entre les deux segments pouvant aller d'après le premier octet, jusqu'à avant le dernier octet. Par récurrence on a : p-1 SJ (P) = E i=J-1 C'est-à-dire, le nombre de structures possible à j segments dans p octets est la somme du nombre de structures possibles à J-1 segments, sur un nombre d'octets variant de p-1 à J-1, la place disponible pour le premier segment variant entre 1 et p-(J-1). A la main, ou à l'aide d'outils de calcul symbolique, cela donne : s3 (p) = 2-(P -1)(p -2) Sa (p) = 6 (p -1)(p û 2)(p -3) Ss (p) = 24 (P -1)(p-2)(p -3)(P -4) S6 (p) = 120 (p -1)(p ù 2)(p ù 3)(p ù 4)(p -5) s,(p) = 720 (p -1)(p - 2)(p -3)(P - 4) (p - 5)(p -6) s8 (p) = -(p -1)(p ù 2)(p ù 3)(p ù 4)(p ù 5)(p ù 6)(p ù 7) 5040 Note : Il n'y a pas lieu ici de faire croître ms énormément , en effet le but est de gérer et 20 manipuler des espaces d'identifiants de type n1.n2 n1 , mais pas des formes syntaxiques ou s-expressions dont les ni constitueraient les termes. Autrement dit le nombre de segments doit répondre aux contraintes administratives de distribution, mais pas de classification ou détermination d'objets à travers des phrases ou expressions syntaxiques. Ce qui ne veut pas dire bien sûr que l'on ne puisse pas bâtir après des s-expressions ou formes syntaxique à l'aide de ces 25 identifiants, ni que ces listes aient ou prennent souvent dans la pratique une certaine syntaxe. Que15 -5- le nombre de segments soit fixe ou variable, le moins possible est toujours préférable, un seul suffirait en principe, le choix du nombre de segments et de la variabilité ou pas est bien sûr du ressort des organisations gérant/utilisant ces identifiants. Dans la suite nous nous limitons à 7 au maximum, 5 suffiraient peut-être, les principes et algorithmes restant valable pour tout ms. Plus à ce sujet dans la partie Applications industrielle . Ensuite, pour calculer le nombre total de structures à ms ou moins segments, noté TSn,Ç(p), on a : ms TS(p) = S, (p) 7=0 Les représentations polynomiales des TS ne sont pas ici données, mais peuvent être aisément acquises. Les fonctions TS peuvent aussi être facilement calculées par récurrence de manière programmatique. Principe de numérotation des structures, définitions de NStruct et DNStruct Il faut maintenant définir un algorithme permettant d'expliciter un couple de fonctions NStruct et 15 DNStruct. Pour cela, le principe est de ranger les structures de la manière suivante : [taille premier segment 0][taille premier segment 1]... [taille premier segment p ù cs] Où cs est le nombre d'octets (ou de bits) nécessaires au codage du numéro de structure, ceci est explicité plus en détails dans la partie Applications industrielle , pour simplifier on utilise dans la 20 suite p pour noterp-cs Puis, à l'intérieur de l'intervalle [taille premier segment 1] , on range les structures selon : [taille deuxième segment 0][taille deuxième segment 1]... [taille deuxième segment p-1] A l'intérieur de l'intervalle [taille deuxième segment 1] ci-dessus, on rangera les structures selon : [taille troisième segment 0][taille troisième segment 1]... [taille troisième segment p-3] 25 Et ainsi de suite. Ceci permet de définir un couple de fonctions NStruct et DNStruct Algorithme pour la fonction NStruct : La fonction NStruct prend donc en entrée une liste de tailles de segments. Pour lui affecter un numéro, appelé ici Idstr pour identifiant de structure, le processus est : 30 1. Se positionner sur le bon intervalle correspondant à la taille du premier segment, en incrémentant au passage Idstr des valeurs correspondantes aux intervalles pour lesquels le premier segment à une taille inférieure à sa taille en entrée. Pour cela on utilise le fait que, pour une taille de premier segment 1, le nombre de structures ayant l comme taille de premier segment sur p octets et ns segments, est égal au nombre total de structures sur p-1 35 octets et ns-1 segments. -6- 2. Appel récursif à la fonction NStruct sur la structure moins le premier élément, avec les paramètres positionnés comme il faut 3. Le numéro est Idstrà la fin du processus Algorithme pour la fonction DNStruct : Ici on part d'un numéro Idstr et l'on doit retourner une liste de tailles de segments, le processus est : 1. Se positionner sur le bon intervalle en utilisant l'égalité décrite au point 1 ci-dessus 2. Ajouter la taille du segment courant en fin de structure (clans la liste) 3. Appel récursif à DNStruct à 1' intérieur de l'intervalle en ayant décrémenter Idstr des 10 valeurs correspondants aux intervalles précédents 4. la liste de tailles de segments est la structure en fin de processus Pour expliciter ces algorithmes complètement, les tester, et aussi déterminer les valeurs de cs par rapport à ms etp , ces algorithmes ainsi que les fonctions définies plus haut sont exprimés à travers 15 le programme en langage de programmation Python joint en annexe. En particulier on a les correspondances suivantes : • fonction Sie ci-dessus : fonction Structs ( i , p) du programme • fonction TS,,e) ci-dessus : fonction ST s (i , p ) du programme 20 • fonction NStruct~,nfy) ci-dessus : fonction AlgCodage (ls , MS, P) du programme • fonction DNStruc%,) ci-dessus : fonction Al g De codage (1 s , MS , P) du programme • fonction Code 14) d-dessus : fonction Code Li s t I nt (l int) du programme • fonction Decod(,,1,,)ci-dessus : fonction DecodeListlnt (intg) du programme Méthode 2 : 25 Ici on ne considère que les structures qui utilisent tous les octets. Cela implique, pour avoir la composition de Decod et Cod égale à l'identité, d'ajouter une règle du type : le dernier entier prend toute la place qui reste dans la fonction Cod D'autres règles, telles que les bits ou octets non nécessaires sont affectés au premier entier peuvent être utilisées. Ainsi la fonction Cod est bien une fonction ou application, et n'associe qu'une structure possible à une liste d'entiers donnée. 30 Nous nous limiterons ici au calcul de la fonction déterminant le nombre total de structures pour comparaison avec la première solution, le principe des algorithmes reste le même pour les fonctions NStruct et DNStruct avec des modifications mineures. -7- Si on appelle DS115(p) le nombre de distributions (comme structures dans la méthode 1) utilisant tous les p octets pour un nombre de segments ms, on a : Do(p) : fonction non nécessaire dans ce cas D1(p)=1 : une distribution à 1 segment sur p octets D2(p)=p-1 : même règle que pour S Par récurrence on a: p-J+1 D., (p) _ E D,1(p ù i) i=1 En effet le nombre de distributions à j segments sur p octets est égal à la somme du nombre de distributions à J-1 segments, ceci pour un nombre d'octets variant entre p-1 et J-1 (le premier segment vaut 1 d'un côté, chaque autre segment vaut 1 de l'autre). Et: TD,(p)=ED,(p) =1 Pour les fonctions de nombre total de distributions à J ou moins segments sur p octets. Pour comparaison les fonction '11)5(p) et '11)7(p) sont exprimées de manière programmatique dans le programme Python joint en annexe avec les références : • 11)5(p) : fonction T D5 (p) du programme • '11)7(p) : fonction TD7 (p) du programme Méthode 3 : Cas des espaces d'identifiants à nombre de segments fixe : Les mêmes principes et algorithmes peuvent être utilisés, en utilisant les fonctions S,4) ou D,u(p) pour numéroter les structures, et donc écrire un identifiant ayant un nombre de segments ns fixe, tout en gardant la variation sur la taille de chaque segment. Comme pour la méthode 2, afin de conserver un procédé de codage/décodage bijectif, une règle utilisateur doit être définie, affectant à l'un des segment (le dernier, premier, ou autre) les bits ou octets non nécessaires au codage de l'identifiant.30 Applications Industrielles Tout d'abord, commençons par préciser quelques aspects quantitatifs des algorithmes et codages à travers quelques exemples générés à l'aide du programme joint en annexe : > STs(7,14) 9908 > log(9908,2) 13.274378153246364 > TD7(14) 4096 > log(4096,2) 12.0 > STs(5,14) 3473 > log(3473,2) 11.761966695382092 > TD5(14) 1093 > log(1093,2) 10.094077685671905 > STs(7,7) 128 > log(128,2) 7.0 > TD7(7) 64 > log(64,2) 6.0 > STs(5,7) 120 > log(120,2) 6.9068905956085187 > TD5 (7 ) 57 > log(57,2) 5.8328900141647422 > Structs(5,14) 715 > log(715,2) 8 .4817994316657526 > Structs(4,15) 364 > log(364,2) 8.5077946401986964 > Structs(4,14) 286 > log(286,2) 8.1598713367783891 10 > Structs(5,7) 15 > log(15,2) 3.9068905956085187 > 15 > TD7 (98 ) 1056235426 > log(1056235426,2) 29.976284289125385 > TD5(46) 20 164221 > log(164221,2) 17.325279100082771 C'est-à-dire, sur 16 octets, les méthodes 1 et 2 permettent de coder un identifiant à 7 25 segments variables maximum, en réservant 2 octets pour la structure et 14 octets pour l'identifiant. 2 bits sont gaspillés avec la méthode 1, et 4 avec la méthode 2 ; bits qui peuvent être affectés à l'identifiant selon des règles ou réservés pour utilisation futures imprévues ou locales. Pour 5 segments maximum sur 16 octets, cela donne aussi 2 octets de structure avec 30 respectivement 4 et 5 bits gaspillés pour les méthodes 1 et 2. Sur 8 octets et 7 segments maximum, la structure nécessite 1 octet avec 1 et 2 bits gaspillés respectivement pour les méthodes 1 et 2. Pour 5 segments maximum, 1 octet de structure est également nécessaire avec respectivement 1 et 2 bits gaspillés. 35 Pour un nombre de segments fixe, 2 octets de structure sont nécessaires sur 16 pour 5 segments avec 6 bits de gaspillés. -9 - 10 - Si on prend le bit et non l'octet comme variabilité des segments, 30 bits sont nécessaires sur 128 pour 7 segments maximum avec la méthode 2. On voit donc que l'espace nécessaire à coder la structure est relativement faible par rapport à l'espace disponible pour l'identifiant lui-même. Comme il a été dit au début, toute organisation utilisant des identifiants de type n1.n2 nj, pourrait donc mettre à profit ces techniques pour : 1. Simplifier les règles régissant chaque segment (pas de taille prédéfinie) et l'affectation des numéros correspondants. Seules des règles d'exceptions ou d ( overflow seraient nécessaires dans la distribution, en fonction des formats cibles choisis pour les écritures en taille fixe. 2. Continuer à utiliser une taille fixe pour les identifiants dans tout contexte ou cela s'avère nécessaire ou pratique (bases de données, codes barres, puces RFID, transmission de données, etc ...). Pour faciliter l'utilisation pratique, une organisation utilisant ces techniques devrait probablement limiter le nombre de formats d'identifiants empaquetés utilisés. On peu par exemple imaginer une liste de formats cibles du type : 20 • TS58 : 5 segments maximum sur 8 octets • TS716 : 7 segments maximum sur 16 octets • TS732 : 7 segments maximum sur 32 octets 15 -11- ANNEXE Le programme en langage de programmation Python qui suit est joint dans un but d'explicitation complète des procédés. # -*- coding:Latin-1 -*- # Ce programme a pour but d'exprimer entièrement les fonctions et algorithmes décrits # pour la mise en place des procédés, ainsi que de déterminer le nombre d'octets ou bits # nécessaires au codage du numéro de structure pour un couple (ms, p) donné. # L'implémentation des algorithmes peut bien sur être grandement optimisée une fois les # choix de nombres de segments max et nombres d'octets max faits from math import * from random import * # Structs est la fonction qui retourne le nombre de structures à i segments sur un # identifiant à p octets. # Ou également bien sûr, le nombre de structures à i segments sur un identifiant à p bits. # note: le nombre de structure à 0 segment sur p octets est 1 def Structs (i,p ): if i==l or i==0 : return 1 elif i==2: return p-1 elif i==3: return ((p-1)*(p-2))//2 elif i==4: return ((p-1)*(p-2)*(p-3))//6 elif i==5: return ((p-1)*(p-2)*(p-3)*(p-4))//24 elif i==6: return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5))//120 elif i==7: return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5)*(p-6))//720 elif i==8: return ((p-1)*(p-2)*(p-3)*(p-4)*(p-5)*(p-6)*(p-7))//5040 else: print "i is out of range in Structs, value : " , i -12- # STs est la fonction qui retourne le nombre total de structures à i ou moins segments # dans p octets, # y compris la structure vide (ou à 0 segment) qui compte pour une structure. * cette fonction à réécrire directement en polynomes def STs (i,p) : j=1 r=1 while j #tOc retourne la taille minimale en octets pour coder l'entier i def tOc (i) : if (i==0 or i==l) : return 1 else: return int(log(i,2))//8+ 1 # AlgCodage prend en input une liste ls de tailles de segments, et retourne le numéro de # structure correspondant. # Ceci pour un nombre de segments max MS et une taille d'octets max P. # Idstr est l'offset du numéro de structure dans les appels récursifs. # Le principe est d'incrémenter Idstr avec les structures à taille de premier segment # inférieur à celle considérée, # puis appelrécursif sur le deuxième segment une fois positioné dans le bon intervalle. ls=[] def AlgCodage (ls , MS , P, Idstr=0): 11=len(ls) lsegl=O pos=0 i=0 if 11==0: -13- return Idstr else : lsegl=ls[O] while i =pos : intl=pos lsegl+=l else : break ls.append(lsegl) return AlgDecodage(Idstr-intl,ls,MS-1,P-lsegl) # CodeListlnt prend une liste d'entier en entrée et la transforme en un entier (binaire), # avec le code de structure au début et ensuite les entiers # Note : nous avons fixé ici le nombre de segments max à 7 et le nombre d'octets max à 14 # pour les entiers (16 en tout), ie 128 bits, # la structure est codée sur 16 bits, 13 suffiraient lint= [ ] def CodeListlnt (lint): 11=1en(lint) lo=list(lint) -14- i=o to=o while i 14 : print "overflow", to return to lt=list(lint) nstruct=AlgCodage(lint,7,14) i=0 bint=nstruct 15 offset=16 while i # mmask retourne un masque sur le p octet def mmask (p): 25 ones=255 return ones 8*(p-l) # DecodeListlnt prend un entier ou numéro ISCN "empaqueté" et renvoi la liste d'entiers 30 # correspondante def DecodeListlnt (intg): mask=mmask(l)Immask(2) nstruct= intg & mask intg=intg 16 35 1s=AlgDecodage(nstruct, [],7, 14) 11=len(ls) lint= [ ] i=0 -15- off-0 while i #Test de Code et Decode pour ms=7, n tests sont effectués def test (n): i=1 Tint= [ ] lseg= [ ] while i #Les fonctions ci dessous implémentent les fonctions Dj(p) et TDj(p) #de la méthode ou solution 2 def D1(p): return 1 def D2(p): if p def D3(p): r=O if p def D5(p): r=O 10 if p def D6(p): 20 r=0 if p 30 def D7(p): r=O if p def TD5(p): return D1(p)+D2(p)+D3(p)+D4(p)+D5(p) def TD7(p): return D1(p)+D2(p)+D3(p)+D4(p)+D5(p)+D6(p)+D7(p)10 REVENDICATIONS 1) Procédé d'écriture, de stockage et de lecture de données sur disques durs, enregistrements de base de données, puces RFID, mémoire de type ROM ou RAM, cartes magnétiques ou impressions de type codes à barres caractérisé en ce que les données à écrire, stocker et lire, sont constituées de segments alphanumériques en taille et nombre variables, mais l'écriture est elle de taille fixe sans contrainte sur la taille individuelle de chaque segment et le nombre de ces segments, la seule contrainte portant sur la somme des tailles des segments et un nombre de segment maximal, l'écriture étant constituée d'une part d'un numéro de structure et des segments concaténés, ceci à travers l'utilisation d'un algorithmes de codage utilisant une numérotation de toutes les structures possibles en tailles et nombre de segments, la lecture utilisant elle le numéro de structure pour déterminer tous les segments, en utilisant un algorithme de décodage à partir du numéro de structure . 2) Procédé d'écriture, de stockage et de lecture de données sur disques durs, enregistrements de base de données, puces RFID, mémoire de type ROM ou RAM, cartes magnétiques ou impressions de type codes à barres selon la revendication 1 caractérisé en ce que les segments à écrire sont en nombre et tailles variables, et que toutes les structures possibles sont considérées et numérotées, y compris celles ne remplissant pas tout l'espace d'écriture. 3) Procédé d'écriture, de stockage et de lecture de données sur disques durs, enregistrements de base de données, puces RFID, mémoire de type ROM ou RAM, cartes magnétiques ou impressions de type codes à barres selon la revendication 1, caractérisé en ce que les segments à écrire sont en nombre et tailles variables, et que seules les structures remplissant tout l'espace d'écriture sont considérées et numérotées, ceci étant associé à une règle définie par l'utilisateur pour conserver des processus de codage et décodage dont la composition soit égale à l'identité. 4) Procédé d'écriture, de stockage et de lecture de données sur disques durs, enregistrements de base de données, puces RFID, mémoire de type ROM ou RAM, cartes magnétiques ou impressions de type codes à barres selon la revendication 1, caractérisé en ce que les segments à écrire sont en nombre fixe et tailles variables, et que seules les structures remplissant tout l'espace d'écriture sont considérées et numérotées, ceci étant associé à une règle définie par l'utilisateur pour conserver des processus de codage et décodage dont la composition soit égale à l'identité.